読者です 読者をやめる 読者になる 読者になる

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第93回「ナルシストなナルシシスト数」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

f:id:ibeckuu:20160523223811j:plain

問題文を要約すると下記の通り

(ウイキペディアより引用)

n桁の自然数であって、その各桁の数のn乗の和が、元の自然数に等しくなるような数をいう。例えば、{{1}^{3} + {5}^{3} + {3}^{3} = 153} であるから、153 はナルシシスト数である。

十進法に限らず、他の基数においても同様にナルシシスト数を定義できる。

  • 標準入力から nが与えられる。n進数で2桁以上のナルシシスト数を小さい方からn個求め、標準出力にn進数で順に出力する。
  • nは10以下の整数。

方針

全探索({O(n)})するより他に良い方法を思いつかなかった。
しかしながら、問題文より、答えを10個出力すれば打ち切れるので全探索をする事にした。

サンプルとして10進法の例が書かれてあり、10進法での10個目の答えは「93084」となっているので、(組み込み関数の内部処理を無視すれば)nの最大で約93,000回ほどのループ(x定数倍)で答えがでる。
その他の基数でのナルシシスト数の個数は不明で、10個に満たない場合、最悪のケースで{{9}^{9}}=約3億8千万回ループする可能性があるが、それで時間制限に間に合わなかった場合は、改めて考え直す事にした。
実装してからローカルでテストすると、十分間に合ったのでそのまま提出した。
(提出結果は{n=10}のケースで約0.3秒で正解)

なお、rubyでは

  • 10進法の数値を任意のn進法の文字列に変換して表示するメソッド
  • n進法の文字列を10進法の数値に変換するメソッド

をともに備えているので、これを利用し、n進法で2桁の最小値({{n}^{1}})からn桁の最大値({{n}^{n}-1})までの整数を都度n進法に変換し比較、ナルシシスト数と一致したものを出力した。
組み込み関数を用いればRubyでの実装は簡単であった。

実装(Ruby)

では、



Sponsored Link