Euler
Project EulerのProblem 113(日本語)です。 「Project Euler 113 - 桃の天然水」を参考に取り組みました。 最後の答えを表示する行ですが、は、増加数、減少数で111などの同じ数字を重複して数えているので、その分を引いています。ここは自分でも納得してい…
Project EulerのProblem 206(日本語)です。 ただ力ずくの方法で解いているだけです。他にいい方法があるのでしょうか？ 206.rb 追記 id:inamori さんからアドバイスをいただきました。 @maehrm どんな問題でもまずは再帰に持ち込むことを考えます。2012-08-1…
Project EulerのProblem 121(日本語)です。 ゲームが4ターンの場合、プレイヤーが勝利する確率は BBBB => RBBB => BRBB => BBRB => BBBR => の和で、となります。 同様に、5ターン、6ターンの場合もノートに書き出すと徐々に解き方が見えてきました。 解いた…
Project EulerのProblem 205(日本語)です。 4面、6面のサイコロを振ったときの目の確率(peter_dice_p,colin_dice_p)を計算しています。 例えば、出た目が9で勝つときは、相手が6, 7, 8が出たときなので、 Peterが9かつColinが6 または、 Peterが9かつColinが…
Project EulerのProblem 187(日本語)です。 配列primesに素数を列挙し、題意を満たす組合せを数え上げています。 187.rb
Project EulerのProblem 179(日本語)です。 179.rb
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…
Project EulerのProblem 101(日本語)です。 『アルゴリズムC〈第3巻〉グラフ・数理・トピックス』のp127で紹介されているラグランジュの補間公式を用いて解いてみました。 101.rb
Project EulerのProblem 124(日本語)です。 124.rb
Project EulerのProblem 107(日本語)です。 最小全域木の問題でした。以前(2009/06/12)、クラスカルのアルゴリズムは作ったことがあったので、今回はプリムのアルゴリズムで解いてみました。 107.rb
Project EulerのProblem 123(日本語)です。 7/14に解いたProblem 120と似た問題でした。 123.rb
Project EulerのProblem 95(日本語)です。 約数の和は、『数学ガール (数学ガールシリーズ 1)』のp27の方法で求めています。 例えば、の約数の和は、 で求められます。 095.rb
Project EulerのProblem 100(日本語)です。 とてつもなく大きい数を扱うときは、そのまま解いたらとんでもないことは、これまでの経験で分かってきました。 円盤の合計を、青い円盤をとすると となります。 これは、 となって、とおくと、ペル方程式 となり…
Project EulerのProblem 96(日本語)です。 数独を解く問題でした。以下のように解いています。 各セルに入る数字の候補を求める。このとき、候補が一つしかない場合はその数字を埋める。candidateメソッドで行なっています。 次に候補の数字が少ないセルに数…
Project EulerのProblem 120(日本語)です。 二項定理より となります。が偶数のときは常にとなるので考えなくてよくて、が奇数のとき、は以下のように表すことができます。 120.rb
Project EulerのProblem 112(日本語)です。 増加数の場合、up_cnt == (数字の桁数 - 1) 減少数の場合、down_cnt == (数字の桁数 - 1) となることを利用しています。up_cnt(, down_cnt)は左の桁より大きい(小さい)か等しい場合にインクリメントしています。 1…
Project EulerのProblem 104(日本語)です。 普通に作ると非常に遅いので、下9桁のみを保存しておく変数を用意し、これが1から9までの数字をすべて含む場合のみ、頭から9桁をチェックするようにしてみました。 104.rb 追記 「Project Euler 104 - 桃の天然水…
Project EulerのProblem 102(日本語)です。 外積を使ってます。 102.rb
Project EulerのProblem 99(日本語)です。 常用対数を使って比較しています。 099.rb
Project EulerのProblem 97(日本語)です。 さすがのRubyでも なので、下6桁だけ残しながら計算してみました。 097.rb
Project EulerのProblem 93(日本語)です。 1〜9から4つの数字の組合せを作り、以下の計算を逆ポーランド記法により求めています。 解答後、フォーラムを見て気付いたのですが、逆ポーランド記法を使わず中置記法のままでも解くことができますね。 093.rb
Project EulerのProblem 90(日本語)です。 題意(6と9の扱い)を読み取るのに苦労しました…。 090.rb
Project EulerのProblem 91(日本語)です。 今まで解いたProject Eulerの問題は、問題文中に示されている例だと解けるが、探索空間が大きくなると、とても短時間に解けないという特徴があったと思います。この問題は珍しく工夫をしなくてもそれなりの時間に解…
Project EulerのProblem 92(日本語)です。 各数の列を求め89になる個数を数えているだけのシンプルな方法で解いています。同じ数の再計算のないよう一度計算した数値についてはメモをしています。 092.rb
Project EulerのProblem 89(日本語)です。 引き算ペアの文字列の置換だけで正解でした。これだと16がVVVIと書かれていてもXVIと1文字節約できない。roman.txtに含まれる1000個のローマ記法の質があまりよくないのかなと思います。 089.rb
Project EulerのProblem 87(日本語)です。 2乗しても50,000,000を超えない素数のリスト、他、同様に3乗、4乗用のリストをまず作成して、工夫もなく総当たりして解きました。 087.rb
Project EulerのProblem 86(日本語)です。 前回といい今回といい苦戦しています。 「Project Euler Problem #86 « KeyZero Conversation」を参考にさせていただきました。 086.rb
Project EulerのProblem 85(日本語)です。 規則性を見出すことが、問題を解く一番の目的なんでしょうけど、「Project Euler Problem 85 - 眠いのです」を参考にさせていただきました。 085.rb
Project EulerのProblem 84(日本語)です。 Monopoly(モノポリー)というゲームの名前は聞いたことがありますが、やったことがないのでゲームの内容を理解するのに手間取りました(ひょっとしたら間違って解釈しているかもしれません)。数学を駆使して解答を導…
Project EulerのProblem 83(日本語)です。 Problem 81, Problem 82同様、2次元配列$memoに、それぞれのセルまでの和の最小値を格納するようにしています。 最初、再帰を使って解いてみましたが、5x5の例題では解けるものの、80x80だとstack level too deep (…
