tags: tgirc早修book

Ch.07 題目練習

副程式

題目
副程式基本沒啥特別的練習題，不過如果想練習寫副程式，可以把程式中時常重複出現的部分，試著提出來另外寫成一組副程式。

編者個人認為副程式這塊除了練習，更重要的是「判斷哪幾段程式可以提出來另外寫」，適時的使用副程式，可以很有效的簡化程式碼。

1. 最大值
2. 絕對值
3. 最大公因數
4. 交換變數
5. Toj 170 / 各種星星樹
6. Kattis DRM Messages

題解

1. 最大值

   回傳兩者中比較大的那個，如果 a > b 就回傳 a ，反之回傳 b

int maximum(int a, int b){
    if(a > b){
        return a;
    }
    else{
        return b;
    }
}

2. 絕對值

   n 小於 0 時回傳 -n，否則直接回傳 n

int abs(int n){
    if(n >= 0){
        return n;
    }
    else{
        return -n;
    }
}

3. 最大公因數

   以輾轉相除法的方式去實作，每次讓 a 與 b 交換並取餘數。
   直到其中一個取餘數為 0 時，就回傳另一個。

int GCD(int a, int b){
    if(b != 0){
        return GCD(b, a%b);
    }
    else{
        return a;
    }
}

4. 交換變數

   此處有用到 參照 的觀念。
   建議可以閱讀補充的 指標與位址

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

5. Toj 170 / 各種星星樹
   （待補）

遞迴

題目

1. GCD 最大公因數
   輸入 a 和 b，求兩者間的最大公因數

2. 平方和
   由 1 至 n 的平方和，前幾項如下：

   f(1) = 1²
   f(2) = 1² + 2²
   f(3) = 1² + 2² + 3²
   f(4) = 1² + 2² + 3² + 4²

   輸入 n，求 1 至 n 的平方和

3. Zerojudge c002: 10696 - f91
4. Zerojudge e357: 遞迴函數練習
5. Zerojudge c813: 11332 - Summing Digits
6. Zerojudge d672: 10922 - 2 the 9s
7. Zerojudge d487: Order's computation process

題解

1. GCD 最大公因數

int GCD(int a, int b){
    if( b == 0 ) return a;
    else         return GCD(b, a%b);
}

2. 平方和

int f(int n){
    if( n == 1 ) return 1;
    else         return n * f(n-1);
}

3. Zerojudge c002: 10696 - f91

int f91(int n){
	if( n <= 100 ) return f91( f91(n+11) );
	else return n-10;
}

4. Zerojudge e357: 遞迴函數練習

int f(int x){
    
    if( x%2 == 0 ) return f(x/2);
    else           return f(x-1) + f(x+1);
}

5. Zerojudge c813: 11332 - Summing Digits

int G(int n){
	int sum=0;
    
	while( n!=0 ){
		sum += n%10;
		n /= 10;
	}
    
	if( sum<10 ) return sum;
	else         return G(sum);
}

6. Zerojudge d672: 10922 - 2 the 9s

（待補）