読者です 読者をやめる 読者になる 読者になる

Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

Problem 214(その2)

昨日に引き続き、Project EulerのProblem 214(日本語)です。 いろいろと調べてみると、以下のページを見つけました。 Problem 214 - 落書き、時々落学 効率よくオイラーのφ関数が計算できるようです。実際、自分でもトレースしてみましたが計算できています…

Problem 214

Project EulerのProblem 214(日本語)です。 久しぶりにProject Eulerを解いてみました。といっても、今日から解きはじめたわけではなくて、昨年末くらいから考えては諦め、諦めては考えというのを繰り返していました。1/19にエラトステネスの篩について書い…

エラトステネスの篩

今まで、Project Eulerの問題で素数を扱うときは、Prime.eachを多用してきたのですが、40000000までの素数を扱う問題で、これを列挙するだけでも、かなり時間を要することに気づきました。 そこで、定番のエラトステネスの篩を作って、Prime.eachと速度比較…

Problem 111

Project EulerのProblem 111(日本語)です。 resolveメソッドで、10桁の整数で、ある数字(d)を、cnt回含むような、すべての数字を生成し、それが素数かどうかを判定しています。 最初、M(n, d)の解釈を、「一番多く素数が存在する」という風に勘違いしてしま…

Problem 231

Project EulerのProblem 231(日本語)です。 より、以下のように計算できることを利用しています。 分母-分子 以下のように作ってみましたが非常に実行時間がかかります。また同じような処理が繰り返され、汚いソースになってます。もっと効率良く解く方法が…

Problem 115

Project EulerのProblem 115(日本語)です。 昨日解いたProblem 114と同じような問題でした。resolvメソッドの引数を増やしたり、2次元Hashにしたりしたのですが、不要でした…。 115.rb

Problem 114

Project EulerのProblem 114(日本語)です。 再帰とメモ化の威力はすごいですね。 114.rb

Problem 105

Project EulerのProblem 105(日本語)です。 すべての可能な部分集合の対の組み合わせについて両方のルール(i.とii.)を満たしているか調べています。 105.rb

Problem 137

Project EulerのProblem 137(日本語)です。 が のように表せるところまではできたのですが、そこから先へ進めませんでした。 Problem 137 - もうカツ丼でいいよな を参考にさせていただいたのですが、この問題でもペル方程式が姿を表わすんですね。非常に興…

Problem 243

Project EulerのProblem 243(日本語)です。 以前、Problem 69を解いたときに、「オイラーのφ関数 - Wikipedia」について学んでいたので、これを使えばいいとは思ったのですが、ただ素直に使うだけでは実行時間がかかりすぎました。 もう一歩、自分で考えつけ…

Problem 110

Project EulerのProblem 110(日本語)です。 参考サイトのPythonスクリプトを単純にRubyに置き換えただけで、まだまだ理解は足りません…。 110.rb 参考サイト Project Euler Problem 110 - San_SS!

Problem 135

Project EulerのProblem 135(日本語)です。 とおくと、 divideメソッドで、nを2数の積に分解し、解の個数をチェックしています。 135.rb

Problem 138

Project EulerのProblem 138(日本語)です。 ピタゴラス数、ペル方程式を用いて解きました。 から、 138.rb 関連 Problem 75 - Maeの(Mae向きな)日記 Problem 94 - Maeの(Mae向きな)日記 Problem 100 - Maeの(Mae向きな)日記

Problem 134

Project EulerのProblem 134(日本語)です。 最初、力技で解こうとしましたが、時間の壁に跳ね返されて途中で実行を止めてしまいました。いろいろ調べてみると「拡張ユークリッド互除法」を使うと良いようですね。以下のサイトを参考にしました。 拡張ユーク…

Problem 131

Project EulerのProblem 131(日本語)です。 「Problem 131 - 落書き、時々落学」を参考にしました。 131.rb

Problem 132

Project EulerのProblem 132(日本語)です。 「Project Euler Problem 132 - San_SS!」を参考にしました。考え方を見ると、なるほどなぁと思いますが、なかなか自分では考えつきません…。 Problem 188のModMath.powを利用しました。 132.rb

Problem 188

Project EulerのProblem 188(日本語)です。ミラー-ラビン素数判定法 - Wikipediaで紹介されているModMath.powは、baseのpower乗に対するmodのモジュロを計算してくれます。これを利用すると簡単に解くことができます。 Pythonには、pow(x,y[,z])があるようで…

Problem 174

Project EulerのProblem 174(日本語)です。 昨日のProblem 173と同じような問題でした。 $h[t]は、t枚のタイルで作れるlaminaeの個数が格納されています。例えば、$h[32]は2となります。 174.rb

Problem 173

Project EulerのProblem 173(日本語)です。 久しぶりなので、簡単な問題を選んで取り組んでみました。 173.rb

Problem 117

Project EulerのProblem 117(日本語)です。 117.rb

Problem 116

Project EulerのProblem 116(日本語)です。 116.rb

Problem 108

Project EulerのProblem 108(日本語)です。 式を変形すると、 となるので、の約数の個数を求めて重複を除いた個数で判定しています。 108.rb

Problem 98

Project EulerのProblem 98(日本語)です。 問題を選ぶときは、解いた方が多い問題から解いているので、問題番号が2桁の問題ですが、今になってしまいました。難しいのかと思いきや、そんなに難しくはありませんでした。皆さん、解けそうだと思うので、実装す…

Problem 94

Project EulerのProblem 94(日本語)です。 以前、取り組んでいたのですが、解けずに放ったらかしになっていました。いろいろ調べてみると、ペル方程式が姿を表わすんですね。Project Eulerを通して、何度かペル方程式に出会っていたのですが、この問題に対し…

Problem 191

Project EulerのProblem 191(日本語)です。 「ProjectEuler Problem 191 - peanutsjamjamの日記」を参考に解いています。30bitの数をカウントしていくとき、3連続1の最後の位に1を足す方法は結構、効果的でした。Cでの実行時間で、3分強だったのが20秒程に短…

Problem 145

Project EulerのProblem 145(日本語)です。 力づくの方法でRubyで書いたのですが、なかなか実行が終りませんでした。Cで書くと30秒ほどで解が求まりますが、Fornumを見ると、pencil and paperで解答を導かれている方も多いですね。 145.rb 145.c

Problem 88

Project EulerのProblem 88(日本語)です。 「Solved By」で見たときに、解きやすい問題に分類される問題だと思いますが、自分にとっては難しく、途中で投げ出していた問題です。作成したプログラムは、恥ずかしい出来栄えですが一応完成したので載せておきま…

Problem 204

Project EulerのProblem 204(日本語)です。 最初、以下のように作ってみました。これまでのProject Eulerの経験から分かることなのですが、例題(Type 5のハミング数で上限が)は解けても、本問は時間がかかり過ぎて手におえません。 # -*- coding: utf-8 -*- …

Problem 203

Project EulerのProblem 203(日本語)です。 久しぶりにProject Eulerに取り組んでみました。簡単に解けそうな問題は、もうないだろうと思っていたのですが、Solved Byで探し当てました。 203.rb

Problem 119

Project EulerのProblem 119(日本語)です。 当たり前の方法で解こうとすると時間がかかり過ぎて解けないので、を計算し条件に合っていれば配列ansに格納していきます。 aとnの探索範囲(2〜100)は適当に決めてしまったのですが、本来は、「Project Euler 119 …

Problem 113

Project EulerのProblem 113(日本語)です。 「Project Euler 113 - 桃の天然水」を参考に取り組みました。 最後の答えを表示する行ですが、は、増加数、減少数で111などの同じ数字を重複して数えているので、その分を引いています。ここは自分でも納得してい…

Problem 206

Project EulerのProblem 206(日本語)です。 ただ力ずくの方法で解いているだけです。他にいい方法があるのでしょうか? 206.rb 追記 id:inamori さんからアドバイスをいただきました。 @maehrm どんな問題でもまずは再帰に持ち込むことを考えます。2012-08-1…

Problem 121

Project EulerのProblem 121(日本語)です。 ゲームが4ターンの場合、プレイヤーが勝利する確率は BBBB => RBBB => BRBB => BBRB => BBBR => の和で、となります。 同様に、5ターン、6ターンの場合もノートに書き出すと徐々に解き方が見えてきました。 解いた…

Problem 205

Project EulerのProblem 205(日本語)です。 4面、6面のサイコロを振ったときの目の確率(peter_dice_p,colin_dice_p)を計算しています。 例えば、出た目が9で勝つときは、相手が6, 7, 8が出たときなので、 Peterが9かつColinが6 または、 Peterが9かつColinが…

Problem 187

Project EulerのProblem 187(日本語)です。 配列primesに素数を列挙し、題意を満たす組合せを数え上げています。 187.rb

Problem 179

Project EulerのProblem 179(日本語)です。 179.rb

Problem 125

Project EulerのProblem 125(日本語)です。 配列sum_of_squaresには、1から添字までの2乗の和が入るようにしておきます。例えば、sum_of_squares[2]には、が入っています。 sum_of_squares = [0, 1, 5, 14, 30, 55, 91, 140, 204, 285, 385, … ]sum_of_squar…

Problem 101

Project EulerのProblem 101(日本語)です。 『アルゴリズムC〈第3巻〉グラフ・数理・トピックス』のp127で紹介されているラグランジュの補間公式を用いて解いてみました。 101.rb

Problem 124

Project EulerのProblem 124(日本語)です。 124.rb

Problem 107

Project EulerのProblem 107(日本語)です。 最小全域木の問題でした。以前(2009/06/12)、クラスカルのアルゴリズムは作ったことがあったので、今回はプリムのアルゴリズムで解いてみました。 107.rb

Problem 123

Project EulerのProblem 123(日本語)です。 7/14に解いたProblem 120と似た問題でした。 123.rb

Problem 95

Project EulerのProblem 95(日本語)です。 約数の和は、『数学ガール (数学ガールシリーズ 1)』のp27の方法で求めています。 例えば、の約数の和は、 で求められます。 095.rb

Problem 100

Project EulerのProblem 100(日本語)です。 とてつもなく大きい数を扱うときは、そのまま解いたらとんでもないことは、これまでの経験で分かってきました。 円盤の合計を、青い円盤をとすると となります。 これは、 となって、とおくと、ペル方程式 となり…

Problem 96

Project EulerのProblem 96(日本語)です。 数独を解く問題でした。以下のように解いています。 各セルに入る数字の候補を求める。このとき、候補が一つしかない場合はその数字を埋める。candidateメソッドで行なっています。 次に候補の数字が少ないセルに数…

Problem 120

Project EulerのProblem 120(日本語)です。 二項定理より となります。が偶数のときは常にとなるので考えなくてよくて、が奇数のとき、は以下のように表すことができます。 120.rb

Problem 112

Project EulerのProblem 112(日本語)です。 増加数の場合、up_cnt == (数字の桁数 - 1) 減少数の場合、down_cnt == (数字の桁数 - 1) となることを利用しています。up_cnt(, down_cnt)は左の桁より大きい(小さい)か等しい場合にインクリメントしています。 1…

Problem 104

Project EulerのProblem 104(日本語)です。 普通に作ると非常に遅いので、下9桁のみを保存しておく変数を用意し、これが1から9までの数字をすべて含む場合のみ、頭から9桁をチェックするようにしてみました。 104.rb 追記 「Project Euler 104 - 桃の天然水…

Problem 102

Project EulerのProblem 102(日本語)です。 外積を使ってます。 102.rb

Problem 99

Project EulerのProblem 99(日本語)です。 常用対数を使って比較しています。 099.rb

Problem 97

Project EulerのProblem 97(日本語)です。 さすがのRubyでも なので、下6桁だけ残しながら計算してみました。 097.rb