본문 바로가기

Studies/Programming Challenges (알고리즘 트레이닝 북)

문제 1. 3n+1 문제(The 3n+1 Problem)

// Written by rinehart

// rinehart@naver.com

//2007. 6. 1

/* Note : About 110,000 times tries, the program freezed. I don't know why. Maybe the windows OS can't support too much loop or function calls. */

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

#define MAX_INPUT   1000000
#define MIN_INPUT   1

 

int Get_Numbers(int *input_a, int *input_b);
int Get_Cycle(int x);

 

int main()
{
    int v_input_a, v_input_b, v_input_temp;
    int v_Max_counter = 0, v_Temp_counter = 0;
   
    if (Get_Numbers(&v_input_a, &v_input_b))
        return 0;   // Error   
   
    v_input_temp = v_input_a;
   
    while (v_input_temp <= v_input_b)
    {
        v_Temp_counter = Get_Cycle(v_input_temp);
        printf (";%d", v_input_temp);   // Progress
       
        if (v_Max_counter < v_Temp_counter)
            v_Max_counter = v_Temp_counter;
       
        v_input_temp++;
    }
   
    printf ("\n\n%d %d %d\n", v_input_a, v_input_b, v_Max_counter);
   
    return 0;
}

int Get_Numbers(int *input_a, int *input_b)
{
    char buf[80];
    char *token;
    int v_err = 0;
   
    *input_a = 0;   *input_b = 0;   // Init
   
    printf ("Input 2 numbers (%d ~ %d)\n", MIN_INPUT, MAX_INPUT);
   
    gets(buf);
    token = strtok(buf, " \n");
    if (token)
        *input_a = atoi(token);
    else
        v_err = 1;
   
    token = strtok(NULL, " \n");
    if (token)
        *input_b = atoi(token);
    else
        v_err = 1;
   
    if (*input_a > *input_b)
        v_err = 1;
    else if (*input_a < MIN_INPUT || *input_a > MAX_INPUT)
        v_err = 1;
    else if (*input_b < MIN_INPUT || *input_b > MAX_INPUT)
        v_err = 1;
   
    if (v_err)  //later, seperate error cases
        printf ("ERROR : Wrong Number\n\n");
   
    return v_err;
}

int Get_Cycle(int x)
{
    int counter = 1;
   
    while(x != 1)
    {
        if (x%2)    //Odd number
            x = (x*3)+1;
        else        //Even number
            x = x/2;
       
        counter++;
    }
   
    return counter;
}