-- / --
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

01 / 02
Thu

「元旦」 ってのは本当に 「元日の朝」 なのだろうか、 と思う Ziphil です。

Project Euler を少しずつ進めていってます。 ということで、 今日やった 24 問目を。

「順列」 とは、 ある物が順に並べられている状態のことをいう。 例えば 3124 は、 数字 1, 2, 3, 4 の順列としてあり得る 1 つである。 全ての順列が小さい順に並べられたとき、 それを 「辞書式配列」 と呼ぶ。 0, 1, 2 の順列の辞書式配列は、 012, 021, 102, 120, 201, 210 である。 数字 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 の順列を辞書式配列で並べたとき、 100 万番目は何か。

高校の数学でありそうな問題ですね。 といっても、 100 万番目というのはただ単に面倒なだけで、 受験数学的能力を試すのにふさわしいとは言えませんが。

この問題、 最適化とか何も考えなければ、 Ruby ではメソッドチェーンで 1 行で書けます。

def project_euler_24
  puts (0..4).map(&:to_s).permutation.to_a.map(&:join).sort[999999]
end

permutation メソッドが便利ですね。 実行しましょう。

project_euler_24  #=> 2783915460

ということで、 2783915460 が答えです。 ・・・答えなんですが、 実は最初、 自信満々に 2783915604 だと答えて、 間違ってると言われて、 しばらく悩みました。 まあ、 もう私が何をしたかわかると思いますが、 プログラムの最後を sort[1000000] と書いていたんです。 配列の最初の項のインデックスは 0 だというのに。 いやー、 プログラミングは 10 年くらいやってますが、 配列のインデックスが 0 から始まるのって、 たまに忘れるんですよねー。

ちなみに、 これだと答えを出すまでに 20 秒程度かかりました。 うん、 遅いね。 まあ、 最適化なんて全くしてないですから仕方ないですよね。


スポンサーサイト
comment ×0
back-to-top
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。