朝日新聞2004年6月26日のパズルパーク問題

問題

307x275=82735

このうち数字を２箇所書き換えると正しい式になる。正しい式を求める。

解答への道(ヒント)

一見抽出系の問題に見えるが，虱潰し問題として考えると簡単。

100万回の虱潰し問題。実際は6桁になったときそれ以上大きな数を比較する必要がなくなるので，33万回位の虱潰し問題になる。

for( int i=1; i< 1000; i++) {
  for( int j=1; j< 1000; j++) {
    k = i*j;
    if( k >= 100000) break;
    // i,j,k の組合せが 307 275 82735 と何文字異なるか調べる。異なる文字数が2となるときが答え
  }
}

かけ算の結果が6桁になった場合は答えにならないので6桁を越えた時点で内側のループは終了して良い。

数字を文字列に変換するのに sprintf() を使うと結構遅くなる。このように桁数が判っているような場合以下のような関数を使って1桁ずつ変換した方が速い。

char dec2chr(int i)
{
  return '0' + (i%10);
}

呼び出しは以下のように1桁ずつ行う。

*p++ = dec2chr(i/100);
*p++ = dec2chr(i/10);
*p++ = dec2chr(i);

文字列に変換せず直接数字のまま比較しても良いけど，プログラムとして美しく無い気がする。

今日もEuro2004だ。早く寝よう。

解速度

0.6秒(Pentium�V500MHz)

sprintf() を使った場合 2.2 秒。

ちなみに数字のまま直接比較すると0.5秒。