2011-03-01から1ヶ月間の記事一覧

バッチファイルで浮動小数点数演算(3)

乗算 仮数部を12ビットずつにわけて掛け算すれば簡単です。その上24ビットを取ります。四捨五入はしていません。指数部は単純に足し算です。最後に符号をつけます。

バッチファイルで浮動小数点数演算(2)

加減算 指数を合わせて加減算するだけです。指数は大きいほうに合わせます。その際に仮数部が四捨五入でなく切り捨てられることがありますが、細かいことは気にしないことにします。

バッチファイルで浮動小数点数演算(1)

バッチファイルでは本来整数演算しかできないのですが、IEEE754の単精度をエミュレートすることにより浮動小数点数演算を実現します。Project Euler 25が解ければいいので、厳密にエミュレートはしません。IEEE754の単精度は、簡単に言うと仮数部を23ビット…

バッチファイルでProject Euler(58)

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

Project Euler 330

http://projecteuler.net/index.php?section=problems&id=330 eってEulerのeなんだっけ? とりあえずa(10)を出してみよう。 やっとa(10)出た。でも、この先どうやっていけばいいのか

バッチファイルでProject Euler(57)

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

バッチファイルでProject Euler(56)

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

バッチファイルでProject Euler(55)

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

バッチファイルでProject Euler(54)

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

Project Euler 329

http://projecteuler.net/index.php?section=problems&id=329 この問題は簡単。できた、と思ったら蹴られた。なにが間違っているのか? 全然違ってた。20着滑り込み。なぜこういうのをスラスラと書けないのだろう。

バッチファイルでProject Euler(53)

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

Project Euler 328

http://projecteuler.net/index.php?section=problems&id=328 また難しそうな問題が出た。でも、今回は英語は易しかった。 C(8)出たけど、C(100)は間違っている。 C(100)出た。でも、20万は数十時間かかりそう。 おいおい、3時間経ってもまだ誰も解けていな…

バッチファイルでProject Euler(52)

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

Project Euler 327(3)

http://projecteuler.net/index.php?section=problems&id=327 今朝電車の中でノートに向かって考えていたら、M(C,R)が実質1行で書ける方法を思いついた。なんだったんだ、いったい。O(R)だし。R = 30にだまされた。

Project Euler 327(2)

http://projecteuler.net/index.php?section=problems&id=327 手計算でC=3のときはわかった。しかし、M(4,6)がなかなか出ない。それがなんとか出た。難しい。

Project Euler 327

http://projecteuler.net/index.php?section=problems&id=327 英語の長文。しかも意味がわからない。なんとか理解したが、それまでにどれだけ時間がかかっただろう。 で、これはどうやって解けばいいのかな?

バッチファイルでProject Euler(51)

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

バッチファイルでProject Euler(50)

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

バッチファイルでProject Euler(49)

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

バッチファイルでProject Euler(48)

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