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
時間掛かりすぎ。