[UVa] 100  - The 3n + 1 problem

uva_100.cpp

// idea: make table, record value have been computed

#include <stdio.h>
#include <string.h>

#define N 1000001

int cycle_length[N];

int get_cycle_length(int i){
    if(i < N){
        if(cycle_length[i] != 0)
            return cycle_length[i];
        else
            return cycle_length[i] = (i % 2 != 0? get_cycle_length(i * 3 + 1) : get_cycle_length(i / 2)) + 1;
    }
    else
        return (i % 2 != 0? get_cycle_length(i * 3 + 1) : get_cycle_length(i / 2)) + 1;
}

int main(){
    int i, j, a, b, n, max_n;

    memset(cycle_length, 0, N * sizeof(int)); // all bytes to zero
    for(i = 1, j = 1; i < N; i <<= 1, ++j)
        cycle_length[i] = j;

    while(scanf("%d%d", &i, &j) != EOF){
        if(i <= j)  a = i, b = j;
        else        a = j, b = i;
        for(max_n = 0; a <= b; ++a)
            if((n = get_cycle_length(a)) > max_n)
                max_n = n;
        printf("%d %d %d\n", i, j, max_n);
    }

    return 0;
}