2009-10-01から1ヶ月間の記事一覧
膝を痛めているので、左のグラフにもあるように、9日ぶりにまともに走った。 意外と軽快に走れた。 1km 4:35.18 1km 4:31.60 1km 4:35.51 1km 4:34.83 1km 4:35.30 - 5km 22:52.42酸素欠乏症で気分が悪くなった。 明日は練習のつもりでゆっくり走ろうと思う。
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=262 そんなに難しい問題ではないと思うけど。 まず、Excelで3-Dグラフを描こうとしたが、どうやって描けばいいか忘れていた。ヘルプを見ても分からないので検索した。 それを見…
あまり速くならない。なぜこのコードでこんなに時間がかかるのか。未だにPythonはどこがネックになるのかわからない。 この問題は、 xy2 = (x + 1)z2 + x(x + 1) という形に帰着する。 s = y / (x + 1) t = z / x とおくと、 (x + 1)s2 = xt2 + 1 xを固定す…
Problem 9 ピタゴラス数は、a < b < cで、a2 + b2 = c2を満たす3つの自然数の組である。 (略)a + b + c = 1000を満たすピタゴラス数は唯一つ存在する。このときのabcを求めよ。 http://projecteuler.net/index.php?section=problems&id=9 もっとも素直に書…
よく知られているように、直角三角形の斜辺の長さをc、他の2辺の長さをa、bとすると、 a2 + b2 = c2 これがピタゴラスの定理です。 この辺の長さが自然数のとき、辺の長さの組をピタゴラス数(Pythagorean triple)と呼びます。また、辺の長さが互いに素であ…
Project Eulerの問題は、反対側から解いたほうがよいことが多いです。この問題は「3桁の整数同士の積で最も大きい回文数を求めよ」ですが、これを「回文数で3桁の整数同士の積になる最も大きいものを求めよ」と読み替えます。そうすると、大きな回文数から順…
Problem 4 回文数はどちらから読んでも同じ数のことである。2桁の数字同士の積で最も大きい回文数は、9009 = 91 × 99。 3桁の整数同士の積で最も大きい回文数を求めよ。 http://projecteuler.net/index.php?section=problems&id=4 回文数の判定は、1桁ごとに…
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=261 大変だった。ノートを6ページも使った。 いろいろ式をいじくりまわして、ペル方程式に似た式に辿りついた。しかし、これをどう解いていいか最初分からなかった。結局、ペル…
元の問題を一般的に、 nと互いに素でないm未満の自然数で総和を求めよ。 としましょう。例えば、nを60とすると、 60 = 22 • 3 • 5 なので、2または3または5の倍数の総和を求めればよいことになります。これを求めるには、まず2の倍数の総和と3の倍数の総和と…
Project Eulerは、毎週末に1問プログラミングの問題が出題され、世界中でひそかにそれを早く解く競争が行われているサイトです。このサイトの問題を最初から解いていくと、自然にプログラミングや数学(主に数論)の力がついていきます。ここではProject Eul…
100未満の自然数を考えます。2の倍数または3の倍数の個数を数えるとします。2の倍数は49個、3の倍数は33個あります。これをあわせると82個になりますが、16個ある6の倍数を重複して数えているので、これを82から差し引いて、66個となります。 S を集合Sの要…
世の中にはすごい人がいて、私が七転八倒しながらProject Eulerの問題を解いている一方、易々と華麗に解いている人もいる。 さて、Project Euler 258は、以前書いたように大きな整数の掛け算の速度が問題になる。よく知られているようにFFTを用いると高速に…
http://www.kamoshika-marathon.com/result.html31秒差か。
エラトステネスのふるい(Sieve of Eratosthenes)は、決められた範囲内の素数を全て求めるためのアルゴリズムです。 1〜nの範囲の素数を求めたい場合、まず適当な方法でn1/2までの素数を求めておきます。これらの素数もふるいにかけながら求める方法もあり…
今シーズン初のロードレース。なのだが、木曜の練習のダメージが大きかったらしく、昨日の朝5km走ったら、どうも膝に違和感が。最後に3本流しを入れようと思っていたのに、それどころか失速。今日もレース前まで違和感が。本当に走れるんだろうか。会場まで2…
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=260 最初、石をどう取ってもloseにならないものをloseと考えたが、逆にloseに石を追加したものをwinとすればよいとわかった。 メモリが足りないのでちょっと工夫した。ただし遅…
互いに素(coprime)とは、与えられた2つの整数が共通の素因数を持たないことを意味します。 例えば、4と6なら、 4 = 22 6 = 2•3 だから、2が共通の素因数となり、互いに素ではありません。12と25なら、 12 = 22•3 25 = 52 だから、互いに素です。 プログラ…
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=74 この問題もちゃんと考えると面白い。 これも以前解いたときは、題意をそのままコードにしただけだった。 from math import factorialdef next(n): s = 0 while n: m = n % 1…
1000mを8本、なるべく4:30以上かからないように。ヤッソ800よりはきついはず。 4本目でバテて、後半は力を溜めることだけ考えた。だいぶ楽をした。 2000 10:32.02 1000 4:24.87 400 2:17.11 1000 4:22.66 400 2:23.68 1000 4:17.39 400 2:18.02 1000 4:18.28…
ユークリッドの互除法(Euclidean algorithm)は、最大公約数を求めるためのアルゴリズムです。 割り切れるまで割り算を繰り返します。例えば、234と177の最大公約数を求めるには、 234 ÷ 177 = 1 余り 57 177 ÷ 57 = 3 余り 6 57 ÷ 6 = 9 余り 3 6 ÷ 3 = 2 …
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=73 前にこの問題を解いた頃は、解ければいいや、ということでずいぶん雑にコードを書いていた。この日は9問解いたようだ。 とにかく何の工夫もなくしらみつぶしに調べていた。 …
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=257 解けないなあと思って久しぶりに問題文を見たら、条件を見落としていることに気がついた。 a ≤ b ≤ c これだと、 (s-b)(s-c) = nbc s = a + b + c で、nは4以下。4なら正三…
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=259 今度は小町算か。 (正確には100になるのを小町算というらしいが、気にしない) この問題は一瞬で解法を思いついた。再帰で解けばいいだけ。たぶん、過去100問で一番易しい…
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=258 この問題では、結局2000項の多項式の掛け算に時間がかかる。単純に計算すると、N=2000として、N2回の掛け算が必要となる。実際には自乗の計算なので半分くらいで済む。しか…
プロジェクトオイラー http://projecteuler.net/index.php?section=problems&id=258 大きな項数の問題なので、最初は周期を求めるのかと思った。ふつうに考えれば周期は非常に長いので、特殊な状態なのかと思った。 しかし、多項式であると考えれば簡単。直…