2011-02-01から1ヶ月間の記事一覧
例えばこんなバッチファイルがあるとします。 @echo off setlocal set /a s = 0 for /L %%i in (1, 1, 100000) do ( set /a s += 1 ) echo %s% forループが時間がかかるので、この処理を行っている隙に echo %s% の部分を echo %s%a と変えて保存すると、 10…
http://projecteuler.net/index.php?section=problems&id=326 朝起きてちらっと問題見たら19人。すぐにでかけて帰ってきたら30人。雲をつかむような問題だと思ったが、またすぐにでかけたときに計算してみたらaの正体はわかった。そうするとあとは割と簡単だ…
Problem 20 4桁ずつ区切った長整数で計算しました。各桁の和だけでなく、100!そのものも出してみました。
Problem 19 この問題は月の日数が必要ですが、 call :set_v m 31 28 31 30 31 30 31 31 30 31 30 31 として、%m1%などとして取り出します。 本当は、1年の初めの曜日とうるう年かをキーにしてメモ化すればよいですが、 そこまでする必要もないでしょう。
http://projecteuler.net/index.php?section=problems&id=325 やっと正しい答えが出た。27着? これはProject Euler史上最も美しい問題だと思う。
http://projecteuler.net/index.php?section=problems&id=325 今朝電車に乗っているときにひらめいた。 無理数と有理数の神秘的な関係。 これでいけると思うのだが、書いてみたら正しい答えが出ない。単なるバグだと思う。
http://projecteuler.net/index.php?section=problems&id=325 もうすぐ24時間経とうとするが、まだ13人。 たぶんこの問題は、 ユークリッドの互除法 ⇔ 黄金比 ⇔ フィボナッチ数列 ということなんじゃないかと思うんだけど、解けそうで解けない。明日もう一度…
http://projecteuler.net/index.php?section=problems&id=325 S(10)すら正しい答えが出ない。 より地道な方法でも同じ答えになった。 試しにS(10000)を計算したら、上3桁まではあっていた。 あ、よく見たらまた不等号を見間違えていただけだった。 法則はわ…
よく知られた方法に行列の片方を転置して掛け合わせるという方法があります。 通常のように AikBkj としてkで回すと、Bのほうは飛び飛びのアドレスを見ることになり、キャッシュのヒットミスが起こりやすくなります。わざわざ転置してから、 AikBjk とすると…
Problem 18 この問題も、 call :set_v v 19 01 23 75 03 34 というように配列を初期化します。 この問題はメモ化を使えば速いのですが、ここでは全探索することが求められています。全探索は再帰を使えば簡単に可能です。
Problem 17 1ならoneなので長さ3、2ならtwoなので長さ3、3ならthreeなので長さ5などというのを連想配列にしておきたいところです。Pythonなら、 L = { 1: 3, 2: 3, 3: 5, ... } などとします。しかし、これだとすぐにバグが発生しそうです。そこで、 s = { 1…
http://projecteuler.net/index.php?section=problems&id=324 f(2)を出すのに30分かかった。今日はあきらめたほうがよさそう。 f(4)が26秒。やっぱ明日以降だな。
Problem 16 べき乗を求める計算なので、バイナリ法を使いましょう。それには多倍長整数の乗算が必要です。4桁ごとに区切って計算すれば比較的やさしいでしょう。乗算するたびに10000で割って次の4桁に加算しています。バイナリ法は再帰を使っていますが、配…
Problem 16 21000を求めます。多倍長整数なので、計算が少し大変です。加算なら簡単です。1 + 1 = 2、2 + 2 = 4、4 + 4と計算していけば、1000回加算するだけです。加算は8桁ごとに区切って配列にしています。
Problem 15 40C20を求めるだけの問題ですが、答えが32ビットを超えるから問題になるのです。 ここではパスカルの三角形を使います。そうすると加算だけで答えが求められます。10進で8桁ずつに区切って配列にして計算すればよいでしょう。
Problem 14 コラッツに戻りましょう。この問題も1に辿りつくまでに何回同じ操作を繰り返せばよいかわかりません。以下では、70回繰り返して、その間に1に辿りつかなかったらまた70回繰り返す、というフローにしています。 また、6の倍数で場合わけをしていま…
powを書いてみましょう。まずバイナリ法をgotoを使って書きます。 @echo off call :pow 2 1024 3 exit /b 0 :pow setlocal set /a m = 1 set /a p = %1 set /a e = %2 :loop_pow if %e% == 0 exit /b %m% set /a r = %e% %% 2 if !r! == 1 set /a m = %m% * …
http://projecteuler.net/index.php?section=problems&id=323 できた、と思ったらはねられた。もう15人できている。 1違っただけだった。20秒ほど間に合わなかった。全然難しいこと考えなくてもよかった。
http://projecteuler.net/index.php?section=problems&id=322 なんとかできた。1時間かかった。速くできそうだけど、余裕があれば。
遅延展開 絶望的に遅い状況をどうしたらよいでしょう。ふつうはforの中では変えた変数の値を使えないのですが、実はおまじないでこれができるようになるのです。例えばこれは恐らく意図通りに動きません。 set /a s = 0 for /L %%k in (1, 1, 10) do ( set /…
Problem 14 コラッツは、再帰+メモ化で速く美しく解くことができます。 def Collatz(n): if n < N: if a[n] > 0: return a[n] m = n if m % 2 == 0: m /= 2 else: m = m * 3 + 1 l = Collatz(m) + 1 if n < N: a[n] = l return l N = 10 ** 6 a = [ 0 ] * N…
http://projecteuler.net/index.php?section=problems&id=322 もっと原始的な方法で4時間かけて計算させても1違う。 今見直してみたら、<になっている。何度も見直したつもりだったけど。
http://projecteuler.net/index.php?section=problems&id=322 なかなかコーディングする時間が取れないので、電車の中だけでも考えていたら、少しずつわかってきた。それで素直に組んでみたら、例の値が1違い。なぜそうなるのかわからない。