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
#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; // 不是回文串 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 https://github.com/aoapc-book/aoapc-bac2nd/tree/master/ch3

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

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

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

88