読者です 読者をやめる 読者になる 読者になる

UVa100 The 3n + 1 problem

問題概要
n の偶奇で計算を分ける。整数 i と j を含む間の数の中で計算を繰り返した結果 1 になる回数が最大のものを求めて、その回数を出力せよ。

解答
UVa の中で最も手を付けられるだろう問題の割にはメモ化再帰しないと恐らく解けない。
奇数の計算をした直後は値が増加するので 1 にはならない。よって偶数の分まで一度に計算してしまうとよい。

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX (1000000)
int memo[MAX];
int solve(int const n) {
  
  if(n < MAX && memo[n]) return memo[n];
  if(n == 1) return 1;
  
  int N = n;
  if(n & 1) {
    if(n < MAX) { return memo[n] = solve((3*n+1) >> 1) + 2; }
    else { return solve((3*n+1) >> 1) + 2; }
  }
  else {
    if(n < MAX) { return memo[n] = solve(n>>1) + 1; }
    else { return solve(n>>1) + 1; }
  }
  
}

int main() {
  
  for(int I, J, i, j; cin >> I >> J; ) {
    if(I > J) { i = J, j = I; }
    else { i = I, j = J; }
    int ans = 0;
    for(int n=i; n<=j; n++) {
      ans = max(ans, solve(n));
    }
    cout << I << " " << J << " " << ans << endl;
  }
  
  return 0;
}