100 - The 3n + 1
问题
http://www.spoj.com/problems/PROBTRES/
我总是得到这个 >>> 运行时错误(SIGSEGV)<<< 为什么请帮忙!
背景:计算机科学中的问题通常被归类为属于某一类问题(例如,NP、不可解、递归)。在这个问题中,您将分析一个算法的属性,该算法的分类对于所有可能的输入都是未知的。
问题:
考虑以下算法:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n = 3n + 1
5. else n = n / 2
6. GOTO 2
给定输入 22,将打印以下数字序列22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
据推测,对于任何整数输入值,上述算法将终止(当打印 1 时)。尽管算法很简单,但这个猜想是否正确尚不清楚。然而,已经验证了对于所有整数 n 使得0 < n < 1,000,000
(并且,事实上,对于比这更多的数字。)
给定输入 n,可以确定打印的数字数量(包括 1)。对于给定的 n,这称为 n 的周期长度。在上面的例子中,循环长度 22 是 16。
对于任何两个数字 i 和 j,你要确定 i 和 j 之间所有数字的最大循环长度。
输入:输入将由一系列整数对 i 和 j 组成,每行一对整数。所有整数都将小于 1,000,000 且大于 0。
您应该处理所有整数对,并为每对确定 i 和 j 之间(包括 i 和 j)之间所有整数的最大循环长度。
您可以假设没有任何操作会溢出 32 位整数。
输出:对于每对输入整数 i 和 j,您应该输出 i、j 以及介于 i 和 j 之间且包括 i 和 j 的整数的最大循环长度。这三个数字应至少用一个空格隔开,所有三个数字都在一行,每行输入对应一行输出。整数 i 和 j 必须按照它们在输入中出现的顺序出现在输出中,并且后面应该是最大循环长度(在同一行上)。
Sample Input:
1 10
100 200
201 210
900 1000
Sample Output:
1 10 20
100 200 125
201 210 89
900 1000 174
#include <iostream>
using namespace std ;
long int a[1000001];
long int F (long int n){
if(a[n]!=0)
return a[n];
else {
if(n%2 !=0)
a[n]=F(n*3+1)+1 ;
else
a[n]=F(n/2)+1 ;
return a[n];
}
}
int main(){
a[1]= 1 ;
long int i , j , MX , MN , x=0 ;
while (cin>>i >> j ){
MX=max(i,j);
MN=min(i,j);
for(;MN<=MX;MN++){
if(x<F(MN))
x=F(MN) ;
}
cout<<i<<" "<<j<<" "<<x<<endl;
x= 0;
}
return 0 ;
}
这和我的代码有什么区别?!!!
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000001
static int result[MAX];
int calculate(unsigned long i);
int main()
{
unsigned long int i = 0;
unsigned long int j = 0;
unsigned long int k = 0;
int max,x,y;
result[1] = result[0] = 1;
while (scanf("%ld",&i)!= EOF)
{
scanf("%ld",&j);
if (i > j)
{
x = i;
y = j;
}
else
{
x = j;
y = i;
}
max = 0;
for (k = y; k <= x; k++)
{
if (result[k] != 0 && result[k] > max)
max = result[k];
else if (calculate(k) > max)
max = result[k];
}
printf("%ld %\ld %d\n",i,j,max);
}
return 0;
}
int calculate(unsigned long i)
{
if (i < MAX && result[i])
return result[i];
if ( i % 2 == 1 )
{
if (i < MAX)
return result[i] = 2+calculate((3*i+1)/2);
else
return 2+calculate((3*i+1)/2);
}
else
{
if( i < MAX)
return result[i] = 1 + calculate(i / 2);
else
return 1 + calculate(i /2 );
}
}