**程式設計Ⅰ【筆記Ⅱ】**
===
* [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)
```
Sign in with Wallet
Connect another wallet