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

例題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; 猜數字遊戲提示

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

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

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

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

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

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

習題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.

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

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

習題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序列和對應的距離。 ，如有多解，輸出最小解。

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

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

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

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

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

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

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

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

自訂結構 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); }

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

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

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

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

對複雜的運算式進行簡化 減少計算量(約分)、避免中間結果溢出 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; }

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

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 很大

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) 即可?

》兩數交換 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;

》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 的位址

》陣列作為參數與返回值 計算陣列元素和 (傳陣列起始位址與陣列大小) 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) 答案為何?

》遞迴函數 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) 會如何呼叫堆疊

APCS1050305

APCS1050305

APCS1050305

APCS1050305

APCS1050305

APCS1050305

APCS1050305

APCS1050305

APCS1050305

APCS1050305

APCS1050305

APCS1050305

APCS1050305

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

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

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

C++ STL C++ STL（標準範本庫）是一套功能強大的 C++ 範本類別, 提供了通用的範本類別和函數 這些範本類和函數可以實現多種常用的演算法和資料結構，如vector、list、queue、stack。

》Sort 與 Search

大理石在那裡(Where is the Marble? Uva 10474) 現有N個大理石，每個大理石上寫了一個非負整數。 首先把各數從小到大排序，然後回答Q個問題。 每個問題問是否有一個大理石寫著某個整數x， 如果是，還要回答哪個大理石上寫著x。排序後的大理石從左到右編號為1～N。（在樣例中，為了節約篇幅，所有大理石上的數合併到一行，所有問題也合併到一行。）

大理石在那裡(Where is the Marble? Uva 10474) 範例輸入： 4 1 2 3 5 1 5 5 2 1 3 3 3 1 2 3 範例輸出： CASE #1: 5 found at 4 CASE #2: 2 not found 3 found at 3 解析： 第一行4 1表示有4個數，1個問題，第二行是大理石上的4個數，第三行是問題，輸出是5在排序後的第3塊大理石上找到。 這題思路很簡單，先進行排序，再查找提問的數。

#include <cstdio> #include <algorithm> using namespace std; const int maxn=10000; int main() { int n,q,x,a[maxn],kase=0; while(scanf("%d%d",&n,&q)==2&&n) printf("CASE# %d:\n",++kase); for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); //排序 while(q--) scanf("%d",&x); int p= lower_bound(a,a+n,x)-a; //在已排序陣列a中尋找x,lower_bound的作用是查找“大於或者等於x的第一個位置” if(a[p]==x) printf("%d found at %d\n",x,p+1); else printf("%d not found\n",x); } return 0;

解析 這題中使用了algorithm標頭檔中的sort 和lower_bound 功能 如果希望用sort排序，這個類型需要定義“小於”運算子，或者在排序時傳入一個“小於”函數。排序物件可以存在普通陣列裡，也可以存在於vector中。 陣列用法 ：sort（a，a＋n） Vector 用法：sort（v.begin( )，v.end()) lower_bound的作用是查找“大於或者等於x的第一個位置”。

Linear Search #include < stdio.h > /* Search for key in the List */ int seq_search(int key, int a[], int n) { int i; for (i = 0; i < n; i++) if(a[i] == key) return i + 1; } return 0; int main() { int i, n, key, pos, a[20]; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); scanf("%d", &key); pos = seq_search(key, n, a); if (pos == 0) printf("Not found\n"); else printf("key found at %d\n", pos); return 0; }

Binary Search #include <stdio.h> #include <stdlib.h> int binarysearch(int[], int, int); int main() { int key, pos; int a[] = {3, 7, 14, 20, 23, 32, 41, 44, 56, 57, 73, 89, 93}; scanf("%d", &key); // 呼叫函式進行搜尋 pos= binarysearch(a, key, sizeof(a)/sizeof(int)); if (pos < 0) printf(“Not found %d\n", key); else printf(“found %d at %d\n", key, pos + 1); return 0; } int binarysearch(int a[], int key, int n) { int low = 0, high = n - 1; while (low <= high) int mid = (low + high) / 2; if (a[mid] == key) return mid; } else if ( key < a[mid] ) high = mid - 1; else if ( key > a[mid] ) low = mid + 1; return -1;

C++中的順序容器 #include <vector> //不定長陣列 #include <map> //映射 #include <set> //集合 #include <list> //鏈表 #include <deque> //*雙向佇列 #include <queue> //佇列 #include <stack> //堆疊

不定長陣列vector vector是一個範本類(template)，所以需要用vector<int> a vector<double> b 這樣的方式來宣告一個vector

vector基本操作 vector<int> a; a.size( ); //讀取a的大小 a.resize( ); //改變a的大小 a.push_back( ); //向a尾部添加元素 a.pop_back( ); //刪除a的最後一個元素 a.clear(); //清空a a.empty(); //測試a是否為空

#include <vector> using namespace std; int main(){ vector<int> vec; // 宣告一個裝 int 的 vector // 現在 vec 是空的 vec.push_back(10); vec.push_back(20); // 經過三次 push_back vec.push_back(30); // vec 是 [10, 20, 30] int length = vec.size(); // length = 3 for(int i=0 ; i<length ; i++){ cout << vec[i] << endl; // 輸出 10, 20, 30 } Vector #1

int main(){ vector<int> vec; for(int i=0 ; i<5 ; i++){ vec int main(){ vector<int> vec; for(int i=0 ; i<5 ; i++){ vec.push_back(i * 10); // [0, 10, 20, 30, 40] } for(int i=0 ; i<vec.size() ; i++){ cout << vec[i] << endl; // 輸出 0, 10, 20, 30, 40 Vector #2

int main(){ vector<int> vec; for(int i=0 ; i<5 ; i++){ vec int main(){ vector<int> vec; for(int i=0 ; i<5 ; i++){ vec.push_back(i * 10); // [0, 10, 20, 30, 40] } vec.pop_back(); // 移除 40 vec.pop_back(); // 移除 30 for(int i=0 ; i<vec.size() ; i++){ // vec.size() = 3 cout << vec[i] << endl; // 輸出 0, 10, 20 Vector #3

SET 基本功能有: insert: 把一個數字放進集合 erase: 把某個數字從集合中移除 count: 檢查某個數是否有在集合中

#include <set> using namespace std; int main(){ set<int> mySet; mySet.insert(20); // mySet = {20} mySet.insert(10); // mySet = {10, 20} mySet.insert(30); // mySet = {10, 20, 30} cout << mySet.count(20) << endl; // 存在 -> 1 cout << mySet.count(100) << endl; // 不存在 -> 0 mySet.erase(20); // mySet = {10, 30} cout << mySet.count(20) << endl; // 0 } SET

堆疊、佇列與優先佇列 STL 提供3種特殊的資料結構：堆疊、佇列與優先佇列。 堆疊(Stack): 符合「後進先出」(Last In First Out, LIFO)規則 可PUSH 和 POP.

Stack #include <stack> stack<int> intStack; intStack.empty()：如果stack為空，則返回true，否則返回false； intStack.size()：返回stack中元素的個數 intStack.pop()：刪除，但不返回stack頂元素 intStack.top():返回,但不刪除stack頂元素 intStack.push(item):放入新的stack頂元素

queue #include <queue> queue<int> s； s.empty(); //如果佇列為空，則傳回true，否則傳回false; s.size(); //傳回佇列中元素的個數; s.push(item); //在佇列尾放入一個新元素。 s.pop(); //刪除佇列首元素，但不傳回佇列首元素。 s.front(); //傳回佇列首元素,但不刪除佇列首元素 s.back(); //傳回佇列尾元素,但不刪除佇列尾元素。

priority_queue #include <queue> priority_queue<int> s； s.empty();//如果佇列為空，則傳回true，否則傳回false; s.size();//傳回佇列中元素的個數; s.pop();//刪除佇列首元素，但不傳回。在 priority_queue中,佇列首元素代表優先順序最高的元素; s.push(item);//在佇列尾放入一個新元素。對於priority_queue,將根據優先順序排序 s.top();//傳回優先順序最高的元素但不刪除

》Ugly Numbers Uva 136 Ugly Numbers是指不能被2，3，5以外的其他質數整除的數。

Note： 除了1之外，其餘所有的Ugly Numbers都是由最基本的2，3，5這三個Ugly Numbers相乘或者自乘得到的。也就是說，兩個Ugly Numbers相乘的積是Ugly Numbers的充分必要條件； 將2，3，5作為種子數位，不斷生成Ugly Numbers 。等到生成足夠多的Ugly Numbers後，就可以得到第1500個Ugly Number了； 以最開始為例，我們取出佇列首元素2，依次和種子數字2，3，5生成三個新的Ugly Number：4，6，10，然後檢查是否已經出現過；再取出佇列元素3，重複這個步驟； 要注意的一點是，在生成的過程中可能會產生重複的數，要注意排除；

#include <iostream> #include <vector> #include <queue> #include <set> using namespace std; typedef long long LL; //考慮到第1500個ugly number的計算過程中可能已經超過int範圍，需要用到long long類型 const int coeff[3]={2,3,5}; int main() { priority_queue< LL,vector<LL>,greater<LL> > pq; set<LL> s; //s用於存儲所有ugly number pq.push(1); s.insert(1); //單獨把第一個ugly number 1分別加入到優先佇列和s中 for(int i=1;;i++) LL x=pq.top(); //將佇列首元素（最小的元素）取出 pq.pop(); //將佇列首元素（剛取出的最小元素）從優先佇列中刪除 for(int j=0;j<3;j++) LL x2=x*coeff[j]; //生成三個新的ugly number if(!s.count(x2)) s.insert(x2); pq.push(x2); } if(i==1500) cout<<"The 1500'th ugly number is "<<x<<".\n"; break; return 0;

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