UVa – The 3n + 1 problem 解读

这个问题并计算质数了一下相间隔似的。思想上一致。

注意问题：

1 i 可能 大于或等于j — 这里上传。小心阅读题意，我没有说这个地方不能保证。需要特殊处理

2 计算过程中可能溢出，的整数大于最大值，需要使用long long

关于效率和时间问题：

1 能够使用数组保存中间结果，这样执行快了。内存消耗大了，

2 能够不使用中间数组。 这样执行肯定比較慢了。可是内存消耗小，一样能够AC的。

全部没有个标准吧。看情况而定。假设须要速度就添加数组，假设省内存就不使用数组吧。

这样的题目一般都使用数组吧。

我这里使用数组。

參考博客：http://tausiq.wordpress.com/2008/12/09/uva-100-the-3n-1-problem/

题目例如以下：

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem

Consider the following algorithm:

 
		1. 		 input n
		2. 		 print n
		3. 		 if n = 1 then STOP
		4. 		 		 if n is odd then   
		5. 		 		 else   
		6. 		 GOTO 2
 

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

注意好上述问题之后就比較好AC了。

我以下程序是写了个类，分开多个函数，能够看的逻辑十分清晰的。当然/2和*2能够改动成>>1和<<1操作。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <stdio.h>

using namespace std;

static int table[1000000] = {0};//={-1}不正常工作。仅仅能清零

class ThreeNOne
{
public:
	const static int MAX_N = 1000000;
	ThreeNOne()
	{
		table[1] = 1;
		for (int i = 2; i < 1000000; i*=2)
		{
			table[i] = table[i/2] + 1;
		}
		initTbl(table);
	}

	int checkTbl(int tbl[], long long i)//i一定要为longlong，int会溢出
	{
		if (i < MAX_N && 0 != tbl[i]) return tbl[i];
		if (i % 2)
		{
			if (i < MAX_N) tbl[i] = checkTbl(tbl, i * 3 + 1) + 1;
			else return checkTbl(tbl, i * 3 + 1) + 1;
		}
		else 
		{
			if (i < MAX_N) tbl[i] = checkTbl(tbl, i / 2) + 1;
			else return checkTbl(tbl, i / 2) + 1;
		}
		return tbl[i];
	}

	void initTbl(int tbl[])
	{
		for (int i = 3; i < 1000000; i++)
		{
			checkTbl(tbl, i);
		}
	}

	void The3n1problem()
	{
		int i = 0, j = 0;
		while (cin>>i>>j)
		{
			pair<int, int> t = minmax(i, j);//区间给定不一定是i<=j的，细致审题
			int ans = 0;
			for (long long d = t.first; d <= t.second; d++)
			{
				ans = max(ans, table[d]);
				//错误：ans += table[d];细致读题，不是和。而是maximum
			}
			cout<<i<<' '<<j<<' '<<ans<<endl;
		}
	}
};

int main()
{
	ThreeNOne tno;
	tno.The3n1problem();
	return 0;
}