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

CodeIQ 挑戦の記録 : 「プライム・ホッパー」問題

CodeIQ

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

f:id:ibeckuu:20160707020612p:plain

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

  • ある素数に対し、変換1と2を次の通り定義する。
    変換1:元の数の右または左に1~9のいずれかの数字一つをつなげる。
    変換2:元の数の右端または左端の数字一つを取り除く。
    (ただし、最上位桁が0で始まる数値への変換は不可)
  • 標準入力から素数{p}{q}が与えられる。({{p} \lt {q}})
    素数{p}から始めて、変換1または2を繰り返して{q}を作る最小の交換回数を解答する。
    (途中の数は全て{q}以下の素数)
  • {{p} \lt {q} \leq {10}^{5}}

方針

幅優先探索を用いる。
qまでの配列を用意し、初期値として素数の項を0、合成数の項を-1とする。
題意の通り変換できる限り素数を変換していき、使用していない素数であればキューに追加し、幅優先探索で探索する。
同時に何回めの変換かを配列に記録する。
変換した数がqと一致すると配列に記入した回数を解答する。

実装(Ruby)

では、


Sponsored Link