プログラムの実行結果は以下の通り。
最大の手数:22 その時の値:87
プログラムのソースは以下の通り。
#include "puzutl.h" int find( int i) // i:1〜99の数 { int cnt = 0; // 手数 while(1) { cnt++; if( (i%5) == 0) i = i*4/5; // 5で割り切れる場合は0.8倍 else i += 7; // 5で割り切れない場合は+7 if( i == 100) break; // 結果が100になった時点で終了 if( cnt > 125) return -1; // 見つからなかった } return cnt; } int main( int argc, cstring argv[]) { int max_cnt = 0, cnt; set<int> nums; // 複数あるかも知れないので念のため for( int i=1; i< 100; i++) { // 1〜99の数を調べる if( (cnt=find(i)) >= max_cnt) { // 100になる数が見つかり,以前より手数が掛かる if( cnt > max_cnt) nums.clear(); // 以前より手数が掛かれば,記憶しておいた数をクリアする max_cnt = cnt; nums.insert(i); } } ps( "最大の手数:%d\n", max_cnt); set<int>::iterator ite; for( ite=nums.begin(); ite != nums.end(); ite++) { ps( "その時の値:%d\n", *ite); } return 0; }
もう一つの状態遷移方法で解いた場合以下のようなソースになる。
#include "puzutl.h" int next_value( int i) { if( (i%5) == 0) i = i*4/5; // 5で割り切れる場合は0.8倍 else i += 7; // 5で割り切れない場合は+7 return i; } int main( int argc, cstring argv[]) { // 状態遷移図を作成し解く方法。 // 1〜99までの数字の次の状態を求める。 map<int,int> next_number; for( int i=1; i< 100; i++) { int n = next_value(i); next_number.insert( pair<int,int>(i,n)); } // その中で100以上の数があれば,その次の数を求める。 // それを繰り返す。 map<int,int>::iterator ite; map<int,int> over100; // 100以上の数を一時的に記憶する領域 for( ite=next_number.begin(); ite != next_number.end(); ite++) { if( (*ite).second >= 100) { // 100以上の数が出現した。 int i = (*ite).second, n; do { n = next_value(i); // 次の遷移先を求めて over100.insert( pair<int,int>( i, n)); // 別の領域に記憶しておく i = n; }while( n >= 100); // 次の値が遷移図に無ければ求める } } // 100未満の数と100以上の数をmergeして,next_number に入れる。結果 next_number は状態遷移図を示すことになる。 for( ite=over100.begin(); ite != over100.end(); ite++) { int i = (*ite).first; int n = next_value(i); next_number.insert( pair<int,int>( i, n)); } // 状態遷移の探索をするため最大値を求めておく。 int max_number = 0; for( ite=next_number.begin(); ite != next_number.end(); ite++) { max_number = max( (*ite).first, max_number); } byte* used = new byte[max_number+1]; // 訪問済みかどうか調べるために利用する int max_cnt = 0, cnt; set<int> nums; // 複数あるかも知れないので念のため // 1〜99の状態遷移を調べる。 for( i=1; i< 100; i++) { ite = next_number.find(i); int v = (*ite).first, v_next = (*ite).second; memset( used, 0, max_number); cnt = 0; while( !used[v_next]) { cnt++; used[v_next] = 1; if( v_next == 100) break; ite = next_number.find(v_next); v_next = (*ite).second; } if( v_next == 100 && // 対象となるのは100になった場合だけ cnt >= max_cnt) { // 最大手数の場合を記録する if( cnt > max_cnt) { // 今までより多く手数が掛かっている場合は過去の記録を削除する nums.clear(); max_cnt = cnt; } nums.insert(v); } } // 解を出力する。 { ps( "最大の手数:%d\n", max_cnt); set<int>::iterator ite; for( ite=nums.begin(); ite != nums.end(); ite++) { ps( "その時の値:%d\n", *ite); } } return 0; }