2008年4月30日水曜日

Project Eulerをやってみた

このブログ記事をはてなブックマークに追加

ちょっと流行っているということで、Project Euler(プロジェクト・オイラー)(日本語Wiki)をやってみた。とりあえず3日で50問以上解いてみたが、結構面白いかも。問題自体は今までのところどれも簡単でコーディングを含めて1問につき数分もあれば解けるものばかり。しかし、すぐに解けてしまうので止め時が難しい。今後、難しくなっていくのかもしれないが。ただし、最適なアルゴリズムを考えて解こうとすると難易度は上がる。

これはプログラミングの勉強や教育にはいいかも。以前、学生にダイクストラ法を教えたことがあったけど、まさにそれを使う問題(Problem 67)も出てきた。

使用言語はC++にしている。しかし、1~2割程度はPythonで解いた。Pythonのワンライナーで解けるような問題だとついつい楽してしまうなぁ。一方、C++だと力技が結構効いたりと、使い分けの重要性を再認識した。

少しコメント。Problem 14はここのブログの自己紹介にあるコードが使える。Problem 19は、C言語のFAQで有名な以下のコードが使える。

int day_of_week(int y, int m, int d) // 0 = Sunday { static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}; y -= m < 3; return (y + y / 4 - y / 100 + y / 400 + t[m - 1] + d) % 7; }

あとは、素数を扱う問題が多いからエラトステネスの篩を使うとちょっと楽になるかもしれない。

0 コメント: