3n + 1

2013-04-06 Robert Zhang 更多博文 » 博客 » GitHub »

原文链接 http://huiming.io/2013/04/06/3n-1.html
注：以下为加速网络访问所做的原文缓存，经过重新格式化，可能存在格式方面的问题，或偶有遗漏信息，请以原文为准。

分析：运算时产生的大数可能会使32位整数溢出，需要使用64位的整数类型<!--more-->

#include <vector>
#include <iostream>

#ifdef DEBUG
#include "../comm_headers/debug_helper.h"
#else
#define DEBUG_OUT(...)
#endif

#define MAX 999999

using namespace std;

vector<int> r(MAX + 1);

int length(int i) {
  DEBUG_OUT("n--------------- length of %d --------------n", i);

  if (r[i]) {
    DEBUG_OUT("=%dn", r[i]);
    return r[i];
  }

  typedef long long ll_t;
  vector<ll_t> s(8);
  s[0] = i;
  int j = 0;
  ll_t n = s[j];
  while ((n <= MAX && !r[n]) || n > MAX) {
    if (s.size() == j + 1)
      s.resize(s.size() * 2);

    DEBUG_OUT("%lld ", n);

    if (n % 2)
      s[++j] = 3 * n + 1;
    else
      s[++j] = n / 2;

    n = s[j];
  }

  int l = r[i] = r[n] + j;
  DEBUG_OUT("... n=%dn", l);

  for (int k = 1; k < j; k++) {
    ll_t m = s[k];
    if (m < MAX && !r[m])
      r[m] = l - k;
  }
  return l;
}

int main() {
  r[1] = 1;
  int a, b;
  while (cin >> a >> b) {
    int l, r;
    if (a <= b) {
      l = a;
      r = b;
    }
    else {
      l = b;
      r = a;
    }
    int max = 0;
    for (int i = l; i <= r; i++) {
      int len = length(i);
      if (len > max)
        max = len;
    }
    cout << a << ' ' << b << ' ' << max << endl;
  }
  return 0;
}