---
# System prepended metadata

title: 程式設計Ⅰ【筆記Ⅱ】
tags: [Programming]

---

**程式設計Ⅰ【筆記Ⅱ】**
===
* [name=Ivy Lin]
* [筆記1](https://hackmd.io/NPFilj4fSNu020tfh5s3TQ)
* [筆記3](https://hackmd.io/bvpG9TeaSTa5Y9cQGVWKaw)

## 第九週<2023.4.11>

### 遞迴(gcd)

:::info
歐幾里得演算法原理:
>A=B*q+R
>(A,B)=(B,R)

說明:
>將兩數相減(大減小)，直到一邊為0則另一邊剩餘的數及為兩數的最大公因數。
:::

```clike=
//程式_遞迴寫法
int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
```

### 擺皇后(西洋棋)
這題比較複雜，因此我們先從三個城堡問題開始。

#### **三個城堡(初階棋盤遞迴)**

* **敘述**
>城堡可以走十字，我們想在3*3的棋盤上擺上3個城堡
>請問有哪些擺法?

* **思路**
>1. 先放旗子
>2. 把不能放的地方刪掉
>3. 遞迴=>剩餘的地方擺放
>4. 停止點=>完整擺放

* **程式**
```clike=
#include <stdio.h>
// 城堡位置(1,1)~(3,3)
int board[5][5];

// 印出棋盤
void show_board()
{
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
            printf("%d", board[i][j]);
        printf("\n");
    }
    printf("\n");
}

// 判斷此位置能否放置城堡
int check(int row, int i)
{
    for (int j = 1; j < row; j++)
    {
        if (board[j][i])
            return 0;
    }
    return 1;
}

// 判斷現在要放第幾行
void place(int row)
{
    if (row > 3)
        show_board();
    else
    {
        for (int i = 1; i <= 3; i++)
        {
            if (check(row, i))
            {
                // 遞迴處!!!
                board[row][i] = 1;
                place(row + 1);
                // 這個步驟非常重要!!!(把城堡拿起來)
                board[row][i] = 0;
            }
        }
    }
}

int main()
{
    place(1);
    return 0;
}
```

:::danger
注意
>在這個程式中，最重要的部分其實是"把城堡拿起來"。
每次的遞迴，都是在執行"放下一行的城堡"
因此結束遞迴後，要"回復"上一階段的動作就需要"取消"你放城堡的動作。
:::







#### **擺放皇后(棋盤遞迴)**

* **敘述**
>皇后可以走米字，我們想在n*n的棋盤上擺上n個皇后
>請問有哪些擺法?

* **思路**
>1. 和城堡的思路一樣(但在檢查的地方要額外檢查斜線)
>2. 精簡紀錄的點=>不記錄行數，改成紀錄放置第幾格即可(可以有效簡化記錄的資料)
>3. 檢驗是否可放的函數記得要多檢查45度(斜上方的格子是否有被放置棋子)

* **程式**
```clike=
#include <stdio.h>
int board[20];
int ans;
// int place(int row, int size);
// int check(int row, int inde);

int place(int row, int size)
{
    // check if the row is equal to the size of the board
    //printf("place(row,size)=(%d,%d)\n", row, size);
    if (row == size)
        ans += 1;
    else
    {
        // place the queen
        for (int i = 0; i < size; i++)
        {
            // check (row,i) can place the queen or not
            //printf("check(row,inde)=(%d,%d)\n", row, i);
            if (check(row, i))
            {
                board[row] = i;
                place(row + 1, size);
            }
        }
    }
    return ans;
}

int check(int row, int inde)
{
    for (int i = 0; i < row; i++)
    {
        if (board[i] == inde || board[i] - inde == i - row || board[i] - inde == row - i)
        {
            //printf("can't put in (%d,%d)\n\n", row, inde);
            return 0;
        }
    }
    //printf("put in (%d,%d)\n\n", row, inde);
    return 1;
}

int main()
{
    int size;
    scanf("%d", &size);
    printf("%d\n", place(0, size));
    return 0;
}#include <stdio.h>
int board[20];
int ans;
// int place(int row, int size);
// int check(int row, int inde);

int place(int row, int size)
{
    // check if the row is equal to the size of the board
    //printf("place(row,size)=(%d,%d)\n", row, size);
    if (row == size)
        ans += 1;
    else
    {
        // place the queen
        for (int i = 0; i < size; i++)
        {
            // check (row,i) can place the queen or not
            //printf("check(row,inde)=(%d,%d)\n", row, i);
            if (check(row, i))
            {
                board[row] = i;
                place(row + 1, size);
            }
        }
    }
    return ans;
}

int check(int row, int inde)
{
    for (int i = 0; i < row; i++)
    {
        if (board[i] == inde || board[i] - inde == i - row || board[i] - inde == row - i)
        {
            //printf("can't put in (%d,%d)\n\n", row, inde);
            return 0;
        }
    }
    //printf("put in (%d,%d)\n\n", row, inde);
    return 1;
}

int main()
{
    int size;
    scanf("%d", &size);
    printf("%d\n", place(0, size));
    return 0;
}

```


#### **找錢問題**

* **敘述**
>輸入不同面值的銅板，然後輸入金額，將可能的找零方式列出

* **思路**
>1. 重複做的地方=>要選擇幾個面值銅板(可以有很多種配法)
>2. 遞迴=>考慮兩種可能
>(1) 使用1元=>錢變成M-1元
>(2) 不使用1=>考慮剩下的5和10元來湊
>3. 停止遞迴=>手上剩下0元、手邊剩下小於0元、沒有辦法湊了

* **程式**
```clike=
#include <stdio.h>
int count[10];
int number[10];
void change(int money, int inde, int total)
{
    // 檢查點1=>是否超過可用的面額種類
    if (inde < total)
    {
        // 檢查點2=>完成題目條件(money=0)
        if (money == 0)
            show(total);
        // 檢查點3=>money是否還可以找錢(小於0就爆掉QAQ)
        else if (money > 0)
        {
            // 遞迴處!!!
            // 第一種狀況=>使用大一個面額湊
            change(money, inde + 1, total);
            // 第二種狀況=>多使用一個同面額
            number[inde] += 1;
            change(money - count[inde], inde, total);
            number[inde] -= 1;
            // 記得要記得"拿起來"這個動作!!!
        }
    }
}

```
```clike=
void show(int total)
{
    printf("(%d", number[0]);
    for (int i = 1; i < total; i++)
        printf(",%d", number[i]);
    printf(")\n");
}

int main()
{
    // 輸入總共有幾種面額的銅板
    int total;
    scanf("%d", &total);
    // 輸入面額為多少
    for (int i = 0; i < total; i++)
        scanf("%d", &count[i]);
    // 輸入要找的錢
    int money;
    scanf("%d", &money);
    change(money, 0, total);

    return 0;
}
```


#### **其他遞迴_進位轉換**

* **敘述**
>轉換10進位=>2進位

* **思路**
>1. 重複做的地方=>/2、%2
>2. 遞迴=>
>(1)將數字想成=>n/2的二進位表示(前)+n%2的值(後)
>(2)所以每次遞迴就是=>將數字拆兩份，前一份遞迴
>3. 停止點=>n/2=0 

* **程式**
```clike=
#include <stdio.h>

void binary(int n)
{
    if (n > 0)
    {
        //遞迴處!!!
        binary(n / 2);
        //注意是先遞迴後印數字
        printf("%d", i % 2);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    binary(n);
    return 0;
}
```


#### **其他遞迴_費氏數列**

* **敘述**
>f(0)=0; 
>f(1)=1;
>f(n+1)=f(n)+f(n-1);

* **思路**
>1. 重複做的地方=>加法
>2. 停止點=>n=0或n=1


* **程式**

```clike=
#include <stdio.h>
int table[100];
int fa_sequence(int n)
{
    if (n == 0 || n == 1)
        return table[n];

    if (table[n] != 0)
        return table[n];
    else
    {
        table[n] = fa_sequence(n - 1) + fa_sequence(n - 2);
        return table[n];
    }
}

int main()
{
    table[0] = 0;
    table[1] = 1;

    int n;
    scanf("%d", &n);
    printf("%d\n", fa_sequence(n));
    return 0;
}
```

:::danger
注意
>費氏數列和河內塔一樣，數字呈指數型態成長，
>遞迴只適用於數字小的狀況
:::

#### **其他遞迴_優先運算**

* **敘述**
>將運算子往前移，該如何顯示運算結果

* **思路**
>1. 看到運算子=>準備接收數值
>2. 停止點=>收到數值&return

* **程式**

```clike=
#include <stdio.h>
#include <ctype.h>
char c;
int a, op1, op2;
int read()
{
    c = getchar();
    if (c == ' ')
        return read();
    else if (isdigit(c))
    {
        //把收到的數值吐回到stdin(標準輸入)
        ungetc(c, stdin);
        scanf("%d", &a);
        return a;
    }
    else if (c == '+')
    {
        //遞迴處!!!
        //op1和op2分別接收接下來的兩個數字
        op1 = read();
        op2 = read();
        return op1 + op2;
    }
    else if (c == '-')
    {
        op1 = read();
        op2 = read();
        return op1 - op2;
    }
    else if (c == '*')
    {
        op1 = read();
        op2 = read();
        return op1 * op2;
    }
}

int main()
{
    printf("%d\n", read());
    return 0;
}
```
* **程式_改成標準寫法**
```clike=
#include <stdio.h>
#include <ctype.h>

int cal(void)
{
    int ans, op1, op2;
    char c = getchar();
    if (c == ' ')
        return cal();

    // 直接收到數字(吐回去&直接印出來)
    else if (isdigit(c))
    {
        ungetc(c, stdin);
        scanf("%d", &ans);
        printf("%d", ans);
        return ans;
    }

    // 收到需要處理的值=>遞迴後印出運算
    if (c != '*')
        printf("(");
    op1 = cal();
    printf(" %c ", c);
    op2 = cal();
    if (c != '*')
        printf(")");

    // 運算最後解答
    if (c == '+')
        return op1 + op2;
    else if (c == '-')
        return op1 - op2;
    else if (c == '*')
        return op1 * op2;
}

int main(void)
{
    printf(" = %d\n", cal());
    return 0;
}
```

### Binary Search

>時間複雜度=O(log2N)

```clike=
#include <stdio.h>
int data[] = {1, 7, 9, 10, 27, 41, 60, 75, 89, 100};

void search(int s, int l, int r)
{
    int mid = (l + r) / 2;
    if (l > r)
        printf("Not in the data\n");
    if (data[mid] > s)
        search(s, mid + 1, r);
    if (data[mid] < s)
        search(s, l, mid - 1);
    if (data[mid] == s)
        printf("data[%d]=%d\n", mid, s);
}

int main()
{
    int s;
    scanf("%d", &s);
    search(s, 0, 9)

        return 0;
}
```

### Merge Sort

>要做binary sort前，需要由小到大(或由大到小)排列好的資料，
>Merge Sort 就是其中一種排列方法



## 第十週<2023.4.18>

### 指標
* 指標小介紹
>typedef使用
>指標變數宣告=>型別+ *
>取址符號=>&
>取值符號=>* (和變數宣告那個*不同)
>印出sizeof(n)=> %lu

* 陣列vs指標
>陣列名即為陣列第一項的指標(所以scanf陣列有時候不需要加上&)
>a[i] <=> *(a+i)
>&a[i] <=> (a+i)

* 指標變數byte

>sizeof char*: 8
>sizeof short*: 8
>sizeof int*: 8
>sizeof long int*: 8
>sizeof float*: 8
>sizeof double*: 8

>sizeof char: 1
>sizeof short: 2
>sizeof int: 4
>sizeof long int: 8
>sizeof float: 4
>sizeof double: 8


* 等價寫法

>a[i] ⟺ *(a+i)
>&a[i] ⟺ (a+i)

* 讀檔案

```clike=
FILE *fopen(const char *filename, const char *mode)
int fscanf(FILE *stream, const char *format [, argument, ...])
int fprintf(FILE *stream, const char *format [, argument, ...])
int fclose(FILE *stream)
```



