Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

Euler

Problem 82

Project EulerのProblem 82(日本語)です。 Problem 81同様、2次元配列$memoに、それぞれのセルまでの和の最小値を格納するようにしています。本問では上下右に移動できるので、例えば、問題文で説明されている5x5の例で考えると、 $memo[1][1]には、 131 + 6…

Problem 81

Project EulerのProblem 81(日本語)です。 2次元配列$memoに、それぞれのセルまでの和の最小値を格納するようにしています。格納する際、上のセルからの和と左からの和のうち小さい方を格納していけば、2次元配列$memoの右下に解が求まることになります。 08…

Problem 80

Project EulerのProblem 80(日本語)です。 最初、module function BigMath.#sqrtを使ってできないかと考えたのですが、計算結果の精度が52位が限界なのでしょうか、計算できなかったので、開平法を使って計算しました。動くことを最優先して作ったので、とて…

Problem 79

Project EulerのProblem 79(日本語)です。 実は手計算で答えを求めて、Answer と Confirmation Code を入力して check ボタンを押してみると正解でした。それで終わってもよかったのですが、tsortライブラリを使って解いてみました。 079.rb

Problem 78

Project EulerのProblem 78(日本語)です。 6/5(火)のProblem 76のような解き方だと時間がかかりすぎて解くことができませんでした。Wikipediaの分割数には、以下のような漸化式も紹介されています。以前、Problem 44,Problem 45で出てきた五角数が分割数を解…

Problem 77

Project EulerのProblem 77(日本語)です。 6/5(火)のProblem 76を少し変更することで解くことができました。 077.rb

Problem 76

Project EulerのProblem 76(日本語)です。 076.rb 分割数の問題でした。分割数については『数学ガール (数学ガールシリーズ 1)』で学習していたので、問題を読んだときにすぐにそれと気付きました。第10章では上界の一つが紹介され、エピローグでは一般項を…

Problem 75

Project EulerのProblem 75(日本語)です。 075.rb 問題文を読んだとき、以前『数学ガール フェルマーの最終定理 (数学ガールシリーズ 2)』で学習した「原始ピタゴラス数の一般形」が頭に浮かびましたので利用してみました。 原始ピタゴラス数の一般形とは、 …

Problem 74

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

Problem 73

Project EulerのProblem 73(日本語)です。 073.rb Problem73もファレイ数列の問題でした。前回のブログには、 最近、大きい数を扱うときは、そのままの解き方では解けないということにようやく気づいてきたので作戦変更です。 と書いたのですが、「そのまま…

Problem 72

Project EulerのProblem 72(日本語)です。 072.rb 最初、Problem 71と同じような解き方で数を数えてみたのですが、さすがに1,000,000ともなると、stack level too deep (SystemStackError) が出ますね。最近、大きい数を扱うときは、そのままの解き方では解…

Problem 71

Project EulerのProblem 71(日本語)です。 071.rb ファレイ数列の問題でした。以前、結城浩さんの既約分数クイズで取り組んだことがあったので、すんなり解くことができました。2003年のことだったんですね…。

Problem 70

Project EulerのProblem 70(日本語)です。 070.rb 5/20に解いたProblem 69と似た問題でした。解き方についても悩んだのですが、一番、悩んだのは小数点演算です。実行すると9708131と出力されていたのですが、この間違いの原因を突きとめるにの多くの時間を…

Problem 66

Project EulerのProblem 66(日本語)です。 066.rb 例にあるの場合だと、単純な方法で解を求めることができるのですが、になると時間がかかりすぎて解くことができなくなります。 いろいろ調べてみるとProblem 64(昨日)とProblem 66は密接に関係しているんで…

Problem 64

Project EulerのProblem 64(日本語)です。 064.rb 連分数を求める部分をプログラムに落としこむことができなくて、後回ししていた問題です。自力で解けたと言いたいところですが、いい参考サイトを見つけることができたという表現の方が正しいです。 参考サ…

Problem 69

Project EulerのProblem 69(日本語)です。 069-1.rb 問題文を読んで、そのままプログラムにしたのが069-1.rbです。phi関数を作成し、ループを回していますが、実行してみると相当時間がかかります。あまりにも時間がかかりすぎるため、途中で実行を中止しま…

Problem 68

Project EulerのProblem 68(日本語)です。 何の工夫もなく全探索しているだけです。 068.rb

Problem 65

Project EulerのProblem 65(日本語)です。 $aryに最初の100項を格納し、solveメソッドを再帰的に呼びだして解いています。例えば、4項目を求めるときは、以下のように処理が進んでいきます。 $ary = [2, 1, 2, 1] pop => 1, pop => 2して、2 + 1/1 をpushす…

Problem 63

Project EulerのProblem 63(日本語)です。 の桁数とnが等しい数が何個あるかという問題ですが、だけ考えればよいので以下のように作りました*1。 Rubyの書き方についてですが、あらかじめ繰り返し回数がわからない場合、Rubyistはどう書くのでしょうか? loop…

Problem 62

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

Problem 61

Project EulerのProblem 61(日本語)です。 create_hash メソッドでは2つのことをやっています。 まずは、以下のようなhashを作ることです。2桁で始まる4桁の整数とその整数が何角数なのかという情報をもたせています。 {10=> [[1035, 3], [1081, 3], [1024, …

Problem 60

Project EulerのProblem 60(日本語)です。 最初、自分で作成したものだと、4つの素数の組の和は簡単に求められたのですが、5つだと求めることができませんでした。いろいろと調べたところ、Y箱: Euler : Problem 60で紹介されているアルゴリズムを参考に作…

Problem 59

Project EulerのProblem 59(日本語)です。 最初、頻度分析をやろうと思ったのですが、問題文中に 「平文はよく用いられる英単語を含んでいる」 とあること。また、 暗号化鍵は3文字の小文字である ので、すべての鍵の組合せを試しながら、theとthisが含まれ…

Problem 58

Project EulerのProblem 58(日本語)です。 Problem 28を少し修正して解きました。 058.rb

Problem 57

Project EulerのProblem 57(日本語)です。 以下のような漸化式を利用しました。 初項 = 3/2 次項 = 1 + 1/(1 + 前項) 057.rb

Problem 56

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

Problem 55

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

Problem 54

Project EulerのProblem 54(日本語)です。 難しい問題というよりも、ちょっと面倒な問題でした。2人のプレイヤーが同じ役の場合、 役を構成する中で値が最も大きいカードによってランクが決まる 一番値が大きいカードによってランクが決まる 一番値が大きい…

Problem 53

Project EulerのProblem 53(日本語)です。なので、が100万を超えたらカウンタ(cnt)を+2してますが、nが偶数で、かつ、のときは、カウンタを+1しています。 053.rb

Problem 52

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