http://projecteuler.net/index.php?section=problems&id=34これもProblem 30とほとんど同じです。 重複組合せを使う方法に対して、8倍くらい速かったです。

http://projecteuler.net/index.php?section=problems&id=30以前のと違う方法をふと思いついたので書きます。例えば、6桁として456789を考えます。 45 + 55 + 65 + 75 + 85 + 95 - 456789 が0ならいいわけです。ここで3桁ずつにわけて考えましょう。456000と…

Project Eulerのフォーラムは一定数投稿があると新規投稿を受け付けていなかったが、リニューアルで投稿できるようになった。人よりよい解法を持っていると思ったら投稿していきたい。よい投稿があると称号が得られるらしい。 以下は備忘録として記しておく…

フォーラムにアップした。基本的に、ScalaでProject Euler（57）の内容と同じ。英語はおかしいことは分かっているが勘弁してもらう。

どこが変わったのか、前に出ていた告知をざっと読んだだけであまり覚えていないけど、満杯だったフォーラムにも書き込めるようになったので、このブログの成果を少しずつ書き込んで行けたらなあと思う。英語書かなきゃいけないと思うと気が重いけど。 325問…

前に書いたものを少し書き直します。 マージ法（Merge algorithm）は、ソートされた二つの列を合体して一つのソートされた列を作るアルゴリズムです。（「マージ法」という用語はあまり使われていないようです） 原理は非常に簡単です。例えば次のような列が…

最後に今まで出てこなかったソートをやりたいと思います。 まず、選択ソートはforが使えるので書きやすく、意外と速いです。 それから、クイックソートです。クイックソートは再帰で書きますが、setlocalが使えないので変数を退避してくれません。退避しなけ…

Problem 30もうちょっと速くならないでしょうか。下の桁から考えて枝刈りすることを考えましょう。例えば、4乗で考えて632とすると、べき乗和は64+34+24=1393となります。元の数との差は761です。次に千の位に数字をつけます。例えば9なら元の数は9000増えて…

Problem 30この問題は、限界の大きさが簡単に求められるのであとはしらみつぶしです。ただ4乗で8分かかったので、5乗だと100分くらいかかりそうです。

Problem 29この問題は、本当は素因数分解などする必要はありません。99 * 99 = 9801通りの中で重複する数を削ればいいのです。重複するのは例えば、24 = 42です。このようになるのは、少なくとも片方が2乗以上のべき乗数です。このような数を指数ごとに数え…

Problem 29この問題は、なにも考えなければ、素因数分解して掛け算してsetに入れる、ですね。これをバッチファイルで実現しましょう。 例えば、24 = 23 * 3を次のように表すことにしましょう。 set f= 2 3 3 1 こうすると構造がシンプルで掛け算しやすいです…

Problem 28 オブジェクト指向？ この問題は、人が原点から歩くと考えると、数学を使わなくて済みます。これをPythonで考えると、こんなクラスを作りたくなります。 class cWalker: def __init__(self): self.x = 0 self.y = 0 self.v = 1 def value(self): r…

Problem 28もうちょっとプログラミングの問題らしくしましょう。1からはじまって、2増して3、2増して5。2増してを4回繰り返します。次に4増して同じく4回繰り返します。このようにして対角線上の数を求めて和を取ればよいです。

Problem 28この問題は答えを出すだけなら簡単です。1から右上は4n2 + 4n + 1などと計算していけばすぐに和は出ます。

Problem 27この問題は、パッと見素数判定が大変そうですが、実は判定する数はそんなに大きくはならないのです。だから、必要になったら1000ごとにエラトステネスのふるいをかけて素数を持っておけばよいです。エラトステネスのふるい用に配列で持っておき、…

部分文字列 @echo off setlocal set s=1234567890 echo %s:~3% こうすると、 4567890と表示されます。しかし、任意の場所からの部分文字列を取るにはどうしたらいいでしょう。例えば、n = 3としたときに、nを使って部分文字列を取りたいです。 set /a n = 3 …

Problem 26pが素数なら 10d ≡ 1 (mod p) となる最小のdがサイクル長となります。実質的には、大きいほうから試してdがn-1となる素数pを探せばよいでしょう。フェルマーの小定理からn-1では必ず上の式を満たします。また、これから上の式を満たすdはn-1の約数…

Problem 25 昨日までの準備した関数を使って、答えを出すことができます。 平方根やlogも用意してもいいのですが、この問題では外で計算しておいてもよいでしょう。 log10√5 = 0.34948500… log10(1 + √5)/2 = 0.20898764… なので、8桁取って、下なら20898764…

Problem 25 この問題は長整数など使う必要はなく、本来Fibonacci数列の一般項、 を使えば即解けます。右辺第2項はnが大きくなれば非常に小さいので無視できます。 ただ、バッチファイルでは整数の演算しかできません。次回からは、工夫して小数の計算ができ…

Problem 25 フィボナッチ数列なので足していくだけです。1000桁まで計算しなければならないわけですが、過去に作った長い整数のための関数群を使えば簡単です。16分かかって答えが出ました。

Problem 24 順列を順番に出してみましょう。どういうアルゴリズムにすればよいかというと、例えば 02431の次は 03124です。まず、後ろから見ていって最初に数字が小さくなるところを探します。2のところですね。そして、また後ろから見ていって2より大きい数…

Problem 24 この問題は解くだけなら手計算レベルです。例えば、0〜3までを使ったとして9番目の順列は、そこまで列挙すると、 0123 0132 0213 0231 0312 0321 1023 1032 1203となります。これをこのように分けるとわかりやすいです。 0123 0132 0213 0231 031…

Problem 23 6が完全数で、12以上の6の倍数が過剰数であることはすぐにわかります。なので、6の剰余で分類して考えるとよいです。 例えば6の剰余が2（以下、r = 2などと表記する）なら20、r = 4なら40になります。しかし、奇数はすなわち2を因数に含めないの…

Problem 23 Problem 21と同じように約数の和を求めて、28123より小さい過剰数のリストを得ます。28123より小さいインデックスの配列を作って、0に初期化します。そして、全ての過剰数のペアの和を取ってその要素を1にします。 しかし、この方法は大きな配列…

Problem 22 この問題は、ファイルを読み込むのが難しいです。どうやらデフォルトでは一度に8192バイト以上は読めないようです。 for /F %%s in (names.txt) do ( echo %%s ) 適当な文字で区切って少しずつ読めば長い文字列でも読めます。例えばZで区切って、…

Problem 21 大きな配列を取ると劇的に遅くなるので、小さい配列でエラトステネスのふるい的に約数の和を取ってみました。ただし、そうすると約数の和のためにもう一つ配列が必要になります。例えば、10なら、a[10]=10とb[10]=1とします。bが約数の和です。2…

整数の範囲で平方根を求める、すなわち整数Nに対して[√N]を求めます。これは簡単なアルゴリズムで求められます。Nを初期値として、x -> [([N / x] + x) / 2]を繰り返し、値が減少しなくなったら、その前の値が平方根です。例えば、10 -> [(10 / 10 + 10) / 2…

Problem 21 今度は、ふつうにエラトステネスのふるい的に約数の和を求めました。ただし、変数の数が多くなると遅くなるので、まず最小の素因数を記録しておいて、そこに約数の和を上書きする方法を取ります。それでも、10000も変数があると非常に遅くなりま…

Problem 21 約数の和といえば素因数分解、素因数分解といえばエラトステネスのふるいですが、最初は単純な約数の求め方を使いましょう。例えば、20の約数を求めたいとすると、[√20] = 4だから2〜4までで割り切れるか調べればよいです。forで回す回数が決まっ…

例えばこんなバッチファイルがあるとします。 @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…