###### 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)
+ 前綴和  **➜** 
+ [如何以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)
用黑、白兩種顏色的正方形地磚依照如下的規律拼成若干圖形：
拼第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。
:::
Sign in with Wallet
Connect another wallet