4 函數 - Bo2SS

課程內容#

函數基礎知識#

函數封裝
- 可讀性、美觀性、⭐調試性（按函數模塊 debug 即可）
函數聲明三組成（必須）
- 返回值
  - 無返回值寫 void
- 函數名
- 參數聲明列表
  - 參數類型 + 參數名
函數定義
- 花括號裡的內容

递归函数#

一類編程技巧（for 循環、if 語句、遞歸），而不是算法（遞推）
函數自己調用自己
組成部分
- 語義信息：根據需求設計
- 邊界條件：設計遞歸出口，可以有多個
- 遞推公式：針對問題！
- 結果返回：不只是通過 return
  - 兩種方式：return 返回、傳出參數（指針）
怎麼證明遞歸函數是正確的？
- 簡單遞歸：將中間過程展開
  - 向下遞推 + 向上回溯
- 複雜遞歸：數學歸納法
  - 比如階乘
    - fac (1) 成立
    - 假設 fac (k) 正確
    - 證明 fac (k+1) 正確，即可

函數指針與應用#

將函數名以指針的形式傳入函數，在函數中通過函數名可以直接使用函數
- 返回值 (* 函數名)(參數類型列表)
應用
- 實現分段函數，如上圖
- 歐拉題庫：EP-45
- 找 40755 後，同時是三角形數、五邊形數、六邊形數的數字
  - 即找下一個三角形數，也滿足五邊形、六邊形數字條件
- 二分查找
  - 單調序列上面的數字序列都是有序的
  - 時間效率：O (logn)
- 代碼

⭐EP-45 亮點很多，主要注意 6 個關鍵#

二分查找的不一定是數組，有映射關係的單調序列即可
2. 根據序列特點調整了區間頭、尾
對偶邏輯減少縮進，增加可讀性
三角形數包含六邊形數：第 2n-1 個三角形數＝第 n 個六邊形數
如果用 int 類型（4 字節），會陷入死循環
1. int 類型不足以涵蓋下一個所求數字
2. 用long long int類型（8 字節），控制字符：% lld
固定六邊形數，跨度更大，速度更快，且根據第 4 點可知其一定是三角形數

其他
- 應該可以用比 temp 更小的右邊界或比 1 更大的左邊界
  - 不過因為是 O (logn)，所以縮小後效果提升不會很大
- 這裡用了函數指針，如果不用，得寫多少個差不多的 binary_search 函數？
  - 不過也可以用宏去做函數的切換
- 圖中紅叉處為筆誤，Hexagonal 修改為 Triangle

歐幾里得算法#

又叫輾轉相除法

快速計算最大公約數
- 如果 gcd (a, b) = gcd (b, a % b) = c，將使規模變小
- 證明

①設 c 為 a、b 的最大公約數，證明 b、a % b 也存在公約數 c

設正整數 k1、k2、k3
a = k1 * c
b = k2 * c
a % b = a - k3 * b // 取模的本質
所以 a % b= k1 * c - k3 * k2 * c =(k1 - k3 * k2) * c
即 a % b 是 c 的倍數，又 b 是 c 的倍數
故 c 是兩者的公約數

②證明 c 是最大的公約數

證明 b、a % b 的另兩個約數 k2、k1 - k3 * k2 互質即可
設 gcd (k2, k1 - k3 * k2)= d (正整數)，即證 d = 1
設正整數 m、n，可令
k2 = m * d
k1 - k3 * k2 = n * d
則
k1 =n * d + k3 * k2 =(n + k3 * m) * d
可得
gcd(k1, k2) >= d
又因為
gcd(a, b) = c
a = k1 * c
b = k2 * c
即
gcd(k1, k2) = 1
所以
d = 1

代碼
遞歸函數
- 可用一句實現 gcd 函數
  - 將 if 語句換成問號表達式
不需要根據 a、b 大小交換順序？不需要
- 如果 a ≥ b：gcd () 函數按正常思維進行
- 如果 a <b：gcd () 函數將交換兩個變量
Ctrl+D 會重複上次輸出而不是終止？
- 【返回讀入的字符數為 0 時會終止，比如輸入非一個 int 值】
- 因為沒有對 scanf 返回值是 EOF 的判斷
- 可以在 scanf 前取反 "~" 或在後面做 - 1 判斷

擴展歐幾里得算法#

快速求解 ax+by=1 的一組整數解
- gcd (a, b) = C 的 C 為何值時，能求解一組整數解
  - C 可取 1 或 > 1 兩種情況

a = nC
b = mC
nCx + mCy = 1
C(nx + my) = 1
nx + my 必定≥1
C 只能取 1

在輾轉相除法最後一輪只剩下 1、0 時，即互質時，就說明有整數解
數學歸納法
- 流程
  - 對於 f (0) 成立→假設 f (k) 成立→若可以得到 f (k+1) 也成立→則 k 為任意都可以成立
  - 參考上圖、下表，向下遞推 + 向上回溯

	a	b	x	y
第 k+1 層（推導）	a	b	y	x - ky
	↓↓↓	↓↓↓	↑↑↑	↑↑↑
第 k 層（假設）	b	a % b	x	y
...	↓↓↓	↓↓↓	↑↑↑	↑↑↑
第 0 層（成立）	1	0	1	0（任意）

代碼

函數輸入的地址一開始沒有值，一直到最深處才賦值，再回溯
輸出的等式右邊不一定是 1
- 其實擴展歐幾里得算法可以快速求解 ax + by = gcd (a, b) 的整數解

變參函數#

通過上述場景來學習：

問題不是函數如何聲明，而是該如何定位到變參列表的每一個參數
- 不知道變參列表裡變量的名字
- 舉例：老師想找張三同學後面一位同學回答問題，但忘記名字了，可以直接叫張三同學後面一位來回答
通過 va 一族來實現 <stdarg.h>
- 變量：va_list 類型，獲取 a 往後的參數列表

va_list arg;

- 函數
- - va_start：定位到變參列表第一參數的位置

va_start (arg, n); //n 為變參列表的前一個變量

- - va_arg：返回下一個類型匹配的表達式

va_arg(arg, int);

- - va_end：結束對可變函數實參的遍歷，清除 va_list 空間

va_end(arg);

代碼
細節見註釋，包含頭文件、va_arg 類型匹配、最多遍歷次數、va_end 清空、int 最小值
當不確定某方法所在的頭文件時，使用 gcc 編譯可能會提示需要包含的頭文件

不過在本機的 Xshell 上就算使用 - Wall 也沒有顯示，老師使用的是 Mac

隨堂練習#

代碼

沒有考慮負數輸入，但不是重點～

代碼演示#

簡版 printf 函數的實現#

實現打印字符的功能（從 0 到 1 的一步）
1. putchar ('x') 函數：向標準輸出輸出一個字符 'x'
輸出字符串功能："hello world"，並有返回成功打印字符數的功能

系統會自動給字符串末尾加 '\0'，其對應十進制值為 0；eg. 'a'→97
const 修飾符是為了讓傳入的字符串字面量不被修改，也不能被修改
- 不加的話，在 C 中不會警告，但在 C++ 中會報警告，如下：
- 另：char *const frm
  - 不能修改 frm 指針（如 char *p; frm = p;），但是可以修改該指針指向的內容
  - 參考const char * 、char const *、 char *const 三者的區別-CSDN，前兩者相同
字符指針取字符串第 i 位的值可以用兩種方式
- frm[i]
- *(frm + i)

讓 % d 控制字符生效，輸出整數
1. 向屏幕輸出 '%'

- 使用 switch 結構
- break 前面不能是逗號，需要是分號
1. 向屏幕輸出正整數 123
- 通過兩個 while 循環，將數字翻轉再翻轉輸出
  - 不翻轉的話，只能從低位開始遍歷輸出
- 數字 + 字符 '0'（即 48），可以將數字轉為字符輸出
- ❌無法輸出整數 0
1. 向屏幕輸出正整數 0
do...while 與 while 的區別
❌對於正整數 1000，輸出為 1
1. 向屏幕輸出正整數 1000
記錄數字位數，考慮 0 值，換成 do...while 方式
第二次翻轉可以使用 do...while (--digit)
- 但為了避免 digit 為 0 時陷入死循環，使用 while (digit--) 先判斷 digit 位數更保險
- 雖然 digit 為 0 幾乎不可能出現
❌錯誤樣例
digit-- 時，輸出數字 1000 時，會多一位
- --digit 則可能陷入死循環，無限循環輸出 0
  - 因為輸入為 0 時，記錄的數字位數為 0（見下），--digit 就變成了 - 1
第一个 while 循環計算 0 的位數時，為 0，有誤！
❌對於負整數，輸出有誤！
1. 向屏幕輸出負整數 - 123
只需加個負數判斷
❌對於 INT32_MAX、INT32_MIN，輸出有誤！
1. 向屏幕輸出 INT32_MAX (2^31 - 1)、INT32_MIN (-2^31)
INT32_MAX 翻轉後，int 類型表示不下→切塊翻轉
- 5 位 5 位切成兩部分→兩部分分別翻轉→兩部分分別翻轉輸出
- 24174 / 83647 →47142 / 74638 →24174 83647
- 代碼
  - rev_num 傳 temp1 地址才能使其值能被修改
  - output_num 所做的返回位數操作，我認為可以直接通過 digit1、2 得到
  - 記得修正高 5 位、低 5 位的實際位數
  - rev_num 和 output_num 函數如下：
    - * output_num裡PUTC並不生效，考慮編譯時其順序在PUTC定義前
  - ❌對於 INT32_MIN，輸出還有誤！
此時 INT32_MIN 輸出還是不對，因為
INT32_MIN 取負數還是它本身，正數可表示不下了
- 負數絕對值比正數大一
- INT32_MIN：1000...000
  - →⭐求相反數：取反 + 1→0111...111 + 1
  - →1000...000（本身）
- 代碼
  - 使用無符號整型uint32_t來存儲即可！

讓 % s 控制字符生效，輸出字符串

很簡單，加入一個 case 即可
- 注意字面量要用 const char *

檢驗返回值功能

附加知識點#

K&R 風格的函數定義
- 對參數列表裡參數的聲明放在了後面
- 上古級別的寫法，了解即可，不推薦使用
使用 % g 控制字符可以以更友好的方式輸出數字的有效位
陣列：展開的函數；函數：壓縮的陣列
int 和 long 的區別- 簡書
- 不同位數系統下大小不同
- long -> 32 位：4 字節；64 位：8 字節
- 但 int 都是 4 字節，long long 都是 8 字節
算法是什麼？聰明人的做事方法
⭐while(~scanf("%d\n", &a))
- while (scanf ("% d\n", &a) != EOF) 可以用 while (~scanf ("% d\n", &a)) 代替
- ~ 是位取反，EOF 即 - 1，按位取反即為 0
undef 宏定義時只需加宏名，不需要加參數，如：

#define PUTC(a) putchar(a)
#undef PUTC

⭐二進制求相反數：取反 + 1
- 無論正負，是互逆的，兩次該操作則回到本身
- 與 - 1 再取反一樣

思考點#

💡va_arg 對於類型不匹配時是怎麼處理的？
- 對於輸出有兩個問題：
  - 第一行，第一个 int 值獲取不到時，輸出的是 0.000000，第二次卻是 nan？
  - 第三行，輸入的全是 int 類型，但卻獲取到了第二個數字：3.000000，實驗證明，這個數字和第二行的 3.000000 有關，是因為 va_list 沒有清理乾淨嗎？
- ❓對於什麼類型就會往後走多少長度的地址去獲取值
  - 如 double，就是往後獲取 8 個字節對應的變量
- 💡但對於覆蓋還是未清理的問題，不知道無法解釋～
- 如果能打印 va_list 的地址就更好了～

Tips#

刷刷 OJ
參考工具書第 7 章