« 2016年7月 | トップページ | 2016年10月 »

2016年8月 5日 (金)

「プライム・ホッパー問題」の高度じゃないコード

「高度じゃないコード」シリーズその16「プライム・ホッパー問題」です。

まずは問題の内容です。(挑戦履歴より転載させていただきました)

ある素数に対し、次の変換1と2のいずれかを適用し、新たな素数を作ります。

変換1:元の数の右または左に1~9のいずれかの数字一つをつなげる。
(例:2→23、13→139、3→13、29→229)

変換2:元の数の右端または左端の数字一つを取り除く。
(元の数が 2 桁以上の場合のみ。例:31→3、673→67、23→3、673→73)

例えば 7→227、17→37 は有効な変換ではありません。
また 103→03 のように、先頭に 0 のつく数への変換はできません。

さて、素数 p と q(p < q)が与えられたときに、素数 p から始めて、変換1または2により q 以下の素数を作るということを繰り返し行い、最小の変換回数で q を作ることを考えましょう。

p=5,q=67 のときの一例を示します。
計 5 回の変換で 67 に変換できます。途中の数がいずれも 67 以下の素数であることに注意して下さい。
なお必ずしも変換1と2の両方を行う必要はありません。

  5 → 53 → 3 → 37 → 7 → 67

素数 p, q に対し、p から始めて q を作るときの最小の変換回数を F(p, q) と定義します。
そのような作り方が存在しない場合は F(p, q) = -1 と定義します。
例えば F(5, 67) = 5,F(3, 29) = 3,F(5, 541) = 10,F(3, 7) = -1 です。

標準入力から、半角空白区切りで素数 p, q(p < q かつ q ≦ 105)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

今回、殺戮ケースがあるという話を予め聞いてはいましたが、最初に作ったコードはそれにまんまと引っ掛かってしまいました。とりあえず、そのコードでの考え方を説明します。

最初に配列に p のみを入れます。そして、配列に入っている全ての数字に対して、変換1か変換2を行ってできる数字であり、q 以下であり、今まで出てきてなくて、そして素数である数を新たな配列に入れ、次回はその配列を処理の対象とします。これを、カウントしながら q が出てくるまで、または、配列が空になるまで繰り返すわけです。

ところが、これで提出すると、テストケースの1つが不正解となります。最初は、意味がわからなかったのですが、問題文をよく読み返してみてわかりました。
「また 103→03 のように、先頭に 0 のつく数への変換はできません」
これを考慮してなかったからでした。それに対する回避コードをつけて提出して全テストケースクリアとなりました。

その後、上記条件があるお陰で、逆向き、つまり、q から始めて p を作ることも同じ処理でできることに気が付きました。しかも、どうやら、そちらの方が最初の処理での発散が少なくなることから、処理時間も短くなりそうです。

続きを読む "「プライム・ホッパー問題」の高度じゃないコード"

| | コメント (0) | トラックバック (0)

« 2016年7月 | トップページ | 2016年10月 »