未解決問題を解こうシリーズ第5弾。http://projecteuler.net/index.php?section=problems&id=373214着。4500秒かかった。当時はたぶん外接円の半径の公式を見てお手上げになっていたのだろう。公式を捨てて逆から考えたら、すなわち半径がある整数なら辺の長…

Problem 30これは重複組合せを生成する問題です。PowerShellの関数はほぼジェネレータなので、簡単に生成できます。 22秒かかりました。 PowerShellのシリーズはここまでです。

Problem 29これは手計算でできる問題です。べき乗の計算をしてはいけません。

Problem 28これは関数型に導くための問題ですね。数学的にも解けますが、対角線上の数を内側から外側に4つずつ列挙します。

Problem 27素数判定のメモ化のために連想配列を使います。連想配列にキーが存在するかの判定は、こうすればいいようですね。 $a = @{ 2 = $true; 3 = $true; 4 = $false } $a[5] -ne $null 無いキーを参照すると$nullが返るようです。 5分弱かかりました。

Problem 26剰余類群で10が生成元になる最も大きい素数を求めればよいのですが、なるべく手抜きすることを考えます。10と互いに素で、gp-1で初めて1になればよいです。これを素直に書きました。

Problem 25この問題はlogを求めてもよいですが、正確に求めてみました。 38秒かかりました。

Problem 24この問題は本当は一瞬で解けるのですが、あえて順列を出します。PowerShellの関数はほとんどジェネレータなので、Pythonのように再帰で簡単にpermutationsを書くことができます。その中で foreach($c in permutations $b) { ,(@($h) + $c) } こう…

Problem 23この問題は6の剰余で分類すると速いです。なぜなら、12以上の6の倍数はすべて過剰数だからです。 144秒かかりました。

Problem 22テキストファイルを読むにはcatコマンドですね。typeでも同じです。シェルスクリプトだからこういうこともできます。 ソートはsortコマンドで。

Problem 21エラトステネスのふるい的に約数の和を求めるだけですね。

Problem 20当然ですが、掛けていくだけですね。数字を配列にすれば最後も簡単です。

Problem 19年月日から曜日を調べるのも簡単です。

Problem 18あえてメモ化を使わずに再帰です。 三角形の頂点はやっぱり配列にならないので、あとから配列にしています。

Problem 17コードを分かりやすくするために1 => "one", 2 => "two", ...という連想配列を作っておきます。 連想配列は次のように作ります。 $pt = @{ x = 1; y = 2 } $pt Name Value ---- ----- y 2 x 1個々にアクセスする方法は、 $pt.x # 1 $pt["y"] # 2 …

Problem 162倍を1000回繰り返すだけです。簡単ですね。

Problem 15Cはfoldを使って実装しています。答えが大きいので、初期値を1Lとします。ただし、この関数は第2引数が0だと正しい答えが出ません。

Problem 14.netのArrayListを使ってみます。 $a = New-Object System.Collections.ArrayList(10) これは領域確保するだけ、すなわちstd::vectorでいうreserveしただけのようです。ここからAddで追加していきます。 $a.Add(1) しかし、Addメソッドは挿入され…

Problem 14コラッツです。再帰でメモ化するだけですね。ふつうに配列を使ってます。 7分あまりかかりました。

Problem 13この問題は1桁ずつの配列にして足し合わせます。足すときPythonのizip_longestに相当する関数を用意しておくとコーディングが比較的楽になります。

Problem 12素因数分解がなかなかうまくいきません。配列の配列を一つ関数から出すと、配列の配列になってくれません。仕方がないので、配列の要素の型を調べてInt32だったら配列の配列にします。

エラトステネスのようなリストを使う計算はPythonでは非常に遅いですが、Numpyを使うと速くなります。http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-pythonに書かれてあるprimesfrom2toという関数です。 import nu…

Problem 11正方形内から3つ進んだところが正方形内なら積を取ることができます。 とにかく,（カンマ）の優先順位が高いのが分かっていても感覚と合わないからすぐに間違えます。

Problem 10単なるエラトステネスのふるいですが、さすがに遅いです。今回は時間測定しました。10分かかりました。

Problem 9この問題は、ピタゴラス数の生成を使えば、 a + b + c = 2 lm(m + n) だから、500を3分割してそれぞれがl, m, m + nに対応させて、それが条件 m + n : 奇数 m m + n m + n m gcd(m, n) = 1 を満たせばよいです。そのために約数を生成しなければなり…

今さらJavaをおぼえなければいけないみたいなので、とりあえず10問解いてみた。 Problem 1 C++とほぼ同じ。 public class e001 { public static void main(String args[]) { int s = 0; int N = 1000; for(int n = 1; n < N; ++n) { if(n % 3 == 0 || n % 5 …

Problem 8文字列は文字の配列のようです。 $s = "123" $c = $s[0] [int]$c # 49 部分文字列を取るにはsubstringを使います。 $sub = $s.substring(1, 2) [int]$sub # 23

Problem 7この問題はふつうにエラトステネスのふるいでよいでしょう。どれだけの大きさの配列を用意すればいいかわかりませんが（素数定理を使えば概算できますが）、上限が不明なときの問題解決法に書いたように倍々にすればよいでしょう。 filter map($f) …

次の関数について考えます。 これをそのまま書くと、kはnまでで十分だから、 def H(n): return sum(n / k for k in xrange(1, n + 1)) ですね。O(n)の計算量のはずです（nが小さければ）。 さて、この計算を速くできないでしょうか。まず、n = 10で具体的な…

Problem 6この問題だけは何の意味があるのか分かりません。 filter map($f) { & $f $_ } $n = 100 $s1 = (1..$n | map { $_ * $_ } | measure -sum).sum $s2 = (1..$n | measure -sum).sum $s2 * $s2 - $s1