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

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

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

Project Euler 335

http://projecteuler.net/index.php?section=problems&id=335法則さえ見つければあとは高校レベル。なぜいまだに40人しか正答者がいないのかわからない。2問が一度に出るときは2問目のほうが少し易しい印象がある。こっちを最初にやったほうがランクインしや…

Project Euler 334(2)

http://projecteuler.net/index.php?section=problems&id=334できた。0.01s。ものすごくつまらないミスだった。 フォーラムで同じ考え方をしている人がいた。

Project Euler 334

http://projecteuler.net/index.php?section=problems&id=334起きた時間ではすでに6時間以上経っていたはずだが、正答者数は20人と17人。Hardの順番だったが、2問ということで易しいのかと思っていた。 考えてみるとわりと簡単なのかなと思って組んでみたが…

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

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

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

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

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

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

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

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

Project Eulerの進め方

時代は数論!今すぐ始められる、簡単☆ProjectEuler入門ガイド - EchizenBlog-Zwei Project Eulerを紹介する記事が上がっていたので、退役軍人(?)の私からも少しアドバイスなんぞを。Project Eulerの問題は基本的には1問目から順に解きましょう。最初の方…

Project Euler 333(2)

http://projecteuler.net/index.php?section=problems&id=333 やり方を変えてさらにメモ化したら20秒になった。 これ、2と3と5だったらどうなるんだろう。ちょっと考えてみたが、難しそう。

Project Euler 333

http://projecteuler.net/index.php?section=problems&id=333 いつの間にか問題が出ていて、60人以上解いていたが、今も60人台。 簡単かと思ったが、なかなか書きづらかった。しかも2時間かかった。もうちょっとなんとかなると思うけど。

Project Euler 331(3)

http://projecteuler.net/index.php?section=problems&id=331 O(N)のコードを書いて、奇数の場合も1小さい四角で考えてコードを書いた。5時間以上かけて動かしたが、答えが違う。ちょっと数値誤差があやしいといえばあやしい。あと奇数の場合もあやしい。も…

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

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

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

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

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

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

Project Euler 332(2)

http://projecteuler.net/index.php?section=problems&id=332結局、球面上の三角形の面積の求め方は検索した。角度を求めればいいのか。角度は自力で求めた。これは高校生レベル。あとは全探索。10分以上かかった。相当重複して計算しているので、余力があれ…

Project Euler 332

http://projecteuler.net/index.php?section=problems&id=332 意味がわかったようなわからんような。そもそも球面上の三角形の面積って? A(14)計算したけど、全然あわない。

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

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

Project Euler 331(2)

http://projecteuler.net/index.php?section=problems&id=331 きのう真面目に考えてみた。そのうちにこれは線形代数であることに気がついた。ノートと格闘したらNが偶数のときに非常に好ましいことになることがわかった。今日それで組んでみたら、T(1000)は…

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

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

Project Euler 330(2)

http://projecteuler.net/index.php?section=problems&id=330 やっとできた。まれにこのパターンの問題があるから困る。1分くらい。

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

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

Project Euler 331

http://projecteuler.net/index.php?section=problems&id=331 オセロ、じゃないのか。 こんな問題解けるのか? さっぱりわからないので、Pythonでこのゲームを遊べるように作った。

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

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

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

除算 被除数が除数より小さければ被除数を2倍します。そして割り算をします。1ビットずつ求めれば簡単です。例えば、111を101で割るなら、まず、被除数のほうが大きいので商が1で、被除数から除数を引いて10、2倍して100。被除数のほうが小さいので商は10、…