iT邦幫忙

2021 iThome 鐵人賽

DAY 17
0
自我挑戰組

用 C & C++ 帶你手把手解 UVa 一顆星選集系列 第 17

Day 0x11 UVa100 The 3n + 1 problem

題意

  • 輸入兩整數,根據演算法輸出最大的 cycle length
  • 需要注意的有:
    1. 演算法
      1. input n
      2. print n
      3. if n = 1 then STOP
      4.     if n is odd then n ← 3n + 1
      5.     else n ← n/2
      6. GOTO 2
      
    2. cycle length
      • 根據演算法,紀錄共跑幾次迴圈使得 n == 1

解法

  • 按照題目要求,先用 while 讀入兩整數,並用 if 讓 i ≦ j,再把虛擬碼轉成 C 就行,如果有遇到更大值就更新
  • C code
    #include<stdio.h>
    
    void compare(int *a, int *b){
    
        int temp;
    
        if(*a > *b){
            temp = *a;
            *a = *b;
            *b = temp;
        }
    }
    
    int main(){
    
        int i, j;
        int n;
    
        while(scanf("%d %d", &i, &j) != EOF){
    
            printf("%d %d ", i, j);
    
            compare(&i, &j);            //let i < j
    
            int max = 0;
    
            while(i <= j){
    
                int count = 1;
                n = i;
    
                while(n != 1){
                    if(n % 2 == 1){     //odd
                        n = 3 * n + 1;  
                    }                   
                    else{               //even
                        n = n / 2;
                    }
                    count++;            //count the length
                }
    
                i++;
    
                if(count > max){
                    max = count;        //update max length
                }
            }
    
            printf("%d\n", max);
        }
    
        return 0;
    }
    

上一篇
Day 0x10 UVa10057 A mid-summer nights dream
下一篇
Day 0x12 UVa10038 Jolly Jumpers
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言