The 3n + 1 Problem

对于这道题，我的第一个想法就是使用《算法导论》中所讲的Memoization技术（动态规划这一章讲的）。因为我觉得这道题明显具有递归的特性，并且会有很多重复的子问题。Memoization技术恰好可以用在这里。简单的说，Memoization技术就是将已经计算过的值存在一个缓存里面。这样的话，当我们需要重新计算这个值时，只需要从这个缓存中读取就可以了，而不用重新计算。当需要重新计算的值比较多的时候，这个技术可以大大减少程序的执行时间。这也是它为什么被用在动态规划中的原因。这也是一个很明显的用空间换取时间的例子。

 

我所编写的代码为：

 

#include <iostream>
using namespace std;
// 问题中指明了测试数据的最大值为10000.这里多加了一个1，以使得数组是从1开始，而不是0.

#define MAX_INT 10001
 
// 对于Memoization技术来说，我们需要定义一个缓存，以及一个函数。这个函数是必要的。

// 当我们取数是，不要直接从缓存中取，而是通过这个函数。

int count[MAX_INT];
int GetCount(int n);
 
int main() {
  int p, q, r;
  int i;
 
  for (i = 0; i < MAX_INT; i++)
    count[i] = 0;
  count[1] = 1;

  while (cin >> p >> q) {
    cout << p << " " << q << " ";
    if (p > q) { // 注意，这里是必须的。因为题目中并没有告诉我们p一定会小于q。

       int temp = q;
       q = p;
       p = temp;
    }
    int max = GetCount(p);
    for (int i = p+1; i <= q; i++) {
      int temp = GetCount(i);
      if (temp > max)
         max = temp;
    }
    cout << max << endl;
  }
}
 
// 计算对于与n的值。如果n小于MAX_INT,该值可能存于count中。对于大于MAX_INT的n，

// 需要重复计算，但我们假定这样的数字不会很多，因而重复的次数不会很多。

int GetCount(int n) {
  int result = 0;
  // 对MAX_INT的测试我觉得是必须的。因为n可能会大于MAX_INT。尽管我们知道测试数据都会小

  // 与MAX_INT。但是可能存在这样的一个数t, 它是奇数，那么我们就会计算t*3+1，而t*3+1可能

  // 会大于MAX_INT。

  if (n < MAX_INT && count[n] != 0)
    return count[n];
 
  if (n%2 == 0) {
    result = GetCount(n/2) + 1;
  } else {
    result = GetCount(n*3+1) + 1;
  }
  if (n < MAX_INT)
    count[n] = result;
  return result;
}

总结：虽然读了题目之后，可以很快的想到解决方法并很快的编写完程序。但是得到这个最终的PKU ONLine接受的版本，还是经过了很多次的修改的。所遇到的主要问题包括：
1. 认为传递给GetCount的参数小于MAX_INT。尽管题目中已经说明了测试数据的最大值是10000，但是这并不是可能传递给GetCount函数的最大值，因为有个n*3+1。在刚开始的时候，没有对大于MAX_INT的参数进行处理，导致了错误。
2. 想当然的认为p一定会小于q. 按照题目的思路以及给的测试数据的例子，很容易的会认为p会小于q。但是，将所写的程序给PKU Online时，一直得不到正确的结果。花了很多的时间改程序，但还是不对。最后尝试着假定p大于q的情况并对程序进行了修改，最后才得到了正确的结果。