2017北一女中 資訊能力競賽 暑期培訓營 Anny@T.F.G.

Presentation on theme: "2017北一女中 資訊能力競賽 暑期培訓營 Anny@T.F.G."— Presentation transcript:

1 2017北一女中 資訊能力競賽 暑期培訓營

2 練習進度調查

3 【培訓用書】 程式設計與演算法競賽入門經典(劉汝佳/著，H&C/譯)
Part I 語言篇 chapter 01 程式設計入門 chapter 02 迴圈結構程式設計 chapter 03 陣列和字串 chapter 04 函數和遞迴 chapter 05 C++ 與 STL 入門 Part II 基礎篇 chapter 06 資料結構基礎 chapter 07 暴力求解法 Part III 競賽篇 chapter 08 高效演算法設計 chapter 09 動態規劃初步 chapter 10 數學概念與方法 chapter 11 圖論模型與演算法 chapter 12 進階專題 Appendix A 開發環境與方法 主要參考書目 【培訓用書】 程式設計與演算法競賽入門經典(劉汝佳/著，H&C/譯)

4 【APCS】 大學程式設計先修檢測 程式設計觀念題 程式設計實作題
單選題，以運算思維、問題解決與程式設計觀念測試為主。 測試包含 code tracing, code completion, code debugging 等題型。 題目若需提供程式片段，則以 C subset 語言命題(參考文件下載  )。 作答結果由系統自動儲存，無須上傳。 >>>查看觀念題_範例試題   程式設計實作題 實作題，撰寫完整程式或副程式。 測驗者可自選程式語言( C, C++, Java, Python )撰寫程式。 須透過系統上傳原始程式碼。若上傳多次，評分時以最後上傳版本為準。 >>>查看實作題_範例試題

5 【APCS】 命題範圍 (2016.12.22更新) Programming Concepts
Data types, constant, variable, Global, Local Control structures Loop structures Functions Recursion Array and Structures

6 【APCS】 大學程式設計先修檢測 《觀念題》
《實作題》

7 【培訓課程】 Day1: 程式競賽基礎 Day2: 陣列與字串 Day3: 函數與遞迴 Day4: 搜尋、排序、堆疊、佇列

8 Day1: 程式競賽基礎 C語言輸入輸出 掌握整數與浮點數含義(數值範圍)與輸出方法 理解程式競賽三步曲：輸入、計算、輸出
掌握迴圈(for, while), 計數器、累加器使用 學會程式逐步除錯方法(變數watch功能) 學會用fopen的方式讀寫檔案

9 C語言輸入輸出格式 #include <stdio.h> int main() { int a, b; scanf("%d%d", &a, &b); printf("%d\n", a+b); return 0; } Hint: stdio.h scanf printf &a &b int %d \n return 0

10 例題1-1 圓柱體的表面積 輸入底面半徑r和高h, 輸出圓柱體的表面積。 保留3位小數，格式請見範例。 範例輸入： 範例輸出： Area =

11 解析：表面積=上底面積+下底面積+側面積
Hint: math.h const Pi = acos(-1.0); double %lf float %f int %d return 0 #include <stdio.h> #include <math.h> int main() { const double pi = acos(-1.0); double r, h, s1, s2, s; scanf("%lf%lf", &r, &h); s1 = pi * r * r; s2 = 2 * pi * r * h; s = s1 * s2; printf("Area = %.3lf\n", s); return 0; }

12 例題1-2 三位數反轉 輸入一個三位數，分離出它的百位、十位和個位，反轉後輸出。 範例輸入 127 範例輸出 721

13 例題1-2 三位數反轉(1) #include <stdio.h> int main() { int n; scanf("%d", &n); printf("%d%d%d\n", n%10, n/10%10, n/100); return 0; }

14 例題1-2 三位數反轉 測資： 520 輸出結果: 025 還是 25

15 例題1-2 三位數反轉(2) #include <stdio.h> int main() { int n, m; scanf("%d", &n); m = (n%10)*100 + (n/10%10)*10 + (n/100); printf("%03d\n", m); return 0; }

16 例題1-2 三位數反轉 測資： 輸出結果:

17 例題1-3 交換變數 輸入兩個整數a和b, 交換二者的值，然後輸出。 範例輸入 範例輸出

18 例題1-3 交換變數 (三變數法) #include <stdio.h> int main() { int a, b, t; scanf("%d%d", &a, &b); t = a; a = b; b = t; printf("%d %d\n", a, b); return 0; }

19 例題1-4 雞兔同籠 已知雞和兔的總數量為n, 總腳數為m。輸入n和m，依次輸出雞的數目和兔的數目。如果無解，則輸出「No answer」(不要引號)。 範例輸入 範例輸出 範例輸入 範例輸出2 No answer

20 例題1-4 雞兔同籠 分析：(已知雞和兔的總數量為n, 總腳數為m) 設雞有 a 隻，兔有 b隻，則 a+b = n 2a+4b=m 解聯立，得 a = (4n-m)/2 b= n-a; 思考：何時為無解呢? 正確的是：a, b 皆為整數且 a,b皆必須為非負數。

21 例題1-4 雞兔同籠 Hint: a, b 皆為整數且 a,b皆必須為非負數 Why m%2==1 #include <stdio.h> int main() { int a, b, n, m; scanf("%d%d",&n,&m); a = (4*n-m) / 2; b = n - a; if (m % 2 == 1 || a <0 || b<0) printf("No answer\n"); else printf("%d %d\n", a, b); return 0; }

22 例題1-5 三整數排序 輸入3個整數，從小到大排序後輸出 範例輸入： 20 7 33 範例輸出： 7 20 33 Hint: a, b,c
a c b b a c b c a c a b c b a

23 例題1-5 三整數abc排序 #include <stdio.h> int main() { int a, b, c; scanf("%d%d%d", &a, &b, &c); if (a<=b && b<=c) printf("%d %d %d\n", a, b, c); else if (a<=c && c<=b) printf("%d %d %d\n", a, c, b); else if (b<=a && a<=c) printf("%d %d %d\n", b, a, c); else if (b<=c && c<=a) printf("%d %d %d\n", b, c, a); else if (c<=a && a<=b) printf("%d %d %d\n", c, a, b); else if (c<=b && b<=a) printf("%d %d %d\n", c, b, a); return 0; }

24 例題1-5 三整數abc排序 #include <stdio.h> int main() { int a, b, c, t; scanf("%d%d%d", &a, &b, &c); if (a>b) { t = a; a = b; b = t;} //執行完畢後 a<=b if (a>c) { t = a; a = c; c = t;} //執行完畢後 a<=c 且 a<=b if (b>c) { t = b; b = c; c = t;} printf("%d %d %d\n", a, b, c); return 0; }

25 總結 比賽時 無論使用C語言程式還是C++程式，都要把程式存成 .cpp，並且與C++ 程式提交。 留意格式問題 重視實驗 學會模仿
int %d float %f double %lf long long %lld (%I64d MinGw gcc) %.3lf, %.0lf, %.2f %3d %03d printf("…..\n") return 0; 重視實驗 學會模仿

26 簡單習題 3 數平均數(average.cpp) 攝氏(c)華氏(f)溫度轉換(temperature.cpp)
連續數字a…b之和(sum.cpp) n(n<360)度的正弦與餘弦(sincos.cpp) 打折(discount.cpp) 三角形判定(triangle.cpp) 閏年判定(year.cpp)

27 迴圈結構程式設計 For, while… 迴圈的使用方法 計數器、累加器 輸出中間結果除錯 使用計時函數測式效率
學會 freopen()重新導向方式讀寫檔案 學會 fopen()的方式讀寫檔案

28 for 迴圈 #include <stdio.h> int main() { int a=1,b=10; int sum=0; for (int i = a; i<= b; i++) sum += i; printf("%d\n", sum); return 0; } Hint: 觀察 i ,sum 的變化

29 Code Block Debugger(1) 開新專案(File/new/project…/console application/Go, Next, C++, project title, 例：myproject)

30 Code Block Debugger(2) 寫程式(在main.cpp裡寫程式)

31 Code Block Debugger(3) 按右鍵增加紅色中斷點Add breakpoints

32 Code Block Debugger(4) 開始除錯 (F8) 停止除錯 (Shift –F8)

33 Code Block Debugger(5) 觀看變數 Add watches Run to cursor / next line

34 例題2-1 aabb 完全平方數 輸出所有像是aabb的四位完全平方數 即， 前兩位數字相等，後兩位數字也相等 思考：1100，1111，1122，1133，1144，…，9999 那些是完全平方數

35 例題2-1 aabb 完全平方數 分析：n = aabb n = a * b * 11 (a:1~9, b:0~9) m = sqrt(n) 四捨五入後的整數 再判斷 m2 是否等於 n

36 例題2-1 aabb 完全平方數 #include <stdio.h> #include <math.h> int main() { for (int a = 1; a<=9; a++) for (int b=0; b<=9; b++) int n = a * b*11; int m = floor(sqrt(n)+0.5) ; if (m*m == n) printf("%d\n",n); } return 0; Hint: n = a * b * 11 (a:1~9, b:0~9) m = sqrt(n) 四捨五入後的整數 再判斷 m2 是否等於 n Hint: sqrt()函數 floor()函數

37 例題2-2 3n+1問題 對於任意大於1的自然數n，若n為奇數，則將n變為3n+1, 否則變為n的一半。 經過若干次這樣的變換，一定會使n變為1。 例如：3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1。 輸入n, 輸出變換的次數。 N <= 109。 範例輸入 3 範例輸出 7

38 例題2-2 3n+1問題 解題分析： 迴圈的次數不確定， n也不是遞增、遞減式的迴圈 適合使用 while迴圈 if (n 是奇數) n = 3*n + 1 else n=n/2 一直做，直到 n 為 1

39 例題2-2 3n+1問題 #include <stdio.h> int main() { int n, count = 0; scanf("%d", &n); while(n > 1) if (n%2==1) n = 3*n + 1; else n = n/2; count ++; } printf("%d\n", count); return 0; Hint: 初始化問題 迴圈重複條件 == 運算子 注意輸出結果要換行 \n

40 例題2-2 3n+1問題 測試一下： 3 11111 555555 987654321 -- 7 55 146 1 Hint: 不要忘記測試
一個看起來正確的程式可能隱含錯誤 若觀察無法找出錯誤，可以「輸出中間結果」

41 例題2-2 3n+1問題 Hint: 不要忘記測試 一個看起來正確的程式可能隱含錯誤 若觀察無法找出錯誤，可以「輸出中間結果」 留意 溢位 問題 思考： int 32 位元整數 %d 數值範圍 -231 ~ ~ long long 64位元整數 %lld (或 %I64d) -263 ~ 263-1

42 例題2-2 3n+1問題 Hint: long long n; 解決溢位問題 n <= 109 n = 3*n + 1
#include <stdio.h> int main() { int n2, count = 0; scanf("%d", &n2); long long n = n2; while(n > 1) if (n%2==1) n = 3*n + 1; else n = n/2; count ++; } printf("%d\n", count); return 0; Hint: long long n; 解決溢位問題 n <= 109 n = 3*n + 1

43 例題2-2 3n+1問題 測試一下： 3 11111 555555 987654321 -- 7 55 146 1  180 Hint:
不要忘記測試 一個看起來正確的程式可能隱含錯誤 若觀察無法找出錯誤，可以「輸出中間結果」

44 例題2-3 近似計算 計算 pi/4 = 1 – 1/3 + 1/5 – 1/7 +… 直到最後一項小於10-6

45 例題2-3 近似計算 計算 pi/4 = 1 – 1/3 + 1/5 – 1/7 +… 直到最後一項小於10-6 分析： i =0 ~ (未知)， i++ 第i項( term )= 1.0 / (i*2+1) 處理一正一負的問題 一直做，直到 term <10-6

46 #include <stdio.h> int main() { double sum = 0; for (int i=0; ; i++) double term = 1.0 / (i*2 +1); if (i%2==0) sum += term; else sum -= term; if (term < 1e-6) break; } printf("%.6lf\n",sum); return 0; 例題2-3 近似計算 Hint: for (int i=0; ; i++) { if (….) break; } 1e-6: 1* 10-6

47 程式競賽中的輸入輸出框架 Hint:重複輸入 輸入完畢先按Enter, 再按Ctrl-Z， 最後再按Enter, 即可結束輸入
while (scanf("%d", &n) == 1) { // } while (scanf("%d%d", &n, &m) == 2) Hint:重複輸入 輸入完畢先按Enter, 再按Ctrl-Z， 最後再按Enter, 即可結束輸入

48 例題2-5 資料統計 輸入一些整數，求它們的最小值、最大值和平均值(保留3位小數)。 輸入保證這些數都不超過1000。 範例輸入： 範例輸出：

49 例題2-5 資料統計 (bug) Hint: 初值設定的重要性
#include <stdio.h> int main() { int x, n=0, min, max, s= 0; while (scanf("%d", &x)==1) s += x; if (x < min) min = x; if (x > max) max = x; n++; } printf("%d %d %.3f", ,min, max, (double)s /n); return 0; Hint: 初值設定的重要性

50 例題2-5 資料統計 (重新導向) Hint: freopen() #ifdef #define
#define LOCAL #include <stdio.h> #define INF int main() { #ifdef LOCAL freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif // LOCAL int x, n=0, minx = INF, maxx= -INF, s= 0; while (scanf("%d", &x)==1) s += x; if (x < minx) minx = x; if (x > maxx) maxx = x; //printf("%d %d %.3f", ,minx, maxx, (double)s /n); n++; } printf("%d %d %.3f",minx, maxx, (double)s /n); return 0; 例題2-5 資料統計 (重新導向) Hint: freopen() #ifdef #define

51 #include <stdio. h> #define INF 1000000000 int main() { FILE
#include <stdio.h> #define INF int main() { FILE *fin, *fout; fin = fopen("data.in", "rb"); fout = fopen("data.out", "wb"); int x, n=0, minx = INF, maxx= -INF, s= 0; while (fscanf(fin, "%d", &x)==1) s += x; if (x < minx) minx = x; if (x > maxx) maxx = x; //printf("%d %d %.3f", ,minx, maxx, (double)s /n); n++; } fprintf(fout, "%d %d %.3f",minx, maxx, (double)s /n); fclose(fin); fclose(fout); return 0; 例題2-5 資料統計 (fopen) Hint: FILE *fin, *fout; fin = fopen("data.in", "rb"); fout = fopen("data.out", "wb"); fclose(fin); fclose(fout); fscanf() fprintf()

52 習題 p2-22~p2-24 水仙花數(daffodil) 韓信點兵(hanxin) 倒三角形(triangle)
子序列之和(subsequence) 分數化小數(decimal) 排列(permutation)

53 水仙花數(daffodil) 輸出100~999中的所有水仙花數。 水仙花數為3位數ABC並滿足 ABC = A3 + B3 + C3，
例如153 = 13 + 53 +33，則153為水仙花數。

54 韓信點兵(hanxin) 相傳韓信才智過人，從不直接清點自己軍隊的人數，只要讓士兵先後以三人一排、五人一排、七人一排地變換隊形，而他每次只看一下隊伍的排尾就知道總人數了。 輸入3個非負整數a,b,c,表示每種隊形排尾的人數（a<3,b<5,c<7）,輸出總人數的最小值（或報告無解）。 已知總人數不小於10，不超過100。 範例輸入：2 1 6 範例輸出：41 範例輸入：2 1 3 範例輸出：No answer

55 倒三角形(triangle) 輸入正整數n<=20，輸出一個n層的倒三角形。例如，n=5時輸出如下： ######### ####### ##### ### #

56 #include <stdio.h> int main() { int n; scanf("%d", &n); for (int i = n; i >= 1; i--) for(int j = n; j > i; j--) //每一層前輸出的空格數，第一層沒有空格 printf(" "); for(int k = 2*i-1; k>0; k--) printf("#"); printf("\n"); } return 0; 倒三角形(triangle)

57 子序列之和(subsequence) 輸入兩個正整數<m<106，輸出1/n2 + 1/(n+1)2 + …… + 1/m2，保留5位小數。輸入包含多組資料，結束標記為n=m=0。提示：本題有陷阱。 範例輸入： 樣例輸出： Case 1： Case 2：

58 #include <stdio.h> int main() { int n, m, i; while( scanf("%d%d", &n, &m) != EOF) double sum = 0; for(i = n; i <= m; i++) sum += 1.0/i/i; printf("%.5f\n", sum); } return 0; 子序列之和(subsequence)

59 子序列之和(subsequence) 本題陷阱在於n比較大時，n*n會溢出 所以 1/n^2 應該用 1/n/n 而不是 1/(n*n) 如果沒有sum = 0;，後面的輸出是前一次輸出和本次輸出之和。

60 分數化小數(decimal) 輸入正整數a, b, c，輸出a/b的小數形式，精確到小數點後c位。a, b <= 10^6，c <= 100。輸入包含多組資料，結束標記為a=b=c=0. 範例輸入： 範例輸出： Case 1：0.1667

61 //version 1 未考慮double型資料的有效數字只有15-16位 #include <stdio
//version 1 未考慮double型資料的有效數字只有15-16位 #include <stdio.h> int main() { int a,b,c,count=1; while(scanf("%d%d%d",&a,&b,&c)!=EOF){ if(a==0&&b==0&&c==0) break; printf("Case %d:%.*lf\n",count++,c,(double)(a)/b); //printf("%*.*lf", x, y, z); //意思是輸出頻寬為x，小數點後y為的double型數據z } return 0; 分數化小數(decimal) 可用 測試。

62 分數化小數(decimal) 可用【3930 1687 4】、【3930 1687 3】測試。
//version 2 未考慮小數部分第c位是9，即四捨五入後還需進位 #include <stdio.h> int main() { int a,b,c,tmp,count=1; while (scanf("%d%d%d", &a, &b, &c) != EOF){ if (a==0 && b==0 && c==0) break; printf("Case %d:%d.", count++, a / b); //整數部分 a = a % b * 10 ; while(c-->1){ //小數點後前c-1位 printf("%d", a/b); a = a % b * 10; } tmp = a % b * 10 /b; //tmp是初始a/b的小數點後第c+1位元數字 if (tmp < 5) printf("%d\n", a / b ); else printf("%d\n", a / b + 1); return 0; 分數化小數(decimal) 可用【 】、【 】測試。

63 //version 3 #include <stdio
//version 3 #include <stdio.h> int main() { int a,b,c,tmp,i,t,count=1; int s[110];//用於保存小數點後的部分 while(scanf("%d%d%d",&a,&b,&c)!=EOF){ if(a==0&&b==0&&c==0) break; t=a/b; a=a%b*10; for(i=1;i<c;i++){//小數點後前c-1位元保存到陣列s中 s[i]=a/b; } tmp=a%b*10/b;//tmp是初始a/b的小數點後第c+1位元數字 if(tmp<5) s[i]=a/b;//s[i]即s[c] else s[i]=a/b+1; while(i>1){ if(s[i]==10){ s[i]-=10; s[i-1]+=1; i--; if(s[1]==10){ s[1]-=10; t++; printf("Case %d:%d.",count++,t); for(i=1;i<=c;i++) printf("%d",s[i]); printf("\n"); return 0; 分數化小數(decimal)

64 排列(permutation)

65 Day2: 陣列與字串 掌握一維陣列、二維陣列的宣告與使用 memset, memcpy (string.h)
掌握字串宣告、指定值、比較與連接方式 熟悉ASCII碼與ctype.h的字元函數 競賽題目精選：UVa272, 10082, 401, 340, 1583, 1584 1585, 1586, 1225, 455, 227, 232, 1368, 202, 10340, 1587

66 3-1 逆序輸出 讀入不超過100個整數。 任務：逆序輸出，以空白隔開。 範例輸入： 範例輸出： 最後記得換行

67 3-1 逆序輸出 解析： 開一整數陣列 (思考大小 : 100? ?) 連續輸入放入陣列中 輸出格式

68 3-1 逆序輸出 #include <stdio.h> #define maxn 105 int a[maxn]; int main() { int x, n=0; while (scanf("%d", &x)==1) a[n++]=x; //連續讀入 for (int i = n-1; i>0; i--) printf("%d ", a[i]); //印出前n-1個 printf("%d\n", a[0]); //處理最後一個 return 0; } x 1 7 39 52 15 26 37 CtrlZ 2 3 4 5 6 a[0] a[1] a[2] a[3] a[4] a[5] a[6] n Hint: n++, maxn, 陣列宣告的位置 a[n++]=x; 代表 a[n]=x; N++; 輸出 a[6]~a[1]空格隔開 輸出 a[0] 換行

69 3-2 開燈問題 有 n 盞燈，編號為1~n。 第1個人把所有燈打開，第2個人下所有編號為2的倍數的開關(這些燈將被關掉) 第3個人按下所有編號為3的倍數的開關(關掉的燈將被打開，開著的燈將被關掉) 依此類推。 一共有 k 個人，問最後有哪些燈開著? 輸入：n和k，輸出：開著的燈的編號( k<= n <= 1000)。 範例輸入： 7 3 範例輸出： 1 2 3 4 5 6 7 1 2 3

70 3-2 開燈問題 if(j%i==0) a[j] = !a[j];
解析：用 a[1], a[2], a[3], …, a[n] 表示編號為1,2,3,…,n的燈是否開著。 #include <stdio.h> #include <string.h> #define maxn 1010 int a[maxn]; int main() { int n, k; memset(a, 0, sizeof(a)); scanf("%d%d", &n, &k); for (int i=1; i<=k; i++) for (int j=1; j<=n; j++) if(j%i==0) a[j] = !a[j]; for (int i=1; i<=n; i++) if (a[i]) printf("%d", i); printf("\n"); return 0; } 1 2 3 4 5 6 7 1 2 3 3-2 開燈問題

71 #include <stdio. h> #include <string
#include <stdio.h> #include <string.h> #define maxn 1010 int a[maxn]; int main() { int n, k, first = 1; memset(a, 0, sizeof(a)); scanf("%d%d", &n, &k); for (int i=1; i<=k; i++) for (int j=1; j<=n; j++) if(j%i==0) a[j] = !a[j]; for (int i=1; i<=n; i++) if (a[i]) { if (first) first = 0; else printf(" "); //避免多餘空格 設置一個旗標變數 first printf("%d", i); } printf("\n"); return 0; } 1 2 3 4 5 6 7 1 2 3 3-2 開燈問題

72 陣列與字串競賽題 char c; c = getchar(); putchar(c); char s[20];
scanf("%s", s); printf("%s", s);

73 例題3-1 TeX中的引號(Tex Quotes, Uva 272)
TeX 是一種由 Donald Knuth 所發展出的一套文書排版軟體。這套軟體可以將原始文件檔加上一些像字型等型態後，轉成一份很漂亮的文件。而一份漂亮的文件是需要用 `` 和 " 來把別人說的話給「引」出來，而不是用大部份鍵盤上有的 " 。 如果原始文件檔內容是： "To be or not to be," quoth the bard, "that is the question." 我們需要把原始文件變成這個樣子： ``To be or not to be,'' quoth the bard, ``that is the question.''

74 TeX中的引號(Tex Quotes, Uva 272)
"To be or not to be," quoth the bard, "that is the question." ``To be or not to be,'' quoth the bard, ``that is the question.'‘ 關鍵： 如何判斷是左引號還是右引號 如何輸入字串

75 TeX中的引號(Tex Quotes, Uva 272)
// UVa272 Tex Quotes // Rujia Liu #include<stdio.h> int main() { int c, q = 1; while((c = getchar()) != EOF) { if(c == '"') { printf("%s", q ? "``" : "''"); q = !q; } else printf("%c", c); } return 0;

76 TeX中的引號(Tex Quotes, Uva 272)
if(c == '"') { printf("%s", q ? "``" : "''"); q = !q; } else printf("%c", c); if(c == '"'){ printf("%s", q ? "``" : "''"); q = !q; } else printf("%c", c); Hint: q 為旗標變數 q = 1 !q = 0 q = !q (正反正反…)

77 例題3-2 WERTYU (UVa10082) 打字時一個常見的錯誤就是沒有把手放在正確位置，而是偏右邊一個位置。所以會發生Q被打成W，J被打成K等等的情況。你的任務就是要把打錯的字修正回來。 範例輸入 O S, GOMR YPFSU/ URD. ,U [JPMR MI,NRT OD 範例輸出 I AM FINE TODAY. YES, MY PHONE NUMBER IS

78 WERTYU (UVa10082) #include<stdio.h>
// UVa10082 WERTYU // Rujia Liu #include<stdio.h> char s[] = "` =QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"; int main() { int i, c; while((c = getchar()) != EOF) { for (i=1; s[i] && s[i]!=c; i++); // 找錯位之後的字元在常量表中的位置 if (s[i]) putchar(s[i-1]); // 如果找到，則輸出它的前一個字元 else putchar(c); } return 0; WERTYU (UVa10082)

79 例題3-3 迴文(Palindromes, UVa401)
迴文的定義為正向，反向讀到的字串均相同. 如：abba , abcba ... 等就是迴文 請判斷一個字串(長度 < 1000)是否是一個迴文？ 範例輸入 ： abba Abcd 範例輸出 ： yes no

80 迴文 #include<stdio.h> #include<string.h> int main() {
char s[30]; while(scanf("%s", s) == 1) int len = strlen(s); int p = 1; for(int i = 0; i < (len+1)/2; i++) if (s[i] != s[len-1-i]) p = 0; // 不是回文串 break; } if (p) printf("yes\n"); else printf("no\n"); return 0; 迴文

81 例題3-4 猜數字遊戲提示(Master-Mind Hints, Uva 340)
實現一個經典"猜數字"游戲。 給定答案序列和用戶猜的序列，統計有多少數字位置正確（A），有多少數字在兩個序列都出現過但位置不對（B）。 輸入包含多組數據。 每組輸入第一行爲序列長度n， 第二行是答案序列，接下來是若干猜測序列。 猜測序列全0時該組數據結束。 n=0時輸入結束。

82 例題3-4 猜數字遊戲提示(Master-Mind Hints, Uva 340)
範例輸入： 4 10 範例輸出： Game 1: (1,1) (2,0) (1,2) (4,0) Game 2: (2,4) (3,2) (5,0) (7,0)

83 // UVa340 Master-Mind Hints // Rujia Liu #include<stdio
// UVa340 Master-Mind Hints // Rujia Liu #include<stdio.h> #define maxn int main() { int n, a[maxn], b[maxn]; int kase = 0; while(scanf("%d", &n) == 1 && n) { // n=0時輸入結束 printf("Game %d:\n", ++kase); for(int i = 0; i < n; i++) scanf("%d", &a[i]); for(;;) { int A = 0, B = 0; for(int i = 0; i < n; i++) { scanf("%d", &b[i]); if(a[i] == b[i]) A++; } if(b[0] == 0) break; // 正常的猜測序列不會有0，所以只判斷第一個數是否爲0即可 for(int d = 1; d <= 9; d++) { int c1 = 0, c2 = 0; // 統計數字d在答案序列和猜測序列中各出現多少次 if(a[i] == d) c1++; if(b[i] == d) c2++; if(c1 < c2) B += c1; else B += c2; printf(" (%d,%d)\n", A, B-A); return 0; 猜數字遊戲提示

84 習題3-1 得分(Uva 1585) 列出一個由O和X組成的字串(長度為1~80)，統計得分。每個O的得分為目前連續出現的O的個數，X的得分為0。例如： OOXXOXXOOO的得分為

85 習題3-2 分子量(Uva 1586) 列出一種物質的分子式(不帶括弧)，求分子量。
本題中的分子式只包含4種原子，分別為C, H, O, N，分子量分別為 12.01, 1.008, 16.00, (單位：g/mol)。 例如： C6H5OH 分子量為 g/mol

86 習題3-3 數數字( Uva 1225) 把前n (n<=10000)個整數順次寫在一起： …數一數，0~9各出現多少次。 輸出10個整數，分別是0，1，2…9出現的次數。

87 習題3-4 週期串(Uva 455) 如果一個字串可以由某個長度為k的字串重複多次得到，則稱該串以 k 為週期。
例如，abcabcabcabc以3為週期(注意，它也以6、12為週期) 輸入一個長度不超過80的字串，輸出其最小週期。

88 習題3-5 Puzzle UVa227 有一個55的網格，其中恰好有一個格子是空的，其他格子各有一個字母，一共有四種指令：A,B,L,R,分別表示把空格上、下、左、右的相鄰字母移到空格中。輸入初始網格和指令序列（分別以數字0結束），輸出指令執行完畢後的網格。如果有非法指令，應輸出"This puzzle has no final configuration."，例如，圖執行ARRBBL0後，效果如圖所示

89 習題3-5 Puzzle UVa227 給定方格一開始的佈局及移動步驟，請輸出方格最後的形式。 INPUT
輸入會有多組測試資料，每組資料的前五列每列有五個字元，表示方格一開始的佈局，以空白字元表示空格。第六列開始為移動步驟，每個步驟一個字元，以A表示空格上面的方塊向下移動；B表示空格下面的方塊向上移動；R表示空格右邊的方塊向左移動；L表示空格左邊的方塊向右移動。注意可能會有不合法的移動方式(就算所有移步僅包含ABRL，也可能會有不合法的移步)，若出現不合法的移步，則視為該組資料無解。移步可能會有許多列，並以 0 表示移步結束。當出現字元 Z 表示測試資料結束。 OUTPUT 請在每組測試資料輸出資料編號(Puzzle #1, Puzzle #2...)，若無解請輸出"This puzzle has no final configuration."，否則請輸出方塊最後的佈局，每列的字母以一個空白字元隔開，請參考範列輸出。 請每組輸出之間以一列空行隔開。

90 習題3-5 Puzzle UVa227 SAMPLE INPUT SAMPLE OUTPUT Puzzle #1: T R G S J
XDOKI M VLN WPABE UQHCF ARRBBL0 ABCDE FGHIJ KLMNO PQRS TUVWX AAA LLLL0 AAAAABBRRRLL0 Z SAMPLE OUTPUT Puzzle #1: T R G S J X O K L I M D V B N W P A E U Q H C F Puzzle #2: A B C D F G H I E K L M N J P Q R S O T U V W X Puzzle #3: This puzzle has no final configuration.

91 習題3-6 Crossword Answers, Uva 232
輸入一個r行c列（1≤r, c≤10）的網格，黑格用“*”表示，每個白格都填有一個字母。如果一個白格的左邊相鄰位置或者上邊相鄰位置沒有白格（可能是黑格，也可能出了網格邊界），則稱這個白格是一個起始格。 首先把所有起始格按照從上到下、從左到右的順序編號爲1，2，3，…。 接下來要找出所有橫向單詞（Across）。這些單詞必須從一個起始格開始，向右延伸到一個黑格的左邊或者整個網格的最右列。最後找出所有竪向單詞（Down）。這些單詞必須從一個起始格開始，向下延伸到一個黑格的上邊或者整個網格的最下行。

92 習題3-6 Crossword Answers, Uva 232
分析： 首先搜索起始格並依次打標記。以數組a,b記錄橫縱坐標資料，數組u,w記錄橫向起始格序列與縱向起始格序列。 處理橫向單詞時依次訪問u數組記錄未訪問過的點（其橫縱坐標已由a,b數組記錄），並把已訪問過的點標記以避免重複訪問。縱向單詞亦然。 由于此前爲避免重複訪問已對u數組進行過修改，所以特意使用w數組。

93 習題3-7 DNA序列(UVa1368) 給定m個長度均爲n的DNA序列，求一個DNA序列，使其到所有序列的總hamming距離儘量小
兩個等長字串的Hamming distance等於字元不同的位置個數。例如：ACGT和GCGA的Hamming distance 為2(左數第1、4個字元不同) 輸入整數m和n(4<=m<=50, 4<=n<=1000)，以及m個長度為n的DNA序列(只包含字母A, C, G, T). 輸出到m個序列的Hamming distance和最小的DNA序列和對應的距離。 ，如有多解，輸出最小解。

94 習題3-7 DNA序列(UVa1368) Sample Input Sample Output TAAGATAC 7 ACGTACGTAA
5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA 6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA Sample Output TAAGATAC 7 ACGTACGTAA 6 AAGTTACCAA 12

95 習題3-8 循環小數(UVa202) Repeating Decimals
輸入整數a和b (0<=a<=3000, 1<=b<=3000)。 輸出a/b的循環小數表示以及循環節長度。 例如：a=5, b=43 小數表示為0.( ), 循環節為 21

96 習題3-9 子序列 All in All, Uva 10340 輸入兩個字串s和t，判斷是否可以從t中刪除0個或多個子元(其他字元順序不變)，得到字串s。 例如：abcde 可以得到bce, 但無法得到dc

97 習題3-10 盒子 Box, Uva1587 給定6個矩形的長和寬wi 和 hi (1<wi, hi<=1000).
判斷它們能否構成長方體的6個面。

98 Summary 陣列和字串往往意味著大資料量，處理大資料量時經常遇到「存取非法記憶體」的錯誤。 適當把陣列空間定義得較大。
陣列大小可以用sizeof取得。 字元編碼與正確使用字串是非常重要的。

99 Code in the book

100 Day3: 函數與遞迴 學會定義區域變數與全域變數 自定函數與結構 函數呼叫與參數傳遞 理解遞迴定義與遞迴函數
熟悉Stack segment，了解stack overflow的常見原因 例題：Uva1339, 489, 133, 213, 512, 12412

101 自訂函數 計算兩點歐幾里得距離的函數 double dist(double x1, double y1, double x2, double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); }

102 自訂結構 typedef struct 計算兩點歐幾里得距離的函數 typedef struct { double x,y;} Point;
double dist(Point a, Point b) { return hypot(a.x-b.x, a.y-b.y); } double hypot(double dx, double dy) { return sqrt(dx*dx-dy*dy); }

103 》計算組合數 編寫函數，參數是兩個非負整數n和m 傳回組合數結果 其中，m<=n<=25m
C(n, m) = n! / ((n − m)! × m!)

104 編寫求 n! 的函數 long long factorial(int n){ long long m=1; for (int i=1; i<=n; i++) m *= i; return m; }

105 C(n, m) = n! / ((n − m)! × m!) long long C(int n, int m) {
long long factorial(int n){ long long m=1; for (int i=1; i<=n; i++) m *= i; return m; } long long C(int n, int m) { return factorial(n) / (factorial(n-m)*factorial(m));

106 別忘了測試 n=25, m=12時，答案為5200300。 n=21, m=1 答案為?
即使最終答案在我們選擇的資料型別內，計算的中間結果仍可能溢位。

107 對複雜的運算式進行簡化 減少計算量(約分)、避免中間結果溢出
long long C(int n, int m){ if (m < n-m) m = n-m; long long ans = 1; for (int i=m+1; i<=n; i++) ans *= i; for (int i = 1; i<=n-m; i++) ans /= i; return ans; }

108 》質數判定 編寫一函數，參數是一個正整數n。如果n是質數，返回1，否則返回0。

109 is_prime (bug) int is_prime(int n) { for (int i=2; i*i <=n ; i++) if (n%i == 0) return 0; return 1; } 思考why： n = 1 n 很大

110 is_prime (正確) int is_prime(int n) { if (n<=1) return 0; int m = floor(sqrt(n) + 0.5); for (int i=2; i<=m ; i++) if (n%i == 0) return 0; return 1; } 思考why： m 為何不為 sqrt(n) 即可?

111 》兩數交換 swap() – 三變數交換 呼叫函數時的參數為實際參數(Argument)。 定義函數時的參數為形式參數(Parameter)。 函數內部的變數為區域變數(local variable)。 main()函數以外的變數為全域變數(global variable) 思考以下程式執行結果： #include <stdio.h> void swap(int a, int b){ int t=a; a=b; b=t; } int main(){ int a = 3, b=4; swap(a,b); printf("%d %d\n", a,b); return 0;

112 》swap() 以指標當作參數 思考以下程式執行結果： #include <stdio.h> void swap(int* a, int* b){ int t=*a; *a=*b; *b=t; } int main(){ int a = 3, b=4; swap(&a,&b); printf("%d %d\n", a,b); return 0; int* a; 整數指標的宣告 *a 為 a 指向的變數值 &a 為a 的位址

113 》陣列作為參數與返回值 計算陣列元素和 (傳陣列起始位址與陣列大小) int sum(int* a, int n) { int ans = 0; for (int i = 0; i<n; i++) ans +=a[i]; return ans; } int main() { int a[] = {1,2,3,4}; printf(" %d\n ", sum(a,4)}; return 0; } 若改計算 sum(a+1,3) 答案為何?

114 》遞迴函數 Recursive function
f(n) = n! = n * f(n-1) f(0)=1 f(n) = f(n-1)*n #include <stdio.h> int f(int n){ if (n==0) return 1; else return f(n-1)*n; } 問： f(3) = ? f(3) 會如何呼叫堆疊

115 APCS

116 APCS

117 APCS

118 APCS

119 APCS

120 APCS

121 APCS

122 APCS

123 APCS

124 APCS

125 APCS

126 APCS

127 APCS

128 練習題：UVa100 - The 3n+1 考慮以下的演算法： 輸入 n 印出 n 如果 n = 1 結束
GOTO 2 例如輸入 22, 得到的數列： 據推測此演算法對任何整數而言會終止 (當列印出 1 的時候)。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的n ( 0 < n < 1,000,000 )來說，以上的推測已經被驗證是正確的。

129 練習題：UVa100 - The 3n+1 給一個輸入 n ,透過以上的演算法我們可以得到一個數列（1作為結尾）。此數列的長度稱為n的cycle-length。上面提到的例子, 22 的 cycle length為 16. 問題來了：對任2個整數i，j我們想要知道介於i，j（包含i，j）之間的數所產生的數列中最大的 cycle length 是多少。

130 Day4:搜尋、排序、堆疊、佇列 熟悉C++版競賽程式框架 熟練並掌握string 與 stringstream
熟練STL中的排序與檢索等相關函數 熟練STL中的vector容器 理解堆疊、佇列與優先佇列的概念 掌握亂數產生方法，自行設計測資 UVa 10474, 101, 136, 221

131 Day5:資料結構基礎 Stack, queue, 運算式解析 二元樹與走訪 圖的DFS與BFS 拓撲排序演算法、尤拉迴路
Uva 514, 10305

132