cycle length of n
consider the following algorithm :
if n = 1 then STOP
if n is odd then 
else 
Given the input 22, the following sequence of numbers will be printed
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is
printed) for any integral
input value.
Given an input n, it is possible to determine
the number of numbers printed (including
the 1). For a given n this is
called the cycle-length of n. In the example above, the cycle
length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle
length over all numbers between i and
j.
Sample Input (1<n<1000000)
1 10
100 200
201 210
900 1000
Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174
sir plz tell the approach
ReplyDeleteI can't think of anything except brute-force.
plzz help ??
@above if you will see the pattern you will find that you don't need to recompute values for all n.
ReplyDeleteplease see the code below
#include
#include
using namespace std;
typedef unsigned int uint;
typedef unsigned short ushort;
#define SIZE 1000001
static unsigned short table[SIZE];
ushort print(uint n)
{
if(n < SIZE && table[n])
return table[n];
if(n & 1)
{
if( n < SIZE)
{
table[n] = 2 + print( (3*n+1) >> 1 );
return table[n];
}
else
{
return 2 + print( (3*n+1) >> 1 );
}
}
else
{
if( n < SIZE)
{
table[n] = 1 + print( n >> 1 );
return table[n];
}
else
{
return 1 + print( n >> 1 );
}
}
}
int main()
{
//read and write inputs and outputs to file
freopen("INPUT","r",stdin);
freopen("OUTPUT","w",stdout);
uint x,y,i;
ushort max_count=0,count=0;
table[1] = 1;
while(cin>>x>>y)
{
max_count = 0;
if(x < y)
{
for(i=x;i<=y;i++)
{
count = print(i);
if (count > max_count)
max_count = count;
}
}
else
{
for(i=y;i<=x;i++)
{
count = print(i);
if (count > max_count)
max_count = count;
}
}
cout<<x<<" "<<y<<" "<<max_count<<endl;
}
return 0;
}