POJ 1207 The 3n + 1 problem

题目链接：http://poj.org/problem?id=1207

题目大意：给你一个数x，规定一个函数F(x)，如果x为1则F(x)==1，否则如果x是偶数，F(x)==F(x/2)，x为奇数F(x)==F(3*x+1)计算给定x到变换到1的步数。

注意点：

1.提供的每组两个数字不一定是左边小右边大，所以可能要交换两者的值，另外，输出时必须要按两个数出现的顺序输出

或者可以，先输出两个数，最后输出maxlen的值，保证在同一行即可

2.直接枚举比较也是可以通过的，打表同样是可以的，因为数据范围不是很大

3.其他的还有深搜法，记忆法什么的，参考网址：http://hi.baidu.com/wzyjerry/blog/item/f7c1e44481ced42586947347.html     深搜+记忆化

方法一：直接枚举

Memory: 3004K
Time: 204MS

import java.util.Scanner;public class Main{public static void main(String[] args) {Scanner sin=new Scanner(System.in);int start,end,len,maxlen,temp;while(sin.hasNext()){maxlen=0;temp=0;start=sin.nextInt();end=sin.nextInt();if(start>end){temp=end;end=start;start=temp;}for(int i=start;i<=end;i++){len=calculateLen(i);if(len>maxlen){maxlen=len;}}if(temp==0){System.out.println(start+" "+end+" "+(maxlen));}else{System.out.println(end+" "+start+" "+(maxlen));}}}public static int calculateLen(int n){int len=1;while(n!=1){if(n%2==0){n=n/2;}else{n=3*n+1;}len++;}return len;}
}

方法二：打表

Memory: 3044K
Time: 172MS

import java.util.Scanner;public class Main{public static int[] lens=new int[10002];public static void main(String[] args) {Scanner sin=new Scanner(System.in);calculateLen();int start,end,maxlen,temp;while(sin.hasNext()){maxlen=0;temp=0;start=sin.nextInt();end=sin.nextInt();if(start>end){temp=end;end=start;start=temp;}for(int i=start;i<=end;i++){if(lens[i]>maxlen){maxlen=lens[i];}}if(temp==0){System.out.println(start+" "+end+" "+(maxlen+1));//注意这里的括号()，不能少，不然会出现问题，将1看作了一个字符}else{System.out.println(end+" "+start+" "+(maxlen+1));}}}public static void calculateLen(){int i,n;for(i=1;i<10002;i++){lens[i]=0;n=i;while(n!=1){if(n%2==0){n=n/2;}else{n=3*n+1;}lens[i]++;}}}
}

方法三：深搜+记忆优化

Memory: 1024K
Time: 0MS

#include <iostream>
#include <string.h>
using namespace std;
int M[200001];
int Ans;
int dfs(int n)
{if(n==1)return 1;if(n>200000){if(n%2==0)return dfs(n/2)+1;//这里就是深搜，此处向下递归了一层，后面加上 1elsereturn dfs(n*3+1)+1;}if(!M[n])//判断是否已经求过n的长度，如果没有的话就去求，否则直接返回上次求得的值[记忆]{if(n%2==0)return M[n]=dfs(n/2)+1;elsereturn M[n]=dfs(n*3+1)+1;}elsereturn M[n];
}
int main()
{int a,b;M[0]=1;for(int i=1; i<=10000; i++){M[i]=dfs(i);//这里实际上就是打表，但是它主要的目的是保存那些频繁计算的数的长度}while(cin >> a >> b){cout << a << ' ' << b << ' ';Ans=0;for(int i=min(a,b); i<=max(a,b); i++)Ans=max(Ans,M[i]);cout << Ans << endl;}return 0;
}