Thursday, August 19, 2010

ACM - UVA 100 - The 3n + 1 problem

The problem:100 - The 3n + 1 problem
The solution: using C++
Hints: http://www.algorithmist.com/index.php/UVa_100
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <utility>
#include <set>
#include <math.h>
using namespace std;

#define SIZE 1000001

static unsigned short table[SIZE];

unsigned short calcCycleLength( register unsigned long n )
{
        if(n < SIZE && table[n])
                return table[n];
        if(n & 1)
        { /* if n is odd */
                 if( n < SIZE)
                 {
                         /* calc two steps at one */
                         table[n] = 2 + calcCycleLength( (3*n+1) >> 1 );
                         return table[n];
                 }
                 else
                 {
                          return 2 + calcCycleLength( (3*n+1) >> 1 );
                  }
         }
         else
        {
                  if( n < SIZE)
                 {
                          table[n] = 1 + calcCycleLength( n >> 1 ); /* n/2 */
                          return table[n];
                 }
                 else
                 {
                          return 1 + calcCycleLength( n >> 1 );
                  }
        }
}

int main()
{
        unsigned long fn = 0;
        unsigned long sn = 0;
        unsigned long i;
        short out = 0, temp;
        table[1] = 1;
        while(cin>>fn>>sn)
        {
                 if( fn > sn)
                {
                        for( i = sn; i <= fn; ++i )
                        {
                                 temp = calcCycleLength( i );
                                 if( temp > out)
                                         out = temp;
                         }
                }
                else
                {
                        for( i = fn; i <= sn; ++i )
                       {
                                temp = calcCycleLength( i );
                                if( temp > out)
                                        out = temp;
                        }
                }
                cout<< fn<<" "<< sn<<" "<< out<<endl;
                out = 0;
        }
        return 0;
}

No comments:

Post a Comment