Problem 7 配列もどきを使うにしても、大きな配列は使えないことがわかりました。 そこでエラトステネスのふるいを小さな範囲で行い、それを繰り返すようにします。それ以前に必要な範囲の素数はこれまたエラトステネスのふるいよって求めておきます。これで…

試行錯誤していると、環境変数が多いと遅くなることがわかりました。 まず、指定した数だけ配列もどきの変数を生成し、そのあとに単純な和を取る処理にかかる時間を計測しました。 変数の数 処理時間 10 11.38s 100 12.03s 1000 15.95s 3000 26.00s 10000 61…

Problem 7 この問題は、10001番目の素数を求めるというのがミソです。だからエラトステネスのふるいをいくつまですればいいのかわかりません。ここは手抜きをします。N = 10001として、N log2 Nまでふるいにかけることにします。ちょっと大きめですが、これ…

Problem 7 配列？ 素数を求めるといえば、ふつうはエラトステネスのふるいですね。それには配列を使わなければなりません。しかし、バッチファイルに配列はありません。ではどうすればよいでしょう。こんなのはどうでしょうか。 @echo off for /L %%i in (1,…

http://projecteuler.net/index.php?section=problems&id=316 いちおうできたけど、遅い。 うまくメモ化できない。

http://projecteuler.net/index.php?section=problems&id=316 非常に地道にコードを書いたら簡単に27280188が出た。でも遅い。 メモ化して200秒になったが、答えがあっていないらしい。

http://projecteuler.net/index.php?section=problems&id=316 昼ごろからg(535)を計算していたが、いっこうに1008になりそうにない。しかたなくジョギングに出かけて考えていたが、やっぱりならない。帰って疑似乱数を使って計算してみると、そんな感じの数…

Problem 7素数の判定を再帰にするとさすがに遅いのでループにします。 :is_prime setlocal set /a n = %1 set /a k = 2 :loop_is_prime set /a k_sq = %k% * %k% if %k_sq% GTR %n% exit /b 1 set /a r = %n% %% %k% if %r% == 0 exit /b 0 set /a k += 1 go…

http://projecteuler.net/index.php?section=problems&id=316 これは、夜も遅いし諦めたほうがいいかな？ 風呂入って考えたらだんだんわかってきた。でも、これからすぐに解けるとは思えないので、明日ゆっくり考える。できればジョギングしながら考えたいが…

Problem 7難しい問題が来ました。 一つずつ素数かどうかチェックしていればとても間に合わないでしょう。

時間計測できるようになったので、ベンチマークしてみましょう。1〜1000の和を4つの方法で求めます。それぞれ、for、goto、for+callで回したもの、そして再帰を使ったものです。 500500 for : .07s 500500 goto : 1.57s 500500 for+call : 1.38s 500500 recu…

時間計測 %TIME%という特殊な環境変数があり、ここには現在の時刻が格納されています。 echo %TIME% 12:09:22.90なので、この文字列を区切って時・分・秒にすればよいです。 しかし、この分を次のように取ると、 set t=%TIME% set /a m = %t:~3,2% 無効な数…

Problem 6 高階関数？ Pythonだとこんな感じに書けます。 from itertools import imap N = 100 s = sum(xrange(1, N + 1)) s2 = sum(imap(lambda n: n * n, xrange(1, N + 1))) print s * s - s2 sumはreduceを使えば、 N = 100 s = reduce(lambda x, y: x +…

http://projecteuler.net/index.php?section=problems&id=315 1ステップで100未満になるので、100未満をメモ化した。それでも1分切らない。エラトステネスのふるいが遅い。これを速くして41秒。

http://projecteuler.net/index.php?section=problems&id=315 たぶん、なんの変哲もない問題だと思うが。 解けた。実行時間2分。 20着より5分遅かった。やっぱ頭が鈍っている。

Problem 6答えを出すだけなら和の公式で終わりですね。 @echo off set /a N = 100 set /a s = %N% * (%N% + 1) / 2 set /a s2 = %N% * (%N% + 1) * (%N% * 2 + 1) / 6 set /a result = %s% * %s% - %s2% echo %result% forで回すなら、 @echo off set /a N =…

Problem 5最小公倍数を求めるだけです。 最小公倍数は最大公約数がわかれば求まります。最大公約数は再帰で簡単に求まります。

Problem 4この手の問題は、回文数であるかを判定するのではなく、回文数を生成するのが定番です。回文数を生成するには、例えば987なら反転して789にして結合して987789とします。まず、反転です。 :reverse setlocal if %1 == 0 exit /b %2 set /a d = %1 %…

Problem 4まず、ある自然数が3桁の自然数同士の積になっているかどうかを調べるコードを書きましょう。999から降順に割っていって、割り切れたら積になっています。割り算の結果が自分以上になったら積がないことになります。 :is_product setlocal set /a d…

Problem 3長整数の掛け算は4桁ずつにわければ簡単です。しかし割り算は難しいです。ここでは手抜きしています。除数は32ビットの整数を使って、被除数を4桁に分けています。しかし、除数は最大6桁で、余りも最大6桁になるので1万倍したら10桁になってオーバ…

http://projecteuler.net/index.php?section=problems&id=314 問題文が長い。意味を理解するのに8分。今までにないタイプの問題だ。ちょっと買い物にでかけて考えるかな。 25分くらい買い物行ってきたけど、あまり思いつかなかった。 やっと125が出た。この…

Problem 3早くも難問がやってきました。これは12桁で32ビットで表せないので難しいです。この問題が解ければいいというものでもありません。ある程度は一般化したいところです。ここでは、12桁までの場合になるべく解けるようにします。 まずはPythonで書い…

複合代入演算子 こんな感じの演算子です。 set /a n += 1 nという変数に1を加えています。しかし、 @echo off set /a n = 1 setlocal set /a n += 1 echo %n% endlocal echo %n% 2 1やっぱり。

Problem 2は簡単です。フィボナッチ数列は再帰で生成できます。 @echo off set /a N = 4000000 call :Fibonacci 0 1 echo %ERRORLEVEL% exit /b 0 :Fibonacci setlocal set /a f = %1 + %2 if %f% GTR %N% exit /b 0 call :Fibonacci %2 %f% set /a r = %f% …

http://twitter.com/cddddr/status/12632522261266432このあたりについては前から何度か考えていて、例えばProject Euler 110（1）にも書いているが、なかなか難しい。 バッチファイルのほうはProblem 11まで書けたので、また考えてみたいと思う。もっともバ…

再帰 変数がローカルでなかったり、gotoが使われているのが気に入らない場合は、やっぱり再帰でしょうね。よくある階乗の例を見てみましょう。 @echo off call :factorial %1 echo %ERRORLEVEL% exit /b 0 :factorial setlocal if %1 == 0 exit /b 1 set /a …

即時変数展開 forとifが使えるようになったので、Problem 1を題意どおりに書くことができます。ただし、バッチファイルにはandやorはないので、そこはifを2つ使うことになります。 @echo off set /a N = 1000 set /a M = %N% - 1 set /a s = 0 for /L %%i in…

forコマンド この問題は和の公式を使ってもいいのですが、使わないのがふつうの解き方のようです。さいわいforコマンドがあるので、それで回すことができます。forにはいろいろパターンがありますが、/Lを指定すると変数を変化させることができます。 @echo …

setlocalコマンド setlocalはendlocalまたはexitが呼ばれるまで有効です。 @echo off set /a n = 1 setlocal set /a n = 2 setlocal set /a n = 3 echo %n% endlocal echo %n% endlocal echo %n% 3 2 1気をつけなければいけないのは、setlocalは関数を呼んだ…

http://projecteuler.net/index.php?section=problems&id=313 やっと出来た。2秒。なんだろうね、簡単な問題のはずなのに。