iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
自我挑戰組

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

Day 0x7 UVa11417 GCD

題意

  • 輸入一數字 N,根據定義輸出結果 G
  • 需要注意的點有:
    1. 重複輸入
    2. 讀到 0 就結束程式
    3. G 的定義
      • 題目都直接給 code 了,就拿來 參考吧
        G=0;
        for(i=1;i<N;i++)
        for(j=i+1;j<=N;j++)
        {
        G+=GCD(i,j);
        }
        /*Here GCD() is a function that finds
        the greatest common divisor of the two
        input numbers*/
        

解法

  • 參考之前,一樣先把重複輸入架構寫好
    int N;
    
    while(scanf("%d", &N)){
        if(N == 0){
            break;
        }
        else{
            ...
        }
    }
    
  • 開始 參考,因為根據定義 G 是用 Σ 疊加,所以每筆測資都要記得先初始化 G = 0
    else{
    
        G = 0;
    
        for(i = 1; i < N; i++){
            for(j = i + 1; j <= N; j++){
                G = G + GCD(i, j);
            }
        }
    
        printf("%d\n", G);
    }
    
  • 本題最精華之部分 - 最大公因數,這邊使用遞迴的輾轉相除法版本,至於什麼是輾轉相除法,我們一樣交給專業的來解釋
    int GCD(int a, int b){
        if(b == 0){
            return a;
        }
        else{
            GCD(b, a % b);
        }
    }
    
  • 用三元運算子可以寫成邪教般的一行版
    int GCD(int a, int b){
        return b == 0 ? a : GCD(b, a % b);
    }
    
  • C code
    #include<stdio.h>
    
    int GCD(int a, int b){
        return b == 0 ? a : GCD(b, a % b);
    }
    
    int main(){
    
        int G;
        int N;
        int i, j;
    
        while(scanf("%d", &N)){
            if(N == 0){
                break;
            }
            else{
    
                G = 0;
    
                for(i = 1; i < N; i++){
                    for(j = i + 1; j <= N; j++){
                        G = G + GCD(i, j);
                    }
                }
    
                printf("%d\n", G);
            }
        }
    
        return 0;
    }
    

討論

  • 最後分享一下,假如各位在練習這題,可能會查其他寫法,剛剛碰巧看到這篇 Misster Hao's Blog - 【CPE】UVA 11417 GCD 一顆星 by C++,裡面有提到:

    比較要注意的是我有多加一個判斷是當 a ==0 時也回傳0
    但是我記得n和0的GCD就是n呀(?)
    我加上這個判斷才AC(???)

  • 挖馬母災數學上 0 和 N 的最大公因數應該要是多少,但是這題因為 G 的定義寫得很清楚,從 i = 1 開始,所以如果寫成 i = 0 開始,這圈 G 的值都不能更新,而且會導致內層多跑 N 圈
  • 這位作者可能不像我 參考題目的 code,是自己手打,所以沒注意到這點,不過能發現問題出在哪,然後嘗試找出解決辦法我覺得很厲害

上一篇
Day 0x6 UVa10008 What's Cryptanalysis?
下一篇
Day 0x8 UVa10193 All You Need Is Love
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言