UVA 100: The 3n + 1 problem

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

题目大意：

      3n+1问题是一个非常经典的数学问题，目前还没有人能够证明。一个数通过3N+1的算法会等到一个序列，序列肯定会以1结尾，例如22的序列是22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1，它的序列长度是16.

     现在要给你一个范围,n,m，让你求出这个范围你每个数的3N+1序列最长是多少。

解题思路：

      这个问题是UVA中最简单的题目，打算按那个UVA的难度排行表一题一题做下去。

      解决办法是将这个范围内的数，每个都求出它的序列长度，然后保留最大的长度。

      这题有一个trick,就是给你n,m并不是一定是n<=m，因为这个做错一次，所以做题时候要细心注意细节条件。一些没有提到的条件要想到。

解题代码：

#include<iostream>
using namespace std;
int t3n1(int n){
	int num=1;
	while(n!=1){
		if(n%2)
			n=3*n+1;
		else
			n=n/2;
		num++;
	}
	return num;
}
int work(int n,int m){
	int max=0,tmp;
	for(int i=n;i<=m;i++)
		if(max<(tmp=t3n1(i)))
			max=tmp;
	}
	return max;
}
int main(){
	int n,m;
	while(cin>>n>>m){
		if(n>m){
			cout<<n<<' '<<m<<' '<<work(m,n)<<endl;
		}
		else
			cout<<n<<' '<<m<<' '<<work(n,m)<<endl;
	}
	return 0;
}

扩展知识：http://www.equn.com/3x+1/

• 全局相关文章
• 相关文章