pc110101 The 3n+1 problem
The 3n+1 problem
Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22:
It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.
For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, includingboth endpoints.
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.
Output
For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input.
Sample input
1 10
100 200
201 210
900 1000
Sample output
1 10 20
100 200 125
201 210 89
900 1000 174
题意：输入两个整数 a , b ；输出 a 、 b 间循环节的最大值
循环节定义 n 如果 n 为偶数，则 n = n/2; 如果 n 为基数，则 n = 3*n + 1 ；直到 n == 1；
算法分析：这个题是用暴力过的，自己的优化是打表，速度其实蛮快的，就是 W A ，真郁闷!!到现在还没过！！就更郁闷了！！！
代码：
暴力发：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int i,a,b,ans,s;
__int64 t;
while(cin>>a>>b)
{
bool yes=false;
if(a>b)
{
int c;
c=a;a=b;b=c;
yes=true;
}
ans=0;
for(i=a;i<=b;i++)
{
s=1;t=i;
while(t!=1)
{
if(t%2==0) t=t/2;
else t=t*3+1;
s++;
}
if(ans<s) ans=s;
}
if(!yes) cout<<a<<" "<<b<<" "<<ans<<endl;
else cout<<b<<" "<<a<<" "<<ans<<endl;
}
return 0;
}
打表法：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000010
using namespace std;
int r[N];
void Init()
{
r[0]=0;r[1]=1;
long long int t;
int i,s;
for(i=1;i<N;i++)
{
t=i;s=0;
while(t!=1)
{
if(t%2==0)
{
t=t/2;
s++;
if(i>t)
{
r[i]=s+r[t]; //打表的优化在此
break;
}
}
else
{
t=t*3+1;
s++;
}
}
}
}
int main()
{
Init();
int i,s;
int ans,a,b;
bool yes=false;
while(cin>>a>>b)
{
if(a>b)
{
int t;
t=a;a=b;b=t;
yes=true;
}
ans=0;
for(i=a;i<=b;i++)
if(ans<r[i])
{
ans=r[i];
}
if(!yes) cout<<a<<" "<<b<<" "<<ans<<endl;
else cout<<b<<" "<<a<<" "<<ans<<endl;
}
return 0;
}
优质内容筛选与推荐>>
1、CSS之新闻列表
2、链表
3、java-Enumeration，单向队列Queue及双向队列Deque等容器简单使用
4、xapian搜索系统存储结构解读
5、【Delphi】编写DLL(以及静态和动态方式调用)