Problem 20 4桁ずつ区切った長整数で計算しました。各桁の和だけでなく、100!そのものも出してみました。

Problem 19 この問題は月の日数が必要ですが、 call :set_v m 31 28 31 30 31 30 31 31 30 31 30 31 として、%m1%などとして取り出します。 本当は、1年の初めの曜日とうるう年かをキーにしてメモ化すればよいですが、 そこまでする必要もないでしょう。

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…

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% * …

遅延展開 絶望的に遅い状況をどうしたらよいでしょう。ふつうは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…

Problem 14 コラッツです。単純に最初から順に長さを計算すると、3日くらいかかりそうです。

Problem 13 8桁ずつ区切って計算します。足し算なので簡単ですね。

Problem 12 エラトステネスのふるいのように約数の個数を求めるとさらに速くなります。ここの下のほうで説明した方法とだいたい同じです。ただし、下の段には素因数分解を記憶しておくのではなく、約数の個数を記憶しておきます。具体的には、まず1を代入し…

Problem 12 1 2 3 4 5 6 …の偶数を2で割って、 1 1 3 2 5 3 …隣同士を掛け合わせると、 1 3 6 10 15 …これは三角数の列になっています。2番目の列の約数の数を求めると、 1 1 2 2 2 2 …隣同士を掛け合わせて、 1 2 4 4 4 …これが対応する三角数の約数の数に…

Problem 12 三角数をふつうに素因数分解していたのでは間に合いません。

Problem 11 スペースで区切るコードを書きましょう。頭から見ていってスペースがあったら配列に登録するだけです。 rem // 引数は 文字列 配列変数 バッファ :split if %1 == "" ( call :push %2 %3 exit /b 0 ) set s=%~1 set c=%s:~0,1% if "%c%" == " " (…

Problem 11 与えられたデータをテキストファイルにしてそれを読みましょう。 @echo off for /F %%s in (%1) do echo %%s 08 49 81 …実は、%%sには1行そのままではなくスペースとタブで区切られた最初のトークンが格納されます。文字列全体を格納するにはオプ…

べき乗は、ふつうはバイナリ法を使うと速くなるのですが、バッチファイルの場合は事情が変わってきます。バッチファイルではforループが相対的に速いため単純に一つずつ掛けていくのが速くなりやすいのです。 @echo off set /a N = 100 set /a e = 128 call …

Problem 10 Miller-Rabin法を実装してみましたが、さらに時間がかかりました。しかも自乗でオーバーフローする問題に対処できていません。

Problem 10 Problem 7と同じように部分的にエラトステネスのふるいを行います。 しかし、2時間もかかってしまいました。この連載ではなるべくなら1時間以内で答えを出したいところなのです。

Problem 9 この問題は、実は手計算レベルです。直角三角形の辺の長さは表すと、 a = l(m2 - n2) b = 2lmn c = l(m2 + n2) 0 < n < m m + nは奇数 mとnは互いに素。 このとき周の長さは、 a + b + c = 2lm(m + n) よって、mとm + nは500の約数で互いに素。と…

Problem 8 数字の並びはテキストファイルにしておきます。実はバッチファイルはテキストファイルを読めるのです。 @echo off for /F %%s in (%1) do echo %%s これでテキストファイルを表示できます。これは1行ずつ読んでそれをスペースとタブで区切った最初…

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,…

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…

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

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