時間計測 %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 +…

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桁になってオーバ…

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は関数を呼んだ…

関数 前回、Problem 1を解きましたが、その際3と5と15で同じ処理を繰り返していましたね。こういうときに関数を使いたくなるのがプログラマです。 まず簡単な、整数を引数にして5倍する関数を例にしましょう。 @echo off call :five_times 3 echo %ERRORLEVE…

最近、バッチファイルでコーディングする機会があって、バッチファイルでもがんばれば意外とできるのではと思ったので、Project Eulerを解いてみることにしました。 バッチファイルについては、最初はバッチメモを参考にしました。あとは、コマンドラインでs…

最初に戻って、素数のガウス整数の素因数を格納するときに、2つ配列を作ってそれぞれに実部と虚部を格納していましたが、よく考えるとそれぞれは10000以下なので、16ビットごとにそれを格納して一つの整数にすればよいですね。 そうすると、それでも250MBく…

5の約数は、1, 2 + i, 2 - i, 5ですが、整数は足して考えてもよいです。ai + bii(ai ≥ bi ≥ 0)に対して1と5を掛けると、ai + bii, 5ai + 5biiとなり、90度回転したbi - aii, 5bi - 5aiiと実部の和を取ると、6ai + 6biとなり、最初から6としたときと同じにな…

例えば、5の実部が正の約数は、 1, 2 + i, 1 - 2i, 2 - i, 1 + 2i, 5 ですが、15の約数は、5の約数とそれを3倍したものになります。すなわち、s(15) = 4s(15)となります。105なら、s(105) = (1 + 3 + 7 + 21)s(5)となります。 ガウス整数の約数を計算しなけ…

素因数分解をするのではなく、素数の積を生成するのと同じ方法で約数の組を作っていきます。最も素直に書いてみました。 しかし、やっぱり遅いですね。

素因数分解ができればガウス整数での約数の和が求められるようにしましょう。 まず、素数のべき乗について考えます。例えば、3はガウス整数でも素数なので9なら約数は(1, 3, 9)です。一般に4の剰余が3なら同じようになります。 5 = (2 + i)(2 - i)なので、5e…

この問題はメモリを多く使えば簡単のようですが、いつもやっているように300MBを目標にしてPythonでなるべく速くなるようにします。ガウス整数の範囲で約数の和を求めるということなので、素因数分解ができれば約数は簡単に求められるでしょう。ガウス整数の…

ガウス整数は、a, bを整数としたとき、a + ibと表せる数を言います。 ガウス整数は、素因数分解の一意性があります。例えば5なら、 5 = (2 + i)(2 - i) と一意に分解できます。ただし、-1、±iを掛けた数は同じ因数とみなします。すなわち、 5 = (-1 + 2i)(-1…

メモ化（memoize）は、Project Eulerで何問かに1問必ず使う手法なので、絶対に覚えましょう。 Project EulerのProblem 151を考えます。意味が分かりにくい問題ですが、分かれば簡単です。まず最初にA1の紙が1枚封筒に入った状態を考えます。この状態を (1, 0…

マージ法（Merge algorithm）は、ソートされた二つの列を合体して一つのソートされた列を作るアルゴリズムです。 原理は非常に簡単です。例えば次のような列があったとして、 2 4 6 8 ... 3 6 9 12 ... まず、両方の列の先頭を比較します。小さいほうの2を取…

フィボナッチ数列Fnは次のように定義されます。 F1 = 1 F2 = 1 Fn+2 = Fn+1 + Fn F2 = 2とする流儀もあるようです。 フィボナッチ数列はいろいろなところに出てくるためか、Project Eulerでもしばしば取り上げられます。フィボナッチ数列をPythonで生成する…

母関数は数え上げや確率の問題で使います。Project Eulerではときどき使えるのでおぼえましょう。最近ではProblem 286で使いました。例えばこんな問題で使えます。 N個のブロックが横一列に並んでいます。赤・青・緑・黄の4色のペンキがあり、これらで各ブロ…

http://projecteuler.net/index.php?section=problems&id=150 Pythonってこういう書き方ができたんですね。知らなかった。 for (i, j), s in izip(gen_index(N), gen_pseudo_random()): これとの連想で、ラムダでもこういう書き方ができます。 lambda (i, j)…

http://projecteuler.net/index.php?section=problems&id=149 よく考えたら、これって左から順に考えたほうが簡単ですね。そうすると、全体の和、最大の和、右端を含む最大の和の3つを考えれば済みます。こうするとコードがすっきりした上、46秒でした。再帰…