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

Mae向きなブログ

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

Euler

Problem 93

Project EulerのProblem 93(日本語)です。 1〜9から4つの数字の組合せを作り、以下の計算を逆ポーランド記法により求めています。 [tex:*1] [tex:*2 \diamond d)] [tex:(a \diamond *3] 解答後、フォーラムを見て気付いたのですが、逆ポーランド記法を使わず…

Problem 90

Project EulerのProblem 90(日本語)です。 題意(6と9の扱い)を読み取るのに苦労しました…。 090.rb

Problem 91

Project EulerのProblem 91(日本語)です。 今まで解いたProject Eulerの問題は、問題文中に示されている例だと解けるが、探索空間が大きくなると、とても短時間に解けないという特徴があったと思います。この問題は珍しく工夫をしなくてもそれなりの時間に解…

Problem 92

Project EulerのProblem 92(日本語)です。 各数の列を求め89になる個数を数えているだけのシンプルな方法で解いています。同じ数の再計算のないよう一度計算した数値についてはメモをしています。 092.rb

Problem 89

Project EulerのProblem 89(日本語)です。 引き算ペアの文字列の置換だけで正解でした。これだと16がVVVIと書かれていてもXVIと1文字節約できない。roman.txtに含まれる1000個のローマ記法の質があまりよくないのかなと思います。 089.rb

Problem 87

Project EulerのProblem 87(日本語)です。 2乗しても50,000,000を超えない素数のリスト、他、同様に3乗、4乗用のリストをまず作成して、工夫もなく総当たりして解きました。 087.rb

Problem 86

Project EulerのProblem 86(日本語)です。 前回といい今回といい苦戦しています。 「Project Euler Problem #86 « KeyZero Conversation」を参考にさせていただきました。 086.rb

Problem 85

Project EulerのProblem 85(日本語)です。 規則性を見出すことが、問題を解く一番の目的なんでしょうけど、「Project Euler Problem 85 - 眠いのです」を参考にさせていただきました。 085.rb

Problem 84

Project EulerのProblem 84(日本語)です。 Monopoly(モノポリー)というゲームの名前は聞いたことがありますが、やったことがないのでゲームの内容を理解するのに手間取りました(ひょっとしたら間違って解釈しているかもしれません)。数学を駆使して解答を導…

Problem 83

Project EulerのProblem 83(日本語)です。 Problem 81, Problem 82同様、2次元配列$memoに、それぞれのセルまでの和の最小値を格納するようにしています。 最初、再帰を使って解いてみましたが、5x5の例題では解けるものの、80x80だとstack level too deep (…

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

Problem 51

Project EulerのProblem 51(日本語)です。 いろいろ考えてみましたが、全くよい解法を見出すことができず、「Y箱: Euler : Problem 51」を参考にさせていただきました。 051.rb

Problem 50

Project EulerのProblem 50(日本語)です。 例えば、以下の例で考えると、 prime_list = [2, 3, 5, 7, 11, 13, 17, 19] i = 0 # 配列の左端を初期値 j = 7 # 配列の右端を初期値jを減らしていき,初めてsum(prime_list[i]〜prime_list[j]までの和)が素数にな…

Problem 49

Project EulerのProblem 49(日本語)です。 等差数列の候補を変数first, second, thirdで表しています。firstの各桁を入れ替えたもの(second)が素数であるか調べ、もし素数なら、公差second - firstからthirdを生成し、素数かどうかを判定しています。 049.rb

Problem 48

Project EulerのProblem 48(日本語)です。 とても大きな数を扱うことになると思うので、以下で解けなかったら工夫しようと思いましたが計算してくれました。 048.rb

Problem 47

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

Problem 46

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

Problem 45

Project EulerのProblem 45(日本語)です。 Fiberを使って、三角数、五角数、六角数の数列を生成しています。三者が揃うまで、一番歩みの遅い数列を一歩ずつ前に進めていくことを繰り返しています。 045.rb

Problem 44

Project EulerのProblem 44(日本語)です。 ある数が五角数かどうかをpentagonal_number?メソッドで判別式を用いて判定しています。このとき、式(1),(3)ではOKですが、式(2)だとNGです。なぜ、式(2)だとうまく判定できないのでしょう? 1/2=0ですね。初歩的な…

Problem 43

Project EulerのProblem 43(日本語)です。 力づくの方法で解いています。 043.rb

Problem 42

Project EulerのProblem 42(日本語)です。単語の値をsumとすると、解の公式より と書ける。このとき、平方根を開いた数が整数であり、かつ、1+8*sumが奇数なら三角語と判定。 042.rb