100 - The 3n + 1問題
http://www.spoj.com/problems/PROBTRES/
常に私はこれを取得します >>> ランタイム エラー (SIGSEGV) <<< なぜ plz ヘルプ !
背景: コンピュータ サイエンスの問題は、特定の種類の問題 (例: 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 です。
任意の 2 つの数値 i と j について、i と j の間のすべての数値の最大サイクル長を決定する必要があります。
入力: 入力は、一連の整数 i と j のペアで構成され、1 行に 1 つの整数ペアが含まれます。すべての整数は 1,000,000 未満で 0 より大きくなります。
整数のすべてのペアを処理し、各ペアについて、i と j を含むすべての整数の最大サイクル長を決定する必要があります。
32 ビット整数をオーバーフローする演算はないと想定できます。
出力: 入力整数 i と j の各ペアに対して、i、j、および i と j を含む整数の最大サイクル長を出力する必要があります。これらの 3 つの数値は、少なくとも 1 つのスペースで区切られ、3 つの数値すべてが 1 行に表示され、入力行ごとに 1 行の出力が表示されます。整数 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 );
}
}