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

練習進度調查 https://goo.gl/forms/fDQRTAnYgOKTXDUo2

【培訓用書】 程式設計與演算法競賽入門經典(劉汝佳/著，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/譯) http://www.books.com.tw/products/0010650143

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

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

【APCS】 大學程式設計先修檢測 《觀念題》 https://apcs.csie.ntnu.edu.tw/index.php/samplequestions/conceptquestions 《實作題》 https://apcs.csie.ntnu.edu.tw/index.php/samplequestions/implementationquestions

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

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

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

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

解析：表面積=上底面積+下底面積+側面積 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 * 2.0 + s2; printf("Area = %.3lf\n", s); return 0; }

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

例題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; }

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

例題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; }

例題1-2 三位數反轉 測資： 520 123 200 輸出結果: 025 321 002

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

例題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; }

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

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

例題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; }

例題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

例題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; }

例題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; }

總結 比賽時 無論使用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; 重視實驗 學會模仿

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

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

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 的變化

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

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

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

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

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

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

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

例題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 * 1100 + b*11; int m = floor(sqrt(n)+0.5) ; if (m*m == n) printf("%d\n",n); } return 0; Hint: n = a * 1100 + b * 11 (a:1~9, b:0~9) m = sqrt(n) 四捨五入後的整數 再判斷 m2 是否等於 n Hint: sqrt()函數 floor()函數

例題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

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

例題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

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

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

例題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

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

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

例題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

#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

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

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

例題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: 初值設定的重要性

例題2-5 資料統計 (重新導向) Hint: freopen() #ifdef #define #define LOCAL #include <stdio.h> #define INF 1000000000 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

#include <stdio. h> #define INF 1000000000 int main() { FILE #include <stdio.h> #define INF 1000000000 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()

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

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

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

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

#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)

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

#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)

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

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

//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) 可用 1 6 58 測試。

分數化小數(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) 可用【3930 1687 4】、【3930 1687 3】測試。

//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)

排列(permutation)

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

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

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

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] 換行

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

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 開燈問題

#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 開燈問題

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

例題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.''

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.'‘ 關鍵： 如何判斷是左引號還是右引號 如何輸入字串

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;

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 (正反正反…)

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

WERTYU (UVa10082) #include<stdio.h> // UVa10082 WERTYU // Rujia Liu #include<stdio.h> char s[] = "`1234567890-=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)

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

#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; 迴文

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

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

// UVa340 Master-Mind Hints // Rujia Liu #include<stdio // UVa340 Master-Mind Hints // Rujia Liu #include<stdio.h> #define maxn 1000 + 10 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; 猜數字遊戲提示

https://github.com/aoapc-book/aoapc-bac2nd/tree/master/ch3

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

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

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