サクサク読めて、アプリ限定の機能も多数！
トップへ戻る
アメリカ大統領選
inamori.hateblo.jp
Problem 468の計算量を見積もるときにこんな問題が思い浮かびました。 N以下を素因数分解したとき、素因数の個数の平均は？ 例えば、2、3、4 = 22、5なら1個、6 = 2 * 3なら2個とします。logNよりはずっと小さいと思われます。とりあえずコードを書いて調べてみましょう。 from itertools import * def div_pow(n, d): e = 0 while n % d == 0: e += 1 n /= d return e, n def make_factors_table(N): a = range(N + 1) for p in takewhile(lambda p: p * p <= N, (n for n in count(2) if a[n] == n)): for m in xrange(p, N + 1, p): if a[m] =
Pythonでは整数は大きくなると勝手に多倍長整数として表すので誤差は出ませんが、浮動小数点数を介すると途端に誤差が発生します。Project Eulerで特に問題になるのは、整数の平方根の計算です。すなわち、 ⌊√n⌋ の計算です。この計算は整数nを浮動小数点数に変換して平方根の計算をします。浮動小数点数は15桁くらい精度があるため、それくらいまでの大きさの整数なら、 int(sqrt(n)) で正確な計算をしてくれます。しかし、それより大きい整数だとそうもいきません。例えば、1234567892098765184は19桁の整数ですが、 n = 1234567892098765184 m = int(sqrt(n)) print m ** 2 - n # 265 とmは√nより大きくなってしまいます。これは、整数1234567892098765184は浮動小数点数化すると精度が足りず、1
Problem 389 これは確率計算をする問題なので、いつものように母関数の計算をすることになります。しかし、多項式をリストとして計算すると、Pythonは非常に遅いんですよね。そんなとき、NumPyを使うと劇的に速くなります。 ダウンロードはこのあたりから。 http://sourceforge.net/projects/numpy/files/ リファレンス http://docs.scipy.org/doc/numpy/reference/generated/numpy.poly1d.html まずは簡単な例から。 import numpy f = numpy.poly1d([3, 2, 1]) print f これを実行するとこう表示されます。 2 3 x + 2 x + 1x2 + 2x + 3ではないので注意です。 print f.c とすると、 [3 2 1]と表示されます
例えばProblem 60のような条件を満たす最小の解を求る問題を考えます。この問題は条件を満たすような解を小さい順に列挙するのが難しいです。しかし、上限を決めてその範囲で解が存在するかを含めて解くのは比較的簡単です。 このようなときは、適当に上限を決めるとよいです。例えば上限を1000と決めて、その範囲に解が無ければ、上限を2倍にして再び解を求めます。この方法は多くの場合にかなり有効です。上限を決めると問題がぐっと易しくなることはよくあります。また、直接解を求めるより時間がかかりそうですが、致命的にはかかりません。例えば、O(N)の問題のとき、解が8000で、いきなり上限を8000にして解を求めるたとき8秒かかったとします。ことのき、N = 1000から始めて倍々していくと、1 + 2 + 4 + 8 = 15秒かかります。まあ、倍くらいです。最悪の場合、N = 999から始めて倍々して
数学ガール/乱択アルゴリズム (数学ガールシリーズ 4) 作者: 結城浩出版社/メーカー: SBクリエイティブ発売日: 2011/02/26メディア: 単行本購入: 19人 クリック: 779回この商品を含むブログ (103件) を見る 買って通勤時に4日で読んだけど、とにかく重い。持ち運ぶときはそんなに感じなかったけど、持って読んでいるとすぐに腕が疲れてくる。だんだん分厚くなってきているよね。 アルゴリズム解析というと、前に古い本を読んだことがある。細かいところにこだわっているところが古さを感じさせるなあと思ったけど、少し触発されてここを何回通るかって数えたっけ。 この本の中でサイコロの目が6つとも出るまでにかかる回数の期待値を求める問題が出ていた。じゃあちょっと考えてみようかと思って本を閉じた瞬間に思いついた。こういう解き方だよね、ふつうは。でも高校生のときでは思いつかなかったよなあ。
Project Eulerを解いていくのに便利な数学の用語やアルゴリズムなどを紹介したものをまとめています。 ユークリッドの互除法 互いに素 エラトステネスのふるい 包除原理 ピタゴラス数 バイナリ法 漸化式 約数 多角数 完全数・友愛数・社交数 オイラーのφ関数 オイラーの定理 回文数 ペル方程式 連分数 ペル方程式（2） n^2+1型の素数の列挙 母関数 フィボナッチ数列 ガウス整数 マージ法 メモ化 上限が不明なときの問題解決法 上下で計算法を変える 分割数 約剰余類群 PriorityQueueの使い方 数値計算による誤差
母関数は数え上げや確率の問題で使います。Project Eulerではときどき使えるのでおぼえましょう。最近ではProblem 286で使いました。例えばこんな問題で使えます。 N個のブロックが横一列に並んでいます。赤・青・緑・黄の4色のペンキがあり、これらで各ブロックを塗っていきます。赤色で塗られたブロックの個数と、緑色で塗られたブロックの個数がともに偶数個となるような塗り方の総数を求め、10007で割った余りを出力しなさい。 プログラミングコンテストチャレンジブックP.182 この本の中では行列を使って解いていますが、母関数を使うとほとんどコーディングしなくてもよくなります。 まず、 (x + y + z + w)2 を考えます。xを赤、yを青、zを緑、wを黄とみなします。そうしてこれを展開することを考えます。 (x + y + z + w)2 = (x + y + z + w)(x
C++のstd::vectorにpush_backしていくと、ある領域を確保して、それを超えそうになったらまたある程度ゆとりのある領域を確保するという機構になっています。 ２倍だけじゃない - d.y.d. にまとめてありますが、std::vectorや類似するコンテナは2倍ずつ領域を大きくしていくのかと思いきや、1.5倍というのも多いんですね。実際にVC10 beta2で動かしてみると、 #include <iostream> #include <vector> int main() { std::vector<int> v; for(int i = 0; i < 100; i++) { const std::vector<int>::size_type old_cap = v.capacity(); v.push_back(i); const std::vector<int>::siz
https://projecteuler.net/problem=29 前回は例えば2乗までのとき何個がダブるかをナイーブに数えていましたが、2乗までなら2～N/2がダブると分かるので、数えるまでもありません。6乗までだと、N/6～N/3の間は2から5の倍数はダブりますが、重複を考えると包除原理を使わないといけません。しかし、前回よりかなり速いはずです。最後のところで多倍長整数を使うとより大きいときも計算できます。でも30秒程度でした。実際のところ、が素数でないと速いです。 from collections import Dict from math import min, max, abs import sys #################### library #################### fn gcd(n: Int, m: Int) -> Int: return n
このページを最初にブックマークしてみませんか？
『inamori’s diary』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
