UVA 100: The 3n + 1 problem

Jasonlin posted @ 2011年3月25日 13:37 in UVA , 1853 阅读

题目链接: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/

 

 

  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter