« 「階乗フィーバー数問題」の高度じゃないコード | トップページ | 「トライアングル・メイズ問題」の高度じゃないコード »

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 を作ることも同じ処理でできることに気が付きました。しかも、どうやら、そちらの方が最初の処理での発散が少なくなることから、処理時間も短くなりそうです。

ということで、逆向きの処理に直して最終提出したのが次のコードです。(なぜか、手違いで1行目~8行目までがダブった状態で提出していました。エラーが出なかったので全く気付きませんでしたが)


(28行目の sort は、最初のコードで d[-1] が q であるか調べていた名残なので、今では不要です)

ちなみに、この逆向きコードで殺戮ケース避けである21行目最後の「if s[1]>?0」を除いて8つのテストケースを試してみましたが、その状態でも全テストケースクリアとなりました。どうせやるのなら、逆向きコード用の殺戮ケースも用意しておかないと・・・。

|

« 「階乗フィーバー数問題」の高度じゃないコード | トップページ | 「トライアングル・メイズ問題」の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/64016160

この記事へのトラックバック一覧です: 「プライム・ホッパー問題」の高度じゃないコード:

« 「階乗フィーバー数問題」の高度じゃないコード | トップページ | 「トライアングル・メイズ問題」の高度じゃないコード »