プログラムの実行結果は以下の通り。
最大の手数: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;
}