2012-07-01から1ヶ月間の記事一覧

Windows PowerShellでProject Euler(25)

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

Windows PowerShellでProject Euler(24) 連想配列

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

Windows PowerShellでProject Euler(23)

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

Windows PowerShellでProject Euler(22)

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

Windows PowerShellでProject Euler(21) ArrayList

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

Windows PowerShellでProject Euler(20)

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

Windows PowerShellでProject Euler(19)

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

Windows PowerShellでProject Euler(18)

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

NumPyでエラトステネスのふるいを完全理解する

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

Windows PowerShellでProject Euler(17)

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

Windows PowerShellでProject Euler(16)

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

Windows PowerShellでProject Euler(15)

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でProject Euler Problem 1〜10

今さら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 …

Windows PowerShellでProject Euler(14) 文字列

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

Windows PowerShellでProject Euler(13) エラトステネスのふるい

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で具体的な…

Windows PowerShellでProject Euler(12)

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

Windows PowerShellでProject Euler(11)

Problem 5lcmを繰り返し適用するだけの問題です。lcmがgcmを使います。gcmはふつうに再帰で定義します。 function fold($f, $init) { begin { $x = $init } process { $x = & $f $x $_ } end { $x } } function gcd($m, $n) { if($n -eq 0) { $m } else { gc…

Project Euler 391(2)

http://projecteuler.net/index.php?section=problems&id=39133着。2時間かかった。もうちょっとなんとかしないと。 日曜がナイーブな実装とアイディア出し。 月火がコーディング、というかデバッグ。 水木が高速化のためのアイディア出し。 特に今朝はいろ…

Project Euler 391(1)

http://projecteuler.net/index.php?section=problems&id=391M(100)に0.8秒もかかっている。考え直さないと。