____________________________________________________________________
Question: 3n + 1 problem
____________________________________________________________________
#include "iostream.h"____________________________________________________________________
int cyclen[1000001];
int findCycleLength(int num) {
int l = 0, index = num;
long long n = num;
if(cyclen[n] != 0) return cyclen[n];
while(n != 1) {
if(n <= 1000000) if(cyclen[n] != 0 ) return cyclen[index] = l + cyclen[n];
if(n % 2 == 0) n/= 2;
else n = 3 * n + 1;
l++;
}
return cyclen[index] = l + 1;
}
int main()
{
int i,j;
while(true) {
cin >> i >> j;
if(cin.eof()) break;
int min = (i < j)? i : j;
int max = (i > j)? i : j;
int maxlen = 0,len;
for(int k = 0; k <= 1000000; k++) cyclen[k] = 0;
for(int k = min; k <= max; k++) if((len = findCycleLength(k)) > maxlen) maxlen = len;
cout << i << " " << j << " " << maxlen << endl;
}
return 0;
}
No comments:
Post a Comment