RSS

  

RSS

プログラム


ｎで割り切れる最小０１十進数

  • いわいまさか
  • at 2015/1/29 12:36:36

元の問題としては
パズ懇神戸さん作の２０１５年の年賀問題
　２７で割り切れる最小の０１十進数を求めよ
　２０１５で割り切れる最小の０１十進数を求めよ
というもの。
「０１十進数」は０と１だけでできた十進数。

いわいはこれをC#のBigIntegerを使ったプログラムを書いて解いた。所要時間は短め。これはこれでめでたし。

そのプログラムを使って、27や2015だけでなく10000まで調べてみたら、
2439のときが解けなかった。理由はプログラムの作りが悪く、そして、探索が深すぎるためのメモリーオーバーフロー。

「この件」をパズル懇話会のＭＬで投稿したところ、パズ懇メンバー白川さんが、以下のようなプログラムを示してくれた。

>白川です。
>
>2439の時、解いてみました。
>
> 2439 * 00004100496519520340344449 
>  = 10001111011110110100111111
>以下がソースコードです
> https://ideone.com/CiNF3n


そのコードは参照してもらうとそれでよろしい。
のだが、蛇足ながら、説明w

①大筋
　かける数を下の桁から決定していく。
　例えば、2439の場合であれば、
　下一桁目は 9*0=0 か 9*9=81 で0と1しかない。　

　掛け算の筆算的に書いて
■■■■■２４３９
×■ＧＦＥＤＣＢＡ
－－－－－－－－－

　ABCDEFG・・・に当てはまる数を決定していく。ただし、ＡＢＣ・・・それぞれに、候補が複数ある場合があるのでそれを探索していっている。

　Ａが９だとすると

■■■■■２４３９
×■■■■■■Ｂ９
－－－－－－－－－
■■■■２１９５１　　

１の位はＯＫ。Ｂに関しては
２４３９×Ｂ＋２１９５＝の下一桁が０か１になるようなＢをとる
この２１９５を白川プログラムではnextnumとしている。

Ｂを４と決めると
■■■■■２４３９
×■■■■■Ｃ４９
－－－－－－－－－
■■■１１９５１１

nextnum=１１９５　となる。

②プログラムの理解
tableが探索のための配列で、かつ記録をとる。
１桁解決した場合に未解決のnextnumが残り。
usedtableでnextnumの既出をチェック。（循環をふせぎ）
nextnumが１のときが終了条件で。（１０１とかも結局１にいきつくし、最小狙いでやるためには、これじゃないとだめ）
prevを記録しているので、復元できると。
もしも、答えがないときは、出力せずに終了。

③大局的な理解
nextnumを導入したところで、
問題が「分岐のある道の出口までの最短経路探索」になって。
最短経路＝最小桁数ということ。

以上


  • コメント (0)
  • トラックバック (0)
トラックバックURL :
http://www.iwai-masaka.jp/tb.cgi/56152

コメントを書く