朝日新聞2004年11月27日のパズルパーク問題

問題

8桁表示の電卓がある。正の整数割る1桁の正の整数の結果が1〜8の数字を1つずつ使うようにする最小の割られる数を求める。

この電卓は,表示ケタ未満は切り捨てです。

解答への道(ヒント)

え,12345678÷1=12345678 が答え?

そんなはずないと思う。答えは小数になっても良いのだろう。

電卓を起動して取り敢えず11÷9を打ち込む。1.22222222222

おー,111÷9=12.3333333

おー,11111111÷9=1234567.8888

おー,これが答えか?

その後何を思ったか 9876543÷8を実行。1234567.875

おー,11111111より9876543の方が小さい。もっと小さい数がありそうだ。

うーん,何でこれが問題なんだ。プログラムを作ることを考えよう。2はあり得ないから3〜9までの数でそれぞれ最小値を求めることを考える。

9876543 より小さい数になるから骨格になる部分は以下のようなコードなる。

for( int b=3; b<= 9; b++) {
  for( int a=1; a< 9876543; a++) {
    double c = a/(double)b;
    cnt++;
  }
}
ps( "%d\n", cnt);

実行すると,69135794 を出力する。うーん,回数多すぎ。これに文字列への変換とチェックが加わると偉い時間が掛かることが予想される。

だけど途中で解が見つかればそこから先は調べなくて良いので,これでやってみる。

時間掛かりすぎ。暫くパソコンの前から離れて返ってきたら終わっていた。

一応処理時間も出力するようにしてみてもう一度実行。

ループの中ではdoubleから文字列に変換して,1〜8までの数字が1つずつ使われていることをチェックする。

変換は _fcvt() を使用する。文字列に変換した後のチェックコードは以下の通り。

YesNo check( cstring s) {
  cstring       ss = s;
  char          d[] = { 0,0,0,0,0,0,0,0,0,0};
  int           n;
  for( int i=0; i< 8; i++) {    // 調べるのは8文字のみ
    n = *s - '0';
    if( n == 0 || n == 9) return NO; // 結果は1〜8の数字のみ
    if( d[n]) return NO;        // 一度のみ出現しなければならない
    d[n] = 1;                   // この数字が出現した
    s++;                        // 次の文字
  }
  return YES;
}

解速度

プログラム出力結果の数字部分を除いて出力すると以下の通り。

Find: */3 = *, 33.437sec
Find: */4 = *, 4.281sec
Find: */5 = *, 56.266sec
Find: */6 = *, 6.625sec
Find: */7 = *, 0sec
Find: */8 = *, 0.875sec
cnt:21093421

時間掛かりすぎ。