###### tags: `資訊科技` # 程式設計(使用C++、ZeroJudge) ## 零、評量、學習歷程 ### 1. 評量方式 + 上課基本練習(遲交期限：1週) 50% + 期中上機考 20% - 時間：三、迴圈教完後一週 - 上機考時網路會斷線，沒有任何參考資料，請每個子單元至少完成 1~2 題作業，熟練基本語法。 - 不要考前才寫作業，初學程式會有很多錯誤，要花時間除錯。請自我要求每週至少寫 1~2 題作業，上機考才會比較保險。 + 期末上機考(六、函式教完後一週) 20% - 時間：六、函式教完後一週或倒數第 2 週。 + 解題報告 10% - 想高分或上機考考差的同學請保握機會。 - 不會的可以去參考網路上的程式碼、解法，同學也可以互相討論，而且是鼓勵的。不論如何，都要在了解解法後，不看別人的程式碼，自己親自寫一遍。 - 中午電腦教室除考前1週外有開放時間，沒電腦、沒網路做作業的同學請善加利用。 - 繳交期限： * 最後一週上課前1天。接近期末考，最慢在期中上機考後就要開始動工。 - 分數： * 每一題10分，上限120分(12題)。 * 每個單元至多可放 2 題 * 不可以都寫同一單元的題目 * 題號劃掉的太簡單了，只是用來增加信心，不能放入解題報告。 - 報告格式： * 第1頁為解題目錄(單元、題號、題目、頁碼)。 * 每題的子標題為 (1) 單元、題號、題目、題目簡述 (2) 解題動態、評分結果截圖 (3) 解題思路 (4) 程式碼 (5) 反思(遇到的錯誤、修正的地方、更好的方法…) (6) 錯誤程式碼 - 檢核方式： * 有交解題報告者，最後一週會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選)，寫不出來作業直接作廢不算分，請務必自行思考完成。 * 不要為了分數直接複製貼上別人的程式碼，那是無意義的行為，檢核時你就會現出原形，就不用做這種白工了。 - 可整合上課內容後完成課程學習成果，上傳至學習歷程檔案平台。請儘量挑選一開始有錯，然後修正的題目，將修正的想法寫出來更能顯示出反思的能力。 - 如果對寫程式有興趣並要參加APCS檢定，下學期多元選修可以選修APCS(大學程式設計先修檢測)程式實作，挑選標準主要為ZJ的解題數(請寫在多元選修意向書裏)。 ### 2. [TOI推廣計畫-線上練習賽](https://tpmso.org/toi/index.php/reg/) + 成績計算：分數/100直接加在總成績。 + 上學期10、11、12月，下學期3、4、5月，最後一週。 + 星期一08:00 ～ 星期五20:00。90分鐘。 + [證書](https://drive.google.com/open?id=1DcgDKn1R33kOPc_HazdIyQDgyYxSCPlZ) ### 3. [APCS](https://apcs.csie.ntnu.edu.tw/) + 實作級分*2，直接加在總成績。 + 3級分免上機考，上機考成績為100。 + 4級分以上者，一切皆免，學期成績直接算100。 ### 4. 學習歷程檔案(修課記錄、課程學習成果) + 最後一週上課結束前如果認證完成，學期總成績加分。 + [撰寫「課程學習成果」參考資源](https://hackmd.io/@cube/HkCv90e19)。 ### 5. 基礎教學網站 + [基礎程式設計 - C與C++簡報、影片](http://www.18dice.tw/diceweb/teacherstudy/CandC++.html) ### 6. [SoloLearn C++ Tutorial](https://www.sololearn.com/) + 全部學完可拿到[證書](https://i.imgur.com/0yAAPlB.jpg)(額外加分)。 ### 7. 軟體 + [Code::Blocks](http://cs.cysh.cy.edu.tw/software/software_download.html) + [Dev-C++](http://cs.cysh.cy.edu.tw/software/software_download.html) + [VSCode](https://hackmd.io/@liaojason2/vscodecppwindows )([無法debug處理](https://stackoverflow.com/questions/37405975/c-for-vs-code-unable-to-start-debugging-program-path-is-missing-or-invalid?fbclid=IwAR1QQOzXkI6LQc2n0L3q0Sywp_Fx92igG83ngDbhLJrMdZXvaFEqtOW04hM)) + [GDB online Debugger | Compiler - Code, Compile, Run, Debug online C, C++](https://www.onlinegdb.com/) + [The collaborative browser based IDE - Replit](https://replit.com/) ## 一、輸出與輸入、變數、運算式與運算子 ### 1. 輸出與輸入 :::info EX_1_1：[d483: hello, world](https://zerojudge.tw/ShowProblem?problemid=d483) + 快速鍵 `Ctrl+滾輪`：放大、縮小 `F9`：Build and run `Ctrl+a`：全選 `Ctrl+c`：複製 `Ctrl+v`：貼上 `Ctrl+x`：剪下 ::: :::info EX_1_2：[a001: 哈囉](https://zerojudge.tw/ShowProblem?problemid=a001) ``` c int main() { ~ // 變數宣告 while(cin >> ~) //不需要加「;」 { cout << ~ << endl; } return 0; } ``` + 快速鍵 `Shift`+方向鍵、`Home`、`End`：選取程式 + 執行完的測試視窗要關閉，才能再次執行。 ::: ### 2. 變數型態 | 常用型態 | 意義 | 範圍 | |:-------|:---------- |:-------| | int | 整數 |-2147483648~2147483647|| | long long int | 長整數 |-2^63^ ~ 2^63^-1|| | float | 單精度浮點數(小數) |±1.5x10^−45^ ~ ±3.4x10^38^| | double | 雙精度浮點數(小數) |±5.0×10^−324^ ~ ±1.7×10^308^| | char | 字元 | 'A'| | string | 字串 | "Hello"| | bool | 布林 | true、false| ### 3. 變數宣告 ``` c int math=80; // 資料型態 變數名稱; double pi=3.14159265359; // 資料型態 變數名稱=初值; int sum,ave,rank; // 資料型態 變數名稱1,變數名稱2,變數名稱3...; ``` :::info EX_1_3：[a002: 簡易加法](https://zerojudge.tw/ShowProblem?problemid=a002) + cin >> a,b; 是錯誤的語法。 + 使用線上軟體或再開一個專案(homework)寫作業，未寫完存雲端。 ::: :::info EX_1_4：[d489: 伏林的三角地](https://zerojudge.tw/ShowProblem?problemid=d489) + 以[海龍公式](https://zh.wikipedia.org/zh-tw/%E6%B5%B7%E4%BC%A6%E5%85%AC%E5%BC%8F)求三角形面積。 + 「*」不可省略。 + 先乘除後加減，可用小括號改變運算順序。 + // 註解 + 需除錯時，可將變數印出來看。 + cin >> a >> b >> c >> s → error，s不用輸入 ::: :::warning [~~d049: 中華民國萬歲！~~](https://zerojudge.tw/ShowProblem?problemid=d049) ::: :::warning [a861: 1. Secure the Perimeter](https://zerojudge.tw/ShowProblem?problemid=a861) ::: :::warning [c379: 成為出題者](https://zerojudge.tw/ShowProblem?problemid=c379) ::: :::warning [d461: 班際籃球賽](https://zerojudge.tw/ShowProblem?problemid=d461) ::: :::warning [d053: 10970 - Big Chocolate](https://zerojudge.tw/ShowProblem?problemid=d053) ::: ### 4. 算數運算子 | 算數運算子 | 意義 | 備註| |:-------- |:------ |:-------| | + | 加 | | | - | 減 | | | * | 乘 | | | / | 除 | | | % | 取餘數 | | | ++ | 遞增 | i++ 即 i=i+1| | \-\- | 遞減 | i\-\- 即 i=i-1| :::info EX_1_5：[d050: 妳那裡現在幾點了？](https://zerojudge.tw/ShowProblem?problemid=d050) + % ::: :::info EX_1_6：[d485: 我愛偶數](https://zerojudge.tw/ShowProblem?problemid=d485) + 將 a 調整為後一個偶數， b 為前一個偶數，[計算等差數列項數](https://zh.wikihow.com/%E8%AE%A1%E7%AE%97%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97%E4%B8%AD%E7%9A%84%E9%A1%B9%E6%95%B0)。 + a 偶數 a=a+0，a 奇數 a=a+1 - a=a+a%2 + 複合指定運算子(a=a+5 → a+=5) ::: :::info EX_1_7：[d051: 糟糕，我發燒了！](https://zerojudge.tw/ShowProblem?problemid=d051) + (f-32)*5/9 + 整數除法、浮點數除法：5/2、5.0/2。 + 型態轉換(double)。 + C++小數點位數控制。 + f，c 全部宣告為 double？ - double 不可 %。 ``` c #include <iomanip> cout << fixed << setprecision(3) << ... ; // setprecision(n) 會將輸出的數值控制為 n 位數，如果加上 fixed 表示只控制小數點以下的位數。 ``` ::: :::warning [d073: 分組報告](https://zerojudge.tw/ShowProblem?problemid=d073) + / 整數除法 ::: :::warning [d827: 買鉛筆](https://zerojudge.tw/ShowProblem?problemid=d827) + % ::: :::warning [b757: 頸美椰子樹](https://zerojudge.tw/ShowProblem?problemid=b757) + double + / ::: :::warning [a862: 2. My Dear Friend VIR](https://zerojudge.tw/ShowProblem?problemid=a862) + double + / + C++小數點位數控制。 ::: :::warning [f651: 開關燈](https://zerojudge.tw/ShowProblem?problemid=f651) + / 整數除法 + 觀察n=1~10，找規律。類似d073。 ::: ### 5. 關係運算子 | 關係運算子 | 意義 | 備註| |:-------- |:------ |:-------| | == | 等於 | =是指派，==是判斷是否相等 | | != | 不等於 | | > | 大於 | | >= | 大於等於 | | < | 小於 | | <= | 小於等於 | :mega: a < b < c 要寫成 a < b && b < c ### 6. 邏輯運算子 | 邏輯運算子 | 意義 | 備註| |:-------- |:------ |:-------| | && | and | | \|\| | or | | ! | not | :::info EX_1_8：[d063: 0 與 1](https://zerojudge.tw/ShowProblem?problemid=d063) + ! ::: :::info EX_1_9：[e343: BMI 計算](https://zerojudge.tw/ShowProblem?problemid=e343) + 運算式中沒有中、大括號，通通都用小括號。 + 型態轉換。 + C++小數點位數控制。 + 需除錯時，可將變數印出來看。 ::: ## 二、選擇 ### 1. if 條件式語法 ``` c if(條件) { 條件「成立」時的程式碼 } ``` :mega: if()後不能加「;」 :::info EX_2_1：[a012: 10055 - Hashmat the Brave Warrior](https://zerojudge.tw/ShowProblem?problemid=a012) + long long + Q：cout << ans << endl; 放在if{ }內會發生什麼問題？ ::: :::warning [~~a799: 正值國~~](https://zerojudge.tw/ShowProblem?problemid=a799) ::: :::warning [d068: 該減肥了！](https://zerojudge.tw/ShowProblem?problemid=d068) ::: :::warning [b682: 2. 同學早安](https://zerojudge.tw/ShowProblem?problemid=b682) + [提示](https://zerojudge.tw/ShowThread?postid=16450&reply=0) + 將時間全部轉成分鐘會比較好做，分鐘的時間差以/、%轉回小時、分。 + 因為校長最久只會站23小時59分，所以如果開始時間大於結束時間，表示站隔夜，結束時間要多加1440。 ::: :::warning [h658: 捕魚 (Fishing)](https://zerojudge.tw/ShowProblem?problemid=h658) + d(距離)及minD(最小距離)要宣告為double，minD的初值可假設為一個比可能最大值還要大的值(如1000)。 + 開根號用sqrt()，需含入 cmath 標頭檔，d=sqrt((x-a)\*(x-a)+(y-b)\*(y-b)); + 讀入每個魚群的中心座標，計算魚夫和魚群的距離，如果比目前的最小距離小，則記錄此時的最小距離和座標。 ::: ### 2. if~else 語法 ``` c if(條件) { 條件「成立」時的程式碼 } else { 條件「不成立」時的程式碼 } ``` :mega: 養成縮排的好習慣：大括號 { } 內的程式碼以Tab鍵向右縮排，可以增加程式碼的可讀性，並方便除錯。 :::info EX_2_2：[d064: ㄑㄧˊ 數？](https://zerojudge.tw/ShowProblem?problemid=d064) ::: :mega: [常用運算子的優先順序](https://magicjackting.pixnet.net/blog/post/70902861) :::info EX_2_3：[d066: 上學去吧！](https://zerojudge.tw/ShowProblem?problemid=d066) + 7<=h<17 → h>=7 && h<17 → h>=7 && m>=30 && h<17，幾點會造成錯誤？ → (h>=8 && h<17) || (7點的狀況) + &&、|| ::: :::warning [b877: 我是電視迷](https://zerojudge.tw/ShowProblem?problemid=b877) ::: :::warning [f373: 週年慶 Anniversary](https://zerojudge.tw/ShowProblem?problemid=f373) + 題目簡述 - 天天百貨（編號0）消費滿2000折200，琪琪百貨（編號1）消費滿1000折100。 - 輸入一正整數 N （0 ≦ N ≦ 10000），代表預計花費的金額，請問去那個百貨可以得到最好的優惠（如果優惠後的價格一樣，預設去天天百貨）。 - 輸出折扣後的金額以及百貨的編號。 + 分別計算兩百貨折扣後的金額，比較大小輸出。 ::: :mega: 如果測資的第一行有一個整數t，代表測試的筆數，要用以下的寫法。 ```cpp= cin >> t; while(t>0) { ~ t--; } 或 cin >> t; while(t--) { ~ } ``` :::warning [e948: 1. 基礎代謝率 (BMR Calculation)](https://zerojudge.tw/ShowProblem?problemid=e948) + 輸入的第一行有一個整數n，代表測試筆數。while(n--) // 兩個減號，[寫法參考](https://yuihuang.com/zj-e948/) + C++小數點位數控制。 ``` c #include <iomanip> cout << fixed << setprecision(2); ``` ::: :::warning [f043: 1. 小豪的回家作業 (Homework)](https://zerojudge.tw/ShowProblem?problemid=f043) + 給定兩整數R、A，求出A＋B＝R的B值後輸出。 + 如果R＝A，則先將A-3再求B。 + A、B小的寫在算式的前面。 ::: ### 3. 巢狀 if 語法 ``` c if(條件1) { if(條件2) { 條件1「成立」，且條件2「成立」時的程式碼 } else { 條件1「成立」，且條件2「不成立」時的程式碼 } } else { 條件1「不成立」時程式碼 } ``` :mega: if或else的大括號{ }內，都可再增加條件式。 :::info EX_2_4：[d058: BASIC 的 SGN 函數](https://zerojudge.tw/ShowProblem?problemid=d058) + if(n>0) vs. if(n>=0) ::: :::info EX_2_5：[a006: 一元二次方程式](https://zerojudge.tw/ShowProblem?problemid=a006) + 開根號用sqrt()，需含入 cmath 標頭檔。 + d=0時，x1還是要計算過程。執行時，不會去執行不符合條件的程式碼。 + F8除錯示範。 + Q：x1、x2放在d後面計算可以嗎？負數開根號？ ::: :::warning [a003: 兩光法師占卜術](https://zerojudge.tw/ShowProblem?problemid=a003) ::: :::warning [d065: 三人行必有我師](https://zerojudge.tw/ShowProblem?problemid=d065) ::: :::warning [f165: 棒棒糖事件](https://zerojudge.tw/ShowProblem?problemid=f165) + 判斷棒棒糖數除以小朋友人數的餘數r是否為0，當r=0時，輸出「OK!」，反之輸出r。 + 小朋友人數可能為0，不會搶成一團，所以蝸牛老師不需吃下任何棒棒糖，輸出「OK!」。 + 先排除小朋友人數為0的狀況，不然「%」運算會錯誤。 ::: :::warning [b899: 2. 物品探測](https://zerojudge.tw/ShowProblem?problemid=b899) + 分別計算三點間的距離，最長的為正方形的對角線。 + 正方形四點 A、B、C、D，假設 A、C 為對角，則 D = A + C - B。 ::: ### 4. 多重選擇 if~else if~else 語法 ``` c if(條件1) { 條件1「成立」時程式碼區塊 } else if(條件2) { 條件1「不成立」，且條件2「成立」時的程式碼 } else if(條件3) { 條件1、2「不成立」，且條件3「成立」時的程式碼 } ... else { 上述條件都「不成立」時的程式碼 } ``` :mega: else if()可視需要增加。 :::info EX_2_6：[d460: 山六九之旅](https://zerojudge.tw/ShowProblem?problemid=d460) ::: :::warning [f337: 同樂會 (Party)](https://zerojudge.tw/ShowProblem?problemid=f337) ::: :::warning [c382: 加減乘除](https://zerojudge.tw/ShowProblem?problemid=c382) + 要宣告一個字元變數(char)讀「+ - * /」，比較時，字元前後要有單引號。 ::: :::warning [b676: 63萬勞工苦輪班不像人像機器](https://zerojudge.tw/ShowProblem?problemid=b676) ::: :::warning [a053: Sagit's 計分程式](https://zerojudge.tw/ShowProblem?problemid=a053) ::: :::warning [a244: 新手訓練 ~ for + if](https://zerojudge.tw/ShowProblem?problemid=a244) + long long + while(n--) ::: :::warning [e972: 1. 貨幣轉換 (Currency)](https://zerojudge.tw/ShowProblem?problemid=e972) + 變數可設為double。 + 先將預算轉成目的地的幣值。 + 依「預算<花費」，「預算-花費<0.05」(0.00以字串列印->"0.00")，「預算>花費」，分別輸出。 + C++小數點位數控制。 ``` c #include <iomanip> cout << fixed << setprecision(2) << money-m; ``` ::: ## 三、迴圈 ### 1. for 迴圈語法 ``` c for(變數初值; 條件判斷; 改變量) { 程式碼 } ``` :mega: 除錯練習 (1) Build and run (F9)後發現錯誤 (2) 設中斷點 (3) Debug (F8) (程式會執行到中斷點後停止，讓我們可以按 F7 逐行執行) (4) Debugging windows/Watches (5) Next line (F7) (行號旁出現黃色箭頭開始按 F7，黃色箭頭的這一行表示按 F7 後要執行) (6) Stop debugger :::info EX_3_1：[d498: 我不說髒話](https://zerojudge.tw/ShowProblem?problemid=d498) ``` c int i; for(i=1; ...) { } ``` Q1：如果改變量寫i+1，會發生什麼事，練習除錯(F8)。 + i=i+1 或 i+=1 或 i++ + i+1不會改到i Q2：n輸入10，以除錯(F8)看流程，當n=10時，下一行會往上或往下執行？i 最後的值為？ Q3：n=10時，i+=3(i=i+3)，會印出幾次字串， i 最後的值為？ ::: :::info EX_3_2：[d490: 我也愛偶數](https://zerojudge.tw/ShowProblem?problemid=d490) Q1：先完成 a+...+b，但答案會錯誤？ + 先將 i、sum 印出來看，或除錯(F8)。 + 初值歸零 Q2：初值歸零後，第2次答案會錯誤？ + 變數範圍：int sum=0; // 宣告在while迴圈內 + 區塊變數：for(int i=a;) ::: :::warning [~~b970: 我不說髒話 (續)~~](https://zerojudge.tw/ShowProblem?problemid=b970) ::: :::warning [d046: 文文採西瓜](https://zerojudge.tw/ShowProblem?problemid=d046) ::: :::warning [d786: 三、平均值](https://zerojudge.tw/ShowProblem?problemid=d786) + 每筆測資sum要歸零。 ::: :::warning [c005: 10300 - Ecological Premium ](https://zerojudge.tw/ShowProblem?problemid=c005) + long long + 運算式可先化簡避免除法誤差。 ::: :::warning [f708: 蟲蟲危機 (Insect)](https://zerojudge.tw/ShowProblem?problemid=f708) + 題目簡述 - 第一行有整數 M 和 N (1 ≤ M ≤ 2000, 1 ≤ N ≤ 2000) 代表螞蟻和蚱蜢的總數 - 第二行有 M 個數字表示螞蟻的身高 Ai (1 ≤ Ai ≤ 1000, 1 ≤ i ≤M) - 第三行有 N 個數字表示蚱蜢的身高 Gi (1 ≤ Gi ≤ 1000, 1 ≤ i ≤ N) - 若螞蟻的數量比蚱蜢多且螞蟻的總身高比蚱蜢高，螞蟻們才敢決定跟蚱蜢打一架爭，輸出 Yes，否則輸出 No。 ::: :::warning [f338: 后羿射日(Archer)](https://zerojudge.tw/ShowProblem?problemid=f338) ::: :::warning [j178: 手遊廣告 (Advertisement)](https://zerojudge.tw/ShowProblem?problemid=j178) + break：強制跳出「整個」迴圈。 ::: :::warning [f312: 1.人力分配](https://zerojudge.tw/ShowProblem?problemid=f312) + 以for迴圈枚舉所有可能的工人分配方法。 + 求最大值可用max函式或if。 ::: :::warning [f605: 1. 購買力](https://zerojudge.tw/ShowProblem?problemid=f605) + 找出3物品最大值和最小值，可使用if或max、min函式。 + max 若要傳入三個以上的參數，須用大括號包住，並含入 algorithm 標頭檔。 ::: :::warning [c299: 1. 連號或不連號](https://zerojudge.tw/ShowProblem?problemid=c299) + 輸入數列時，找出其最大值和最小值，可使用if或max、min函式。 + 最大-最小+1==n，表示這個數列是連續的。 ::: :::warning [d660: 11764 - Jumping Mario](https://zerojudge.tw/ShowProblem?problemid=d660) + prev=now ::: ### 2. 巢狀迴圈語法 ``` c for(變數1初值;條件1判斷;改變量) { for(變數2初值;條件2判斷;改變量) { 程式碼 } } Q：在日常生活中，有什麼事像巢狀迴圈的概念？ ``` :::info EX_3_3：[c418: Bert的三角形 (1)](https://zerojudge.tw/ShowProblem?problemid=c418) ::: :::info EX_3_4：[c419: Bert的三角形 (2)](https://zerojudge.tw/ShowProblem?problemid=c419) + 除錯練習：內圈若寫j--會如何？ ::: :::warning [c420: Bert的三角形 (3)](https://zerojudge.tw/ShowProblem?problemid=c420) ::: :::warning [f063: The Strongest Chain](https://zerojudge.tw/ShowProblem?problemid=f063) + 巢狀迴圈。 + 求每條鏈子最小值中，找出最大值。 ::: :::warning [c013: 00488-Triangle Wave](https://zerojudge.tw/ShowProblem?problemid=c013) + 巢狀迴圈。 + 下半部 for(k=A-1;k>0;k\-\-) ::: ### 3. while 迴圈語法 ``` c while(條件判斷) // 條件為「真」的時候繼續執行 { 程式碼 } ``` ``` c= for(int i=1;i<=5;i++) { cout << "hello "; } cout << endl; int i=1; while(i<=5) { cout << "hello "; i++; } ``` :::info EX_3_5：[d189: 11150 - Cola](https://zerojudge.tw/ShowProblem?problemid=d189) + 請用 while 模擬換瓶過程，不可以直接套公式。 + 以除錯(F8)看換瓶過程，最後剩 2 空瓶，可借 1 空瓶多換 1 瓶。 ``` c= int sum=n; while() { } if(n==2) { sum++; } ``` + 題目先借瓶，什麼狀況需要借？ → 不管需不需要都借。為什麼 n=9 時，不需要借也借，卻不會錯誤。(F8) ``` c= int sum=n; n++; while() { } ``` ::: :::info EX_3_6：[a038: 數字翻轉](https://zerojudge.tw/ShowProblem?problemid=a038) + 前面有 0 的話應消除。如50200 不是輸出 00205，而是205。 + 0要輸出0。為何會TLE？除錯(F8)練習。 + 迴圈中斷 - break：強制跳出「整個」迴圈。 - continue：強制跳出「此次」 迴圈，繼續進入下一次圈。 ``` c== for(int i=1;i<=10;i++) { if(i==5) { break; // continue; } cout << i << " "; } ``` ::: :::warning [c079: 10346 - Peter's Smokes](https://zerojudge.tw/ShowProblem?problemid=c079) ::: :::warning [d570: 神龍見首不見尾](https://zerojudge.tw/ShowProblem?problemid=d570) ::: :::warning [f070: 1. 韓信點兵 (HanXin)](https://zerojudge.tw/ShowProblem?problemid=f070) + 因為答案很小，暴力解即可。 + while(true)，從1開始測，輸出符合條件的值。 ::: :::warning [c350: “綠白黃” 四校聯課](https://zerojudge.tw/ShowProblem?problemid=c350) + ans+=(n/k)*w; // 每次新換的電話號碼 + n-=(n/k)*(k-w); // 因為 k > w，所以可以看成每一次的交換(k換w)，新號碼會減少 (k-w) 個。 ::: ### 4. do..while 迴圈語法 ``` c do { 程式碼 }while(條件判斷); // 條件為「真」的時候繼續執行 ``` :mega: do while()後要加分號！ :::info EX_3_7：[d356: NOIP2002 1.级数求和](https://zerojudge.tw/ShowProblem?problemid=d356) + 型別轉換。 + 浮點數誤差(float->double)。 + cout << --i << endl; ``` c int a=1,b; b=a++; b=++a; cout << a << " " << b << endl; ``` ::: :::info EX_3_8：[a149: 乘乘樂](https://zerojudge.tw/ShowProblem?problemid=a149) + 假設 n 固定只有3位數，練習求百位、十位、個位數字。 + mul*=n%10 vs. mul=mul*n%10 (錯誤) + [常用運算子的優先順序](https://magicjackting.pixnet.net/blog/post/70902861) + 以while迴圈改寫會發生什麼錯誤？ ::: :::warning [a215: 明明愛數數](https://zerojudge.tw/ShowProblem?problemid=a215) ::: :::warning [c561: Bert 愛搗蛋](https://zerojudge.tw/ShowProblem?problemid=c561) + 將數字反轉，記錄最大值。 + 將數值反轉的方法，假設 a為原數值，rvs為反轉後的數值(預設值為 0) rvs=rvs*10+(a%10); a/=10; // 讓個位數消失 ::: :::warning [f374: 分組 Grouping](https://zerojudge.tw/ShowProblem?problemid=f374) ::: ## 四、陣列 ### 1. 陣列宣告 ``` c int a[5]; // 宣告一個大小為5的int陣列 a[0]=80; // 陣列的索引值由0開始 a[5]=90; // 錯誤，索引值0~4 int a[5]={1,3,5,7,9}; // 宣告陣列時設定初值 int a[5]={1}; // a[0]初值1，其餘預設為0 for(int i=0;i<5;i++) // 以 for 迴圈來控制陣列的 index cin >> a[i]; // 1-based indexing int a[6]; for(int i=1;i<=5;i++) // 以 for 迴圈來控制陣列的 index cin >> a[i]; int a2d[4][2]; // 宣告二維陣列(多維陣列) int a2d[4][2]={{1,2},{3,4},{5,6},{7,8}}; Q：如何建立可以儲存班上期中考成績的二維陣列？ // a2d[r][c]表示第 r 列，第 c 欄的值(類似英文書寫習慣) ``` :::info EX_4_1：[b127: 會議中心（Room）](https://zerojudge.tw/ShowProblem?problemid=b127) + [費式數列](https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97) ::: :::info EX_4_2：[a693: 吞食天地](https://zerojudge.tw/ShowProblem?problemid=a693) + [陣列宣告時，大小請直接指定為題目給的最大範圍，避免用變數。](https://openhome.cc/Gossip/CGossip/OneDimArray.html) ``` c int n; while(cin >> n >> m) { int food[n]; // 避免使用，編譯器不一定支援。 int food[100005]; } ``` + 每次都重算會TLE。檔名：a693(TLE) + [時間複雜度](https://jason-chen-1992.weebly.com/home/time-space-complexity) + [前綴和](https://www.youtube.com/watch?v=VfL7dzFkW30)，不要用爆力法 ``` c for(int i=1;i<=n;i++) // 對每個idx { for(int j=1;j<=i;j++) // 從頭開始加到此idx { pfx[i]+=food[j] } } ``` + i=0時，food[i]=food[i-1]+t 會錯誤，所以改從index 1 開始放前綴和。 - [1-based indexing](https://xlinux.nist.gov/dads/HTML/oneBasedIndexing.html) ::: :::info EX_4_3：[i071: 風景 (Landscape)](https://zerojudge.tw/ShowProblem?problemid=i071) + [1-based indexing](https://xlinux.nist.gov/dads/HTML/oneBasedIndexing.html) + 從小明家往左、往右檢查>小明家樓高的數量，錯誤的原因為？ + 以變數(LMax、RMax)記錄小明家左邊、右邊最高樓高(初值為小明家樓高)。從小明家往左、往右檢查，如果檢查的樓高>LMax、RMax，則答案+1，並調整LMax、RMax。 + 或往右發現有比小明家高的樓高，就讓小明家長高，或讓小明搬家。(小明家高要先保留，往左檢查前要恢復原高) + for迴圈的計數變數來控制陣列存取的位置。 ``` c for(int i=1;i<=n;i++) cin >> h[n]; // 錯誤 ``` ::: :::warning [f345: 新手練習題—陣列](https://zerojudge.tw/ShowProblem?problemid=f345) ::: :::warning [b138: NOIP2005 1.陶陶摘苹果](https://zerojudge.tw/ShowProblem?problemid=b138) ::: :::warning [f818: 物競天擇 (Survival)](https://zerojudge.tw/ShowProblem?problemid=f818) + 設一個變數存身高*體重的最小值，初值為1000005。 ::: :::warning [e339: 前綴和練習](https://zerojudge.tw/ShowProblem?problemid=e339) + 累加的數值會超過 int 上限。 + 若使用陣列記錄，小心不要出現b[-1]的狀況。 ::: :::warning [b558: 求數列第 n 項](https://zerojudge.tw/ShowProblem?problemid=b558) ::: :::warning [f442: 老鷹抓小雞 Eagle](https://zerojudge.tw/ShowProblem?problemid=f442) + 題目簡述 - 「老鷹抓小雞」的遊戲玩法為有一人是老鷹、一人是母雞、剩下的人為小雞(老鷹要抓小雞，母雞則要保護身後的小雞)。小雞被抓後會變成老鷹，老鷹則變成小雞(取代被抓小雞的位置)。 - 第一列有一正整數 N，代表有 N 隻小雞。 - 第二列有 N 個正整數，代表小雞的編號。 - 第三列有一正整數 E，代表老鷹的編號。 - 第四列有一正整數 Q，代表玩了 Q 回合。 - 第五列有 Q 個正整數，代表每回合被抓到小雞的編號。 - 輸出經過 Q 回合後，隊伍中小雞的編號。 ::: :::warning [b139: NOIP2005 2.校门外的树](https://zerojudge.tw/ShowProblem?problemid=b139) + 可以宣告一個整數陣列tree(預設為0)，陣列的索引值代表位置，陣列值0、1表示有沒有樹。 ::: :::warning [a253: 王老先生的磨菇田](https://zerojudge.tw/ShowProblem?problemid=a253) + 因為蘑菇編號只介於０～１００間，因此可以開一個大小為１０１的陣列（初始值皆為０），陣列的索引值代表蘑菇編號，儲存對應編號的蘑菇數量。 ::: :::warning [b374: [福州19中]众数](https://zerojudge.tw/ShowProblem?problemid=b374) + [想法參考](https://zerojudge.tw/ShowThread?postid=16300&reply=0) ::: :::warning [c199: 爬山去(Hiking)-TOI練習賽y7m5-1](https://zerojudge.tw/ShowProblem?problemid=c199) + 輸入時可先將重覆的數字去掉。 ::: :::warning [g308: pB. 跳跳布朗尼(Brownie)](https://zerojudge.tw/ShowProblem?problemid=g308) + 使用布林陣列來記錄每個格子是否普經走過。 + 亦可直接使用記錄「傳送點資訊」的陣列，走過就設為「-1」。 ::: ### 2. 二維陣列 :::info EX_4_4：[a694: 吞食天地二](https://zerojudge.tw/ShowProblem?problemid=a694) + 前綴和 ![](https://hackmd.io/_uploads/r1vpzDlSn.png) **➜** ![](https://hackmd.io/_uploads/BJMRGvlr3.png) + [如何以a693的方式加速？](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/a694-tun-shi-tian-de-er) |[0][0] |[0][1]|[0][2] |[0][3] |[0][4]|[0][5] | |:----: |:----:|:----: |:----: |:----:|:----: | |**[1][0]**| | | | | | |**[2][0]**| |[r1-1][c1-1]| | |[r1-1][c2]| |**[3][0]**| | |[r1][c1]| | | |**[4][0]**| | | | | | |**[5][0]**| |[r2][c1-1] | | |[r2][c2] | + 陣列初值設為0 ``` c #include <cstring> memset(a,0,sizeof(a)); ``` + [C++ IO加速](https://blog.csdn.net/YinJianxiang/article/details/76436089)([原始網站](http://chino.taipei/note-2016-0311C-的輸出入cin-cout和scanf-printf誰比較快？/)) ``` c ios::sync_with_stdio(false); cin.tie(0); ``` ::: :::info EX_4_5：[e798: p5. 卷積神經網路](https://zerojudge.tw/ShowProblem?problemid=e798) + 求最大值可用max函式或if。 + max 若要傳入三個以上的參數，須用大括號包住([initializer_list](https://blog.csdn.net/ko_tin/article/details/68190364))，並含入 algorithm 標頭檔。 ::: :::warning [b367: 翻轉世界](https://zerojudge.tw/ShowProblem?problemid=b367) + 假設 a180 為 a 轉 180 度後的陣列，a[i][j] 轉180度後會放在 a180[r-i-1][c-j-1]; ::: :::warning [f513: 舉旗遊戲 (Flag)](https://zerojudge.tw/ShowProblem?problemid=f513) + 題目簡述 - 第一列有兩正整數 R、C（3 ≦ R、C ≦ 100），表示有 R×C 個人排成 R 列 C 行。 - 接著輸入 R 列，每列有 C 個正整數（1或2），代表每個人旗子的編號。 - 如果某人周遭的八個人，旗子的編號跟他都不一樣，則該人就被淘汰。請問有多少人會被淘汰？ + 陣列行、列可多開2個空間，index 0不要用，以免有些點的相鄰點會超出陣列。 + 如果自己的顏色和相鄰 8 點都不同，則淘汰人數+1。 ``` c if(a[i][j]!=a[i-1][j-1] && a[i][j]!=a[i-1][j] && a[i][j]!=a[i-1][j+1] && a[i][j]!=a[i][j-1] && ...) // 左上、上、右上、左 cnt++; ``` ::: :::warning [f418: Word Search Puzzle](https://zerojudge.tw/ShowProblem?problemid=f418) + char a[25][55]; + 不會有起始點在下，終點在上面的單字。 + 總共只有3種情況 - r1==r2 橫著印 - c1==c2 直著印 - 其它斜著印，從(r1+1,c1+1)，(r1+2,c1+2)......印到(r1+(r2-r1-1),c1+(c2-c1-1))，(r2,c2) ::: :::warning [e787: b2.尋寶地圖(Map)](https://zerojudge.tw/ShowProblem?problemid=e787) + 轉換圖計算行、列和時，重複算的要扣除。 + [題目](https://tpmso.org/toi/wp-content/uploads/question/201912/B2-Map.pdf) + [解題參考](https://tpmso.org/toi/wp-content/uploads/question/201912/B2-Map.pptx) ::: :::warning [f737: 農地 (Farmland)](https://zerojudge.tw/ShowProblem?problemid=f737) + 類似 a694 的方法，以前綴和的方式計算(1,1)到每個點的總成本，-1不能開墾，可以將其值設為比開墾總預算大的值。 + 針對每個點，窮舉計算所有邊長的正方形農地的成本和。 + 因為只要知道最大的開墾面積，所以每次計算可從目前最大邊長+1開始即可。如果點座標+邊長超出邊界，或成本和 > 總預算，則之後的邊長都不用再檢查。 + C++ IO加速。 + [解題參考](https://tpmso.org/toi/wp-content/uploads/question/202103/Farmland.odp) ::: :::warning [a867: 7. Minelayer](https://zerojudge.tw/ShowProblem?problemid=a867) + 可以從index 1 開始放，想像盤面最外圍包了一圈0，例如3x5的盤面： 0000000 0●●\*●\*0 0\*\*●●●0 0●\*\*●●0 0000000 + 宣告二維的字元陣列 char mine[17][32]={0}; int cnt[16][31]={0}; + 不需最外層的while() ::: :::warning [f148: 2. 定向越野 (Orienteering)](https://zerojudge.tw/ShowProblem?problemid=f148) + 可以宣告一個 arr[26][3] 的二維陣列，初值均為 0。 - 26 表示有 26 個字母，a 對應到index 0、b 對應到index 1 … - arr[ ][0]存字母是否存在，arr[ ][1]存列座標，arr[ ][2]存欄座標。 - 例如讀到 'a' 位於(0,2) arr[c-'a'][0]=1; arr[c-'a'][1]=0; arr[c-'a'][2]=2; + 當讀取的地圖字元不是'0' 時，標記此字元存在，記錄其座標，並累計目標數量。 + 如果目標數量＜N，輸出"Mission fail."。否則從陣列 0 開始判斷該位子對應的字元是否存在，如果存在則輸出座標，直到滿 N 個目標。 ::: ## 五、字串(字元陣列) ### 1. 字串宣告 ``` c int a[3]={1,2,3}; cout << a << endl; // 陣列名稱為陣列開始的位址 char c='x'; // 宣告字元 cout << c << endl; cout << (int)c << endl; // ASCII char s1[3]={'a','b','c'}; // 字元陣列，宣告長度為3的字串要多一個空間用來儲存空字元'\0'作為結束符號，否則會有錯誤 cout << s1 << endl; char s1[4]={'a','b','c','\0'}; cout << s1 << endl; string s2="abcd"; // 宣告string類別的字串 cout << s2 << endl; cout << s2[1] << endl; cout << s2.size() << endl; ``` ### 2. 字串相關操作 [演算法筆記](https://archive.is/u1lQL) :::info EX_5_1：[b428: 凱薩加密](https://zerojudge.tw/ShowProblem?problemid=b428) + if 或 % + Q：可以寫b[1]-a[1]嗎？ ::: :::info EX_5_2：[d235: Q10929:You can say 11](https://zerojudge.tw/ShowProblem?problemid=d235) + 11的倍數判別法：奇數位數字和與偶數位數字和相差為11的倍數。 + 字串長度：n.size() 或 n.length() + 取絕對值函式：abs() + [1～13的倍數判別法](https://leestar2013.pixnet.net/blog/post/45638266) ::: :::info EX_5_3：[c276: 沒有手機的下課時間](https://zerojudge.tw/ShowProblem?problemid=c276) ::: :::warning [a009: 解碼器](https://zerojudge.tw/ShowProblem?problemid=a009) ::: :::warning [a065: 提款卡密碼](https://zerojudge.tw/ShowProblem?problemid=a065) ::: :::warning [d124: 3的倍数](https://zerojudge.tw/ShowProblem?problemid=d124) + 3的倍數判別法：各個數字和為3的倍數。 ::: :::warning [a882: B. 我灰灰的橡皮鴨是個恐怖的危機](https://zerojudge.tw/ShowProblem?problemid=a882) ::: :::warning [b516: 凱撒密碼-商競103](https://zerojudge.tw/ShowProblem?problemid=b516) ::: :::warning [e505: 12602 - Nice Licence Plates](https://zerojudge.tw/ShowProblem?problemid=e505) + 取絕對值函式：abs() ::: :::warning [g006: 密碼備忘錄 (Password)](https://zerojudge.tw/ShowProblem?problemid=g006) + 以陣列儲存字母出現的次數(字母-'A'為索引值)。 + 因為最多100個字母，表示次數最大為100，由100->1檢查陣列中是否有這個次數，如果有則輸出(char)(索引值+'A') ::: ## 六、函式(遞迴) ### 1. 自定函式宣告語法 ``` c 回傳值的型態 函式名稱(變數型態 參數1，變數型態 參數2，...) { 程式碼 return 回傳值或運算式; } ``` :::info EX_6_1：[a623: 3. Combination](https://zerojudge.tw/ShowProblem?problemid=a623) + 將n!寫成函式，在主程式呼叫3次。 + $C(n,k)=\frac{n!}{(n-k)! * k!}$，例如C(4,2)=6。 ::: :::info EX_6_2：[d237: 質數合](https://zerojudge.tw/ShowProblem?problemid=d237) + 以質數函式測試是否需加此數。 + TLE如何解決 - long long sum=2; for(int i=3;i<=2000000;i+=2) - 如果一個數是合數，它的最小質因數會小於等於它的平方根。 - 因為成對出現的因數中，一個會 $\leq \sqrt n$，而另一個會 $\geq \sqrt n$。因此只要檢查 $\leq \sqrt n$ 中是否有 n 的因數即可。 - 開根號用sqrt()，需含入 cmath 標頭檔。 + 不可直接輸出142913828922(超過int)。 ::: :::warning [a121: 質數又來囉](https://zerojudge.tw/ShowProblem?problemid=a121) + 1不是質數。 ::: :::warning [b112: 5. 高中運動會](https://zerojudge.tw/ShowProblem?problemid=b112)。 + 寫一函式求兩數的最大公因數(輾轉相除法)。 ::: :::warning [f327: 刪除欄位](https://zerojudge.tw/ShowProblem?problemid=f327)。 + 寫一函式將輸入的字串轉成整數(26進位)，A為1，B為2，…，AA為27，AA為28，…。 + s[i]-'A'+1 ::: ### 2. 傳值(call by value)、傳參考(call by reference) :::info EX_6_3：[d491: 我也愛偶數 (swap 版)](https://zerojudge.tw/ShowProblem?problemid=d491) + 將兩數交換寫成函式。 + [等差數列](https://zh.wikipedia.org/wiki/%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97) + ((b-a)/2+1)/2*(a+b) 會錯誤，分子可能是奇數。 ::: ``` c= void swap(int ~a, int ~b) // void 表示沒有回傳值 { int t; ~ ~ ~ cout << "函式內："<< a << " " << b << endl; } int main() { int a=1,b=2; cout << "交換前：" << a << " " << b << endl; swap(a,b); cout << "交換後：" << a << " " << b << endl; return 0; } ``` ### 3. 遞迴 :mega: 問題的答案，可從同類的子問題(規模更小)得到。 :mega: 在函式之中呼叫函式自己本身，要有終止條件，不然會無窮遞迴下去。 :::info EX_6_4：[95數學學測填充題G](http://cs.cysh.cy.edu.tw/computer_concept_108/高中數學遞迴.pdf) 用黑、白兩種顏色的正方形地磚依照如下的規律拼成若干圖形： ![](https://i.imgur.com/PrDcedl.jpg) 拼第95個圖需用到幾塊白色地磚。(478) ::: ``` c= int f(int n) { if ~ // if後只有一行，可省略{} ~ else return ~ } int main() { int n; while(cin >> n) cout << f(n) << endl; // 5->28 return 0; } ``` :::info EX_6_5：[a044: 空間切割](https://zerojudge.tw/ShowProblem?problemid=a044) + [直線分割平面](https://www.youtube.com/watch?v=wcvpvWxf-Kw) - b~n~=b~n-1~+n，b~1~=2 + [平面分割空間](https://www.youtube.com/watch?v=Fjd6Oz_cgYY) - c~n~=c~n-1~+b~n-1~，c~1~=2 ::: :::warning [a623: 3. Combination](https://zerojudge.tw/ShowProblem?problemid=a623) + 以遞迴改寫。 + $C^n_k = C^{n-1}_k + C^{n-1}_{k-1}$ + $n==k \ || \ k==0$ 時，只有一種組合方式。 ::: :::warning [e357: 遞迴函數練習](https://zerojudge.tw/ShowProblem?problemid=e357) ::: :::warning [c002: 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002) ::: ## 七、其它 ### 1. [結構(struct)](https://kopu.chat/2017/05/30/c-%E8%AA%9E%E8%A8%80%EF%BC%9A%E7%B5%90%E6%A7%8B%EF%BC%88struct%EF%BC%89%E8%87%AA%E8%A8%82%E4%B8%8D%E5%90%8C%E8%B3%87%E6%96%99%E5%9E%8B%E6%85%8B%E7%B6%81%E4%B8%80%E8%B5%B7/) ``` c // 自訂的資料型別 struct 結構名稱 { 資料型別 變數1; 資料型別 變數2; ... }; ``` :mega: struct 定義的最後面要加分號！ :::info EX_7_1：[c316: 最遠點對！前傳](https://zerojudge.tw/ShowProblem?problemid=c316) ::: :::warning [a130: 12015 - Google is Feeling Lucky](https://zerojudge.tw/ShowProblem?problemid=a130) ::: :::warning [d809: 黑暗土地](https://zerojudge.tw/ShowProblem?problemid=d809) + [以行列式算三角形面積](http://euler.tn.edu.tw/area.pdf)，避免浮點數誤差。 + 取絕對值函式：abs() + 要印出面積時再/2.0。 :::
Last changed by  
 
cube lin
12788
Published on HackMD