Quiz 09
===
# [A]
## Description
The properties of integer values have been studied for centuries in number theory. Two important concepts developed are the greatest common divisor (GCD), and least common multiple (LCM).
Given two integers 𝑥 and 𝑦. The GCD is defined as the largest integer value which can divide both 𝑥 and 𝑦, while the LCM is defined as the smallest integer value which can be divided by both 𝑥 and 𝑦.

A special properties among 𝑥, 𝑦, and their GCD, and LCM is
𝑥𝑦 = 𝐺𝐶𝐷(𝑥,𝑦) × 𝐿𝐶𝑀(𝑥,𝑦)

To determine the values of GCD and LCM, we can first calculate the value of GCD by using the Euclid's algorithm:
\begin{cases}
𝐺𝐶𝐷(𝑥,𝑦) = 𝐺𝐶𝐷(𝑦,𝑥\;mod\;𝑦)\\
𝐺𝐶𝐷(𝑥,0) = 𝑥\\
\end{cases}

After the value of GCD is determined, the value of LCM can be obtained:
$𝐿𝐶𝑀(𝑥,𝑦) = \frac{𝑥𝑦}{𝐺𝐶𝐷(𝑥, 𝑦)}$

GCD and LCM can be used to quickly calculate the sum of two fractions, e.g. $\frac{1}{6} + \frac{5}{8} = \frac{1∗4}{6*4} + \frac{5∗3}{8*3} = \frac{4}{24} + \frac{15}{24} = \frac{19}{24}$,
where 24 is the LCM of 6 and 8. Note that if the numerator and denominator have common factors, we have divide them by their GCD. Write a program to calculate the sum of two fractions via GCD and LCM. You have to follow the steps mentioned above and wrap the calculation of GCD and LCM into two functions.

**Input**
The input contains several cases and ends with EOF. Each case contains four integer values, which in turn represent the numerator of first fraction, denominator of the first fraction, numerator of the second fraction, and denominator of the second fraction.

**Output**
For each case, output the sum of the two fractions according to the format given in the sample output.

**Example**
| input | output |
|:---------:|:-----------------:|
| 1 2 3 4 | 1/2 + 3/4 = 5/4 |
| -1 2 -3 4 | -1/2 - 3/4 = -5/4 |

## Solution
做分數的加減法時，首先要將分數通分，也就是將兩個分母轉為其最小公倍數，即使用LCD(分母1, 分母2)獲得。
轉換分數的分子分母時，兩者需同乘除一個數，而此數為$\frac{LCD}{分母}$。

最終計算結果為
\begin{cases}
分子：分子1\times\frac{LCD}{分母1}\ +\ 分子2\times\frac{LCD}{分母2}\\
分母：LCD\\
\end{cases}

計算完成後，須將此分數約至最簡。
將計算結果的分子及分母同除以它們的最大公因數，即可獲得答案。

## Code

#include <stdio.h>

int GCD(int x, int y);
int LCM(int x, int y);

int main(){
    int numer1, denom1, numer2, denom2;
    int numer, denom, gcd; //the numerator, denominator, gcd of result

    while(scanf("%d %d %d %d", &numer1, &denom1, &numer2, &denom2) != EOF){
        denom = LCM(denom1, denom2);
        numer = numer1 * (denom / denom1) + numer2 * (denom / denom2);

        if(numer < 0){
            gcd = GCD(numer * (-1), denom);
        }
        else{
            gcd = GCD(numer, denom);
        }

        if(gcd != 1){
            numer /= gcd;
            denom /= gcd;
        }

        if(numer2 > 0){
            printf("%d/%d + %d/%d = %d/%d\n", numer1, denom1, numer2, denom2, numer, denom);
        }
        else{
            printf("%d/%d - %d/%d = %d/%d\n", numer1, denom1, numer2 * (-1), denom2, numer, denom);
        }
    } 
    return 0;
}

int GCD(int x, int y){
    if(x%y == 0){
        return y;
    }

    return GCD(y, x%y);
}

int LCM(int x, int y){
    return (x * y) / GCD(x, y);
}

# [B]
## Description
Hanoi tower is a basic problem for knowing the power of divide-and-conquer method, and recursive function. In the Hanoi tower problem, the priest wants to move the stack from the first peg to the third peg through one temporary peg, the second peg. The rule of Hanoi tower problem is simple, including:
1. Each time we can only move one disk.
2. At any time, a larger disk cannot put on a smaller one.

Now that consider a variation that each time we can and we must if we can move a maximum of two disks.
Your goal is to write a program to show how to solve the variation of Hanoi tower problem with n disks step by step. You have to use recursive function to build your solution.

**Input**
The input has several cases and ends with EOF. Each case contains a number which represent the number of disks.

**Output**
For each case, output the steps to solve the variation of Hanoi tower problem. Add a newline between any two consecutive cases.

**Example**

## Solution

## Code

#include <stdio.h>

void hanoi(int disk1, int disk2, int prev, int tmp, int target);

int main(){
    int disks;

    while(scanf("%d", &disks) != EOF){
        hanoi(disks, disks-1, 1, 2, 3);
        puts("");
    }

    return 0;
}

void hanoi(int disk1, int disk2, int prev, int tmp, int target){
    if(disk2 == 0){
        printf("Move disk %d from %d to %d\n", disk1, prev, target);
        return;
    }
    else if(disk2 == 1){
        printf("Move disks %d and %d from %d to %d\n", disk2, disk1, prev, target);
        return;
    }

    if(disk1 % 2){
        hanoi(disk1-1, disk2-1, prev, target, tmp);
        printf("Move disk %d from %d to %d\n", disk1, prev, target);
        hanoi(disk1-1, disk2-1, tmp, prev, target);
    }
    else{
        hanoi(disk1-2, disk2-2, prev, target, tmp);
        printf("Move disks %d and %d from %d to %d\n", disk2, disk1, prev, target);
        hanoi(disk1-2, disk2-2, tmp, prev, target);
    }
}

# [C]
## Description
Factorial is a common example to show the recursion. The recursive equation for factorial can be given as follows:
\begin{cases}
𝑎_𝑛 = 𝑛𝑎_{𝑛-1}\\
𝑎_1 = 1\\
\end{cases}
However, it is easily to exceed the maximum value of integer in C as the factorial number increases rapidly. To overcome this circumstance, a simplest remedy is to use multiple integers for representing a single factorial number. An integer of type unsigned int can be used to represent 8 digits, and therefore five integers can be used to represent a value with maximum 40 digits.
Write a program which is able to show factorial numbers up to 40th (𝑎40). The calculation of factorial number should be in a recursive function. There is no point if you didn’t use recursive function.

**Input**
The input has several cases and with EOF. Each case contains a number 𝑥.
**Output**
For each case, output the xth factorial number in the following format: “The xth factorial number is y.”
For the representation of y, please add a space for every eight digits.

**Example**
| input | output |
|:-----:|:----------------------------------------------------------------------------------- |
| 1 | The 1st factorial number is 1. |
| 2 | The 2nd factorial number is 2. |
| 3 | The 3rd factorial number is 6. |
| 4 | The 4th factorial number is 24. |
| 40 | The 40th factorial number is 81591528 32478977 34345611 26959611 58942720 00000000. |

## Solution
當輸入值 $x$ 為 $40$ 時，其值太大，即使是用`unsigned long long int`都沒有辦法儲存，因此此題需要將數值切割，依據題目要求，每 $8$ 個數字存為一個值。

根據題目要求，在此使用長度為 $8$，型態為`unsigned int`的陣列`result`來儲存所有的數字。
註：`int`的範圍小於$\overbrace{99\cdots99}^{8}$，且欲存的數值皆為正數，因此在此使用`unsigned int`作為資料型態

首先，每次輸入一個新數字都需要將`result`初始化，也就是將前 $5$ 格設為0, 最後一格設為 $1$，其意義代表將結果這個變數預設為1，之後將對此變數做乘法。

接下來將說明將如何對`result`做乘法。
可將此數視為base $10^8$ 的數，類似題目可參考[Quiz 04 [B]](https://hackmd.io/@nnyjan02426/cp1_quiz04#B-Adder)
先設兩個變數：
1. `tmp_result`：用於儲存每格乘法後得出的結果，因乘出來的數長度超過`int`的範圍，且其值皆為正數，因此使用`unsigned int`
2. `carry`：用於存取將「進位」至下一格的數值，其值預設為0

接著從最後一格開始，將那格的值乘以`n`並加上`carry`，存至於`tmp_result`。
`tmp_result`的後8個數字將存入`result`中，也就是剛剛取出值的那一格，而其他數字將暫存至`carry`。
以上步驟將重複執行6次（對`result`的每一格做加、乘）。

再來便是遞迴，遞迴需要base case 以及 recursive case
1. factorial的base case 為$1! = 1$，因此當n為1時，不執行recursive case，直接`return`
2. factorial的recursive case 為$n! = n\times (n-1)!$，先利用函式factorial計算出$(n-1)$並將結果存至`result`中，接著再乘以n，其計算結果即為所求

## Code

#include <stdio.h>
#define SIZE 6

void factorial(int n, unsigned int arr[], size_t arr_size);

int main(){
    int x; //input
    unsigned int result[SIZE]; //to store result
    int printed;

    while(scanf("%d", &x) != EOF){
        printed = 0;
        //initialize array
        for(int i=0; i<SIZE; i++){
            result[i] = 0;
        }
        result[SIZE-1] = 1;

        factorial(x, result, SIZE);

        //output
        if(x == 1){
            printf("The 1st factorial number is %u.\n", result[5]);
        }
        else if(x == 2){
            printf("The 2nd factorial number is %d.\n", result[5]);
        }
        else if(x == 3){
            printf("The 3rd factorial number is %d.\n", result[5]);
        }
        else{
            printf("The %dth factorial number is", x);
            for(size_t i=0; i<SIZE; i++){
                if(!printed && result[i]){
                    printf(" %u", result[i]);
                    printed = 1;
                }
                else if(printed){
                    printf(" %08u", result[i]);
                }
            }
                puts(".");
        }
    }

    return 0;
}

void factorial(int n, unsigned int arr[], size_t arr_size){
    if(n == 1){
        return;
    }

    unsigned int tmp_result;
    int carry = 0;

    factorial(n-1, arr, arr_size);
    for(int i=arr_size-1; i>=0; i--){
        tmp_result = (arr[i] * n) + carry;
        arr[i] = tmp_result % 100000000;
        carry = tmp_result / 100000000;
    }

    return;
}

###### tags: `程設一quiz`