朝日新聞2006年8月4日のパズル横丁問題

問題

1〜99の数がある。5の倍数は0.8倍し,それ以外の数は7を足す。結果の数字に対して100になるまで同じ処理を繰り返す。

100になる数のうち手数が一番掛かるのはどれか。

解答への道(ヒント)

0.8という数字が出てくるけど,

であるから,5の倍数を0.8倍すると必ず整数になることが判る。

ということで,分母,分子を分けて計算するようなことはしなくて済む。

手数を求める関数は以下のようになる。

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になった時点で終了
  }
  return    cnt;
}

注意しなければならないのは,いくらやっても100にならない場合があるってこと。

最初,問題文にある「100になる数のうち」の部分を見落としていて,何れ100になるだろうと思って上記関数を作り永久ループさせてしまいました。

100にならない数値を検出し,1〜99でこの関数を呼び出せば答えが求まる。

100にならない数値は循環するので,循環を如何に検出するか。

まじめに考えると面倒なので,100/0.8=125を回数の上限にしてしまうのが簡単。

答えは1件出力されました。

今回の問題もEXCELでやろうと思えば,自動で答えを出すのは難しいと思うけど,ある程度の手助けとなるように出来ると思う。

逆にもっと厳密に「状態遷移」を考えて以下のようにする人もいるかも知れない。

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));
  }
  ……… // 状態遷移図を完成させる,最大数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;
}

当然答えは同じになる。何れにしろ自分に合ったやり方で解くのが一番楽しいものである。

 

ガソリンの値段が一気に上がった。7月31日にはガソリンスタンドに行列が出来ていた。8月1日から値上げという話がニュースで取り上げられていたからだと思うが,その時点で既に値上げしていたガソリンスタンドにも行列が出来ていたのは笑った。おいおい,明日になっても一緒だぞ。

「今年の夏休みはガソリンが高いから外出しないで,家でプログラミングするぞー」って人が日本全国で何人くらいいるだろうか。

解速度