Mae向きなブログ

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

Euler

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 …