owned this note
owned this note
Published
Linked with GitHub
# 初學者也適用的ZeroJudge C++詳解
**感謝指導老師 方珮雯老師持續從旁協助!**
## 選擇結構
### [d485:我愛偶數](https://zerojudge.tw/ShowProblem?problemid=d485)
**<題目>**
文文很喜歡偶數，他甚至有收集偶數的習慣。你給他一個範圍的連續整數，他就會把其中的偶數留下來收藏。如今他又拿到了一個範圍的整數，請問他這次收藏了幾個偶數？對文文來說，0 也算是一個偶數哦！
**輸入說明**
輸入只有一行，其中含有兩個由空白隔開的整數 a, b (0 ≤ a ≤ b ≤ 2147483647)。
**範例輸入**
1 4
**輸出說明**
輸出一個整數，代表 a 與 b 之間 (含 a 與 b) 一共有多少個偶數。
**範例輸出**
2
**解題思路**
a和b的奇偶性會影響範圍內的偶數數量，因此可先以選擇結構，判斷a和b是奇數還是偶數，再根據不同的情形討論。
我們可以嘗試舉數字做為例子，討論a和b的奇偶性和範圍內偶數數量的關係。當a為偶數，b為偶數時，範圍內的偶數共有(b-a)/2+1個 ; 當a為偶數，b為奇數時，範圍內的偶數共有(b-a+1)/2個 ; 當a為奇數，b為偶數時，範圍內的偶數共有(b-a+1)/2個 ; 當a為奇數，b為奇數時，範圍內的偶數共有(b-a)/2個。
:::info
**注意事項**
一般在宣告整數型變數時，使用的[資料型態](https://docs.microsoft.com/zh-tw/cpp/cpp/data-type-ranges?view=msvc-170)是int，值的範圍在-2147483648至2147483647之間。而由輸入說明可知0 ≤ a ≤ b ≤ 2147483647，雖然輸入的數值本身在範圍內，但若是輸入的數值較大，在運算時可能出現溢位的情形。故以下程式碼會以同樣是整數型變數，值的範圍較int大的資料型態long long宣告變數。在參與程式競賽時，如果想避免測資的數值過大導致溢位，也可以如以下程式碼做法，以long long宣告整數型態的變數比較保險。
除此之外，還有一件值得注意的事，就是這裡的a和b並非同一個數。想一想，如果是同一個數的話，會發生什麼事呢?(參[c022:Odd Sum](https://hackmd.io/PiBwttGcSKOkL1VIshPI_w?view#c022Odd-Sum))
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
long long a,b; //注意int的位數限制，小心選取資料型態以免溢位
long long sum=0;
cin >> a >> b;
if(a%2==0) //若a為偶數
if(b%2==0) //若b為偶數
sum=(b-a)/2+1;
else //若b為奇數
sum=(b-a+1)/2; //注意int為整數型態，遇到小數會自動無條件捨去，故(a+b)/2+1/2和(a+b+1)/2結果可能不同
else //若a為奇數
if(b%2==0) //若b為偶數
sum=(b-a+1)/2;
else //若b為奇數
sum=(b-a)/2;
cout << sum << endl;
return 0; //返回值設為零
}
```
### [d827:買鉛筆](https://zerojudge.tw/ShowProblem?problemid=d827)
**<題目>**
鉛筆一支 5 元，一打 50 元。小明需要幫班上每位同學買一枝鉛筆，請問要多少錢？由於小明很注重環保，他絕不會為了省錢而多買任何不需要的東西。也就是說，小明買的鉛筆數量一定等於班上的人數。
**輸入說明**
輸入只有一行，含有小明班上的人數 n ， 1 ≤ n ≤ 200。
**範例輸入**
42
**輸出說明**
請輸出一個數字，代表這次採購的金額。
**範例輸出**
180
**解題思路**
鉛筆一支5元，一打十二支50元，以一打做為購買單位較便宜，由此可知在正常情況下，只要所需購買的鉛筆總數大於等於十二支，小明都會以一打做為購買單位，可先以選擇結構判斷小明購買的鉛筆總數大於等於還是少於十二隻，再輸出相對應的輸出。
我們可以依照n的數值將購買鉛筆的情況分為兩類。當n<12時，小明會以一支做為購買單位；當n≥12時，小明會先以一打做為購買單位，剩下的鉛筆再以一支做為購買單位。
:::info
**注意事項**
考量到除法會有除不進的情況，可能會有人思考，當所需購買的鉛筆總數無法被12整除時要如何取商數。事實上在C++的語法中，當[資料型態](https://openhome.cc/Gossip/CGossip/Datatype.html)設定為整數，而實際數值為浮點數時，會無條件捨去。故本題其實也可不用選擇結構，直接將代表所需購買鉛筆打數的變數設為整數型態，再將所需購買的鉛筆總數除以12即可。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int n; //宣告變數n，代表鉛筆支數
cin >> n;
int m=n/12; //int的資料型態為整數，因此當除數出現小數時，會因為其不符合宣告的資料型態，將之無條件捨去
cout << 50*m+5*(n-12*m) << endl; //鉛筆一打50元，一支5元
return 0; //返回值設為零
}
```
### [d066:上學去吧!](https://zerojudge.tw/ShowProblem?problemid=d066)
**<題目>**
板橋高中規定同學必須在 7:30 以前到校早自習，最後一堂課則在 17:00 下課。給你現在的時間，請判斷現在是不是必須在學校的時間。
**輸入說明**
輸入只有一行，其中含有兩個由空隔開的整數 hh 及 mm ， hh : mm 則代表現在的時間(24小時制)。
**範例輸入**
17 00
**輸出說明**
如果現在是上學時間，請輸出「At School」，否則請輸出「Off School」
**範例輸出**
Off School
**解題思路**
由題意可知上學時間和非上學時間各有不同的輸出，可先以選擇結構判斷輸入之時段是上學時間還是非上學時間，再輸出相對應的輸出。
我們可以依照hh的數值，將一天中的時段所對應的情況分為三類。當hh=7時，00≤mm≤29時為非上學時間，30≤mm≤59時為上學時間；當08≤hh≤16時，不論mm的數值為何，皆為上學時間；當00≤hh<07或17≤hh≤24時，不論mm的數值為何，皆為非上學時間。
:::info
**注意事項**
本題時間表示採用24小時制，故當hh<00或24<hh時，hh不具備意義，為不合理的輸入。同理，當mm<00或是mm≥60時，mm不具備意義，為不合理的輸入。此題並未特別討論不合理輸入的情況，但若是題目有要求，就必須在編寫if函數式時一併討論。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int hh,mm; //宣告變數hh，代表小時;變數mm，代表分鐘
cin >> hh >> mm;
if(hh==7){ //當hh=7時
if(00<=mm&&mm<=29) //00<=mm<=29時為非上學時間
cout << "Off School" << endl;
if(30<=mm&&mm<=59) //30<=mm<=59時為上學時間
cout << "At School" << endl;
}
else if(08<hh&&hh<=16) //當08<hh<=16時，不論mm的數值為何，皆為上學時間
cout << "At School" << endl;
else if(00<hh&&hh<07||17<=hh&&hh<=24) //當00<hh<07或17<=hh<=24時，不論mm的數值為何，皆為非上學時間
cout << "Off School" << endl;
return 0; //返回值設為零
}
```
### [d060:還要等多久啊?](https://zerojudge.tw/ShowProblem?problemid=d060)
**<題目>**
文文又想打電話給珊珊，可是這次他碰到了另一個問題。珊珊說他們學校每堂課 50 分鐘，下課的時間都是整點過後 25 分，休息 10 鐘後再上下一節課。文文不想打擾珊珊上課，也不想才剛打通電話她就要上課去了，因此他決定一定要在剛好 25 分的時候打電話給她。給你現在的時間的分，請你幫他算算看還要等多久才能打電話給珊珊？
**輸入說明**
輸入只有一行，包含現在時間的分 m (0 ≤ m ≤ 59)。
**範例輸入**
20
**輸出說明**
輸出還要等幾分鐘文文才能打電話。
**範例輸出**
5
**解題思路**
由題意可知文文只會在剛好25分時打電話給珊珊，故必須先用選擇結構判斷該小時的25分是否已過。
當00≤m≤25時，文文還要再等(25-m)分鐘；當26≤m≤59時，文文還要再等(60+(25-m))=(85-m)分鐘。
:::info
**注意事項**
同[d066:上學去吧!](https://hackmd.io/PiBwttGcSKOkL1VIshPI_w?view#d066%E4%B8%8A%E5%AD%B8%E5%8E%BB%E5%90%A7)的注意事項所述，m的數值理論上必須符合0<=m<=59。雖然此題並未特別討論不合理輸入的情況，但若是題目有要求，就必須在編寫if函數式時一併討論
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int m; //宣告變數m，代表現在時間
cin >> m;
if(00<=m&&m<=25) //當00<=m<=25時
cout << 25-m << endl; //文文還要再等(25-m)分鐘
else if(26<=m&&m<=59) //當25<=m<=59時
cout << 85-m << endl; //文文還要再等(85-m)分鐘
return 0; //返回值設為零
}
```
### [d507:三角形的判斷題目](https://zerojudge.tw/ShowProblem?problemid=d507)
**<題目>**
給你一個三角形的邊長，請你判斷它是銳角 (acute)、直角 (right)、或是鈍角 (obtuse) 三角形。
**輸入說明**
輸入只有一行，含有三個由空白隔開的正整數 a, b, c (0 < a, b, c ≤ 32767)，代表三角形的邊長。
**範例輸入**
3 4 5
**輸出說明**
依三角形的類別輸出「acute triangle」、「right triangle」、或「obtuse triangle」。
**範例輸出**
right triangle
**解題思路**
由數學上[勾股定理的逆定理](https://baike.baidu.hk/item/%E5%8B%BE%E8%82%A1%E5%AE%9A%E7%90%86%E7%9A%84%E9%80%86%E5%AE%9A%E7%90%86/4353342)可知，設一三角形邊長分別為a,b,c，且a為最大邊，當a^2^<b^2^+c^2^時，此三角形為銳角三角形；當a^2^=b^2^+c^2^時，此三角形為直角三角形；當a^2^>b^2^+c^2^時，此三角形為鈍角三角形。故必須利用選擇結構判斷最大邊平方及另兩邊平方和之間的大小關係。
:::info
**注意事項**
要判斷a,b,c三者中哪一邊為最大邊，可利用[基礎排序法](https://blog.techbridge.cc/2019/03/10/computer-science-sorting-algorithm-part1/)，如[氣泡排序法](https://www.google.com/search?q=%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95&oq=%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95&aqs=edge.0.69i59&sourceid=chrome&ie=UTF-8)、[選擇排序法](https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/selection_sort.html)、[插入排序法](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E5%85%A5%E9%96%80-%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F%E8%88%87%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-23d4bc7085ff)等，亦可使用以下程式碼使用的sort函數。但sort函數不在[標準函式庫](https://https://zh.wikipedia.org/wiki/%E6%A0%87%E5%87%86%E5%BA%93)裡，使用前必須引用algorithm函式庫。
:::
**程式碼**
```C++=
#include<iostream>
#include<algorithm> //C++的函式庫之一，內含本程式碼等一下會用到的sort函數
using namespace std;
int main(){
int a,b,c; //宣告變數a,b,c，分別代表三角形的三個邊長
cin >> a >> b >> c;
int S[]={a,b,c};
sort(S,S+3); //sort函數可將陣列的元素依數值大小排序，寫法為sort(陣列名稱,陣列名稱+元素數)
if(S[2]*S[2]<S[1]*S[1]+S[0]*S[0]) //當最大邊平方小於另兩邊平方和時
cout << "acute triangle" << endl; //三角形為銳角三角形
else if(S[2]*S[2]==S[1]*S[1]+S[0]*S[0]) //當最大邊平方等於另兩邊平方和時
cout << "right triangle" << endl; //三角形為直角三角形
else if(S[2]*S[2]>S[1]*S[1]+S[0]*S[0]) //當最大邊平方大於另兩邊平方和時
cout << "obtuse triangle" << endl; //三角形為鈍角三角形
return 0; //返回值設為零
}
```
## 迴圈
### [b970:我不說髒話(續)](https://zerojudge.tw/ShowProblem?problemid=b970)
**<題目>**
文文上次說髒話被老師罰在黑板上寫 50 遍「I don’t say swear words!」，結果他只寫了 45 遍就跑出去玩了，以為老師不會發現。這次老師要求他罰寫的每一遍都要加上編號。
**輸入說明**
輸入只有一行，其中含有一個正整數 n，代表文文被罰寫的次數。
**範例輸入**
10
**輸出說明**
輸出 n 行「I don’t say swear words!」，每行前面要有流水編號。請參考範例輸出。
**範例輸出**
1. I don't say swear words!
2. I don't say swear words!
3. I don't say swear words!
4. I don't say swear words!
5. I don't say swear words!
6. I don't say swear words!
7. I don't say swear words!
8. I don't say swear words!
9. I don't say swear words!
10. I don't say swear words!
**解題思路**
由題目可知必須輸出n行指定的句子，且每一行均需編號。我們可以利用for迴圈中，計數變數i每運算一次就會加一的特性，輸出相對應的輸出。
:::info
**注意事項**
for迴圈的運作機制是跑完迴圈內的程式後，將計數變數i的值+1，再檢查i值是否仍符合條件限制，以決定是否繼續執行迴圈內的程式，也就是說每次要執行迴圈內的程式前都會先檢查i值。因此以下程式碼中，for迴圈的執行條件為i≤n，以確保當i=n時，第n行能順利輸出。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int n; //宣告變數n，代表輸出(罰寫)的行數
cin >> n;
for(int i=1;i<=n;i++){ //當i≤n時，執行for迴圈內的程式，並且每執行完一次迴圈內的程式，i值都會加一
cout << i << ". I don't say swear words!" << endl; //點點和空白記得也要輸出
}
return 0; //返回值設為零
}
```
### [a005:EVA的回家作業](https://zerojudge.tw/ShowProblem?problemid=a005)
**<題目>**
Eva的家庭作業裏有很多數列填空練習。填空練習的要求是：已知數列的前四項，填出第五項。因 為已經知道這些數列只可能是等差或等比數列，她決定寫一個程式來完成這些練習。
**輸入說明**
第一行是數列的數目t（0 <= t <= 20）。 以下每行均包含四個整數，表示數列的前四項。 約定數列的前五項均為不大於105的自然數，等比數列的比值也是自然數。
**範例輸入**
2
1 2 3 4
1 2 4 8
**輸出說明**
對輸入的每個數列，輸出它的前五項。
**範例輸出**
1 2 3 4 5
1 2 4 8 16
**解題思路**
由題目可知輸入的數列只有等差數列或等比數列兩種可能，先用選擇結構檢查輸入之數列為等差數列還是等比數列，再依據等差數列兩相鄰項差相同、等比數列兩相鄰項比相同的性質推知第五項。
:::info
**注意事項**
一般的程式題目可依輸入資料的組數分為只有一組輸入、給定組數的輸入以及無限制組數輸入三種。本文前面的題目皆屬於第一種，而本題即屬於第二種。為了確保程式運算的組數恰等於題目要求的輸入組數，可利用for迴圈運算。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int t,i; //宣告變數t，代表測試資料組數;變數i，用來計數
int a,b,c,d,e; //宣告變數a,b,c,d,e，分別代表數列前五項
cin >> t;
for(i=1;i<=t;i++){
cin >> a >> b >> c >> d; //輸入數列前四項
if(b-a==c-b){ //當兩相鄰項差同時，輸入數列為等差數列
e=d+(d-c); //第五項等於第四項加上公差
cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << endl;
}
else if(b/a==c/b){ //當兩相鄰項比相同時，輸入數列為等比數列
e=d*(d/c); //第五項等於第四項乘上公比
cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << endl;
}
}
return 0; //返回值設為零
}
```
### [a215:明明愛數數](https://zerojudge.tw/ShowProblem?problemid=a215)
**<題目>**
明明是一個愛數（ㄕㄨˇ）數（ㄕㄨˋ）的好學生，這天媽媽叫他從 n 開始數，下一個數字是 n+1，再下一個數字是 n+2，以此類推。媽媽想知道，明明數了幾個數字之後，他數過的這些數字的總和會超過 m。請幫助明明的媽媽吧。
**輸入說明**
輸入以 EOF 結束。每一筆測試資料有兩個數字，分別為 n 和 m，其中 m-n 不會超過 10^5。
**範例輸入**
1 5
5 10
100 1000
**輸出說明**
輸出如題目敘述。
**範例輸出**
3
2
10
**解題思路**
由題目可知輸入的數字所組成的數列為一首項為n，公差為1的等差數列，故其實題目的意思就是要求此一等差數列的級數和在第幾項時恰大於m。我們可以設最初的等差級數和為n，再利用while迴圈計算下一項的值，並在級數和大於m的時候跳出迴圈。
:::info
**注意事項**
在[EVA的回家作業](https://hackmd.io/PiBwttGcSKOkL1VIshPI_w?view#a005EVA%E7%9A%84%E5%9B%9E%E5%AE%B6%E4%BD%9C%E6%A5%AD)有提到，一般的程式題目可依輸入資料的組數分為只有一組輸入、給定組數的輸入以及無限制組數輸入三種，本題即屬於第三種。為了確保程式只要有輸入即有輸出，可利用while迴圈包住欲執行的程式碼，並設定只要有輸入，即執行while迴圈。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int n,m; //宣告變數n，代表明明數的第一個數字(首項);變數m，代表預期的數字總和(等差級數和)
while(cin >> n >> m){ //當輸入n,m時，執行while迴圈
int sum=n; //宣告變數sum，代表實際的數字總和，初始值為n
int i=0; //宣告變數i，用來計數，初始值為0
while(sum<=m){
n++; //明明所數的數字(等差數列)，後項比前項多1
sum=sum+n; //每多數一個數字，實際數字總和就多一項的值
i++; //計數用，程式每運算一次，i值+1
}
cout << i+1 << endl; //注意明明是先數數，再回頭檢查sum是否超過m，所以實際上數到的數字會比理論上該停的數字多一個
}
return 0; //返回值設為零
}
```
### [c022:Odd Sum](https://zerojudge.tw/ShowProblem?problemid=c022)
**<題目>**
給你一個範圍 a 到 b ，請你找出 a 與 b 之間所有奇數的和。
例如：範圍 [3, 9] 中所有奇數的和就是 3 + 5 + 7 + 9 = 24 。
**輸入說明**
輸入的第一列有一個整數 T （1≦T≦100），代表以下有多少組測試資料。 每組測試資料為兩列，包含兩個數 a 與 b （0≦a≦b≦100）。
**範例輸入**
2
1
5
3
5
**輸出說明**
每組測試資料輸出一列，內容為 a 及 b 間所有奇數的和。
**範例輸出**
Case 1: 9
Case 2: 8
**解題思路**
其實這一題的概念和[d485:我愛偶數](https://hackmd.io/PiBwttGcSKOkL1VIshPI_w?view#d485%E6%88%91%E6%84%9B%E5%81%B6%E6%95%B8)非常接近，只是那題要找的是範圍內的「偶數」「個數總和」，這題要找的是範圍內的「奇數」「和」。
但這並非兩題僅存的差別，最大的差別其實是在我愛偶數一題中的注意事項提到的，a和b的值是否相同。不同於我愛偶數一題，在本題的條件中，a和b的值是可以一樣的，必須特別討論，而這也是讓本題成為難題的關鍵!
**注意事項**
:::info
以下程式碼中大量使用各種選擇結構與迴圈，可說是CH1與CH2的學習總驗收。尤其須特別留意變數值的改變，以確保迴圈的執行條件能順利執行。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
long long T,a,b; //宣告變數T，代表測試資料組數;變數a，代表起始數字;變數b，代表終止數字
long long sum=0; //宣告變數sum，代表a至b之間的奇數和
long long i=0; //宣告變數i，用來計數，初始值為0
cin >> T;
for(i=0;i<T;i++){ //當i<T，執行for迴圈
cin >> a >> b;
if(a%2==0){ //若a為偶數
if(a==b){ //若a等於b
a=0;
b = 0; //注意要讓b一起等於0，否則執行第30行會很可怕
}
else //若a不等於b
a=a+1; //a從a+1(奇數)開始
}
else //若a為奇數
a=a; //a從a(奇數)開始
sum=a;
if(a!=b){
// 問題：不知道a+2有沒有超過範圍。
while(a+2<b){ //當a+2<b，執行while迴圈
a=a+2;
sum=sum+a;
}
}
cout << "Case " << i+1 << ": " << sum << endl; //因為i值的初始值定義為零，所以要顯示現在的i值加一
}
return 0; //返回值設為零
}
```
### [c420:Bert的三角形(3)](https://zerojudge.tw/ShowProblem?problemid=c420)
**<題目>**
Bert 有天騎著海豚到了埃及，看到了金字塔不經意的發出『 哇～～ 』
現在 Bert 想請你用程式記下金字塔的樣子～～
現在有一種 n 層的三金字塔，定義如下:
第 i 層要有相對數量的 " * "，請注意要像金字塔一樣向中間對齊
請你寫個程式幫幫 Bert ~~
**輸入說明**
單筆輸入~~
輸入只有一個整數 n (1 <= n <= 100)
n 保證為奇數
**範例輸入**
3
**輸出說明**
輸出整個三角形~~
因為空格不好辨識，請以"_" 代替 ~~
**範例輸出**
**解題思路**
本題極其複雜，關鍵是透過圖形呈現對稱，還有分層計算所對應的符號數量兩個技巧，發現各層所需的各個符號數量恰好成等差數列。
首先是圖形呈現對稱。這點難度不高，可以從觀察圖形得知，但它卻提供了我們解題時很重要的想法 : 將圖形分成在圖形正中間的 * ，在 * 左邊的 _ ，和在 * 右邊的 _ 三個區塊討論。
再來是每一層的 * 和 _ 的個數呈現等差數列。雖然題目的要求是輸出一座金字塔，但考慮到實際上輸出的時候是一行一行輸出，因此我們可以將金字塔分成一層一層來討論所需輸出的情況。由題目可知金字塔各行的情況可依照有沒有 _ 分為兩種。當i=n時，代表第n層，不會有任何的 _ ; 當i≠n時，代表第i層之上的各層，除了 * 以外還會有_。故在討論時，必須分清討論的對象。
綜合上述兩個技巧，我們可以發現圖形左側的 _ 、 正中間的 * 和右邊的 _ ，在每一行對應的數量各自為等差數列。其中圖形正中間的 * 個數a會是一首項為1，公差為2的等差數列，和i的關係式為a=1+(i-1) * 2。而左右兩邊 _ 的個數則分別為金字塔最大底邊減掉正中間的 * 的一半。
:::info
**注意事項**
再次強調，每一層的*和_的個數呈等差數列，是本題解題的關鍵。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int n; //宣告變數n，代表輸出總行數(金子塔的層數)，必為奇數
cin >> n;
for(int i=1;i<=n;i++){ //宣告變數i，代表行數
int a=1+((i-1)*2); //宣告變數a，代表第i行中間的 *的數量，為一首項為1，公差為2的等差數列，必為奇數
int b=1+((n-1)*2); //宣告變數b，代表第n行中間的*的數量
for(int x=0;x<((b-a)/2);x++){ //宣告變數x，代表*左邊_的個數
cout << "_";
}
for(int y=0;y<a;y++){ //宣告變數y，代表正中間的*的個數
cout << "*";
}
for(int z=0;z<((b-a)/2);z++){ //宣告變數z，代表*右邊_的個數
cout << "_";
}
cout << endl;
}
return 0; //返回值設為零
}
```
### [a059:完全平方和](https://zerojudge.tw/ShowProblem?problemid=a059)
**<題目>**
給你一個範圍 a 到 b ，請你找出 a 與 b 之間所有完全平方數的和。
例如：範圍 [3, 25] 中所有完全平方數的和就是 4 + 9 + 16 + 25 = 54 。
**輸入說明**
輸入的第一列有一個整數 T （1≦T≦100），代表以下有多少組測試資料。
每組測試資料為兩列，包含兩個數 a 與 b （0≦a≦b≦1000）。
**範例輸入**
2
1
5
5
35
**輸出說明**
每組測試資料輸出一列，內容為 a 及 b 間所有完全平方數的和。
**範例輸出**
Case 1: 5
Case 2: 50
**解題思路**
設x^2^為在a及b間的任一完全平方數，可知√a≤x≤√b，故只要找出在√a及√b之間的正整數，其平方即為在a及b間的完全平方數，進而求出和。
:::info
**注意事項**
以下程式碼使用了幾個特殊的函數來簡化程式:
sqrt函數:開根號。
ceil函數:ceil在英文中是天花板的意思，因此ceil函數其實就是無條件進位。
floor函數:floor在英文中是地板的意思，因此floor函數其實就是無條件捨去。
但以上幾個函數都不在標準函式庫裡，使用前必須引用cmath函式庫。
:::
**程式碼**
```C++=
#include<iostream>
#include <cmath>
using namespace std;
int main(){
int T,a,b; //宣告變數T，代表測試資料組數
cin >> T;
for(int i=0;i<T;i++){
cin >> a >> b;
int x=ceil(sqrt(a)); //ceil函數可用來無條件進位小數，寫法為ceil(待無條件進位的浮點數值)
int y=floor(sqrt(b)); //for函數可用來無條件捨去小數，寫法為floor(待無條件捨去的浮點數值)
int sum=0;
while(x<=y){
sum=sum+x*x;
x=x+1;
}
cout << "Case " << i+1 << ": " << sum << endl;
}
return 0; //返回值設為零
}
```
### [d010:盈數、虧數和完全數](https://zerojudge.tw/ShowProblem?problemid=d010)
**<題目>**
對一個正整數 N 而言，將它除了本身以外所有的因數加起來的總和為 S，如果 S>N，則 N 為盈數，如果 S<N，則 N 為虧數，而如果 S=N，則 N 為完全數(Perfect Number)。例如 10 的因數有 1、2、5、10，1+2+5=8<10，因此10 為虧數，而 12 的因數有 1、2、3、4、6、12，1+2+3+4+6=16>12，因此 12 為盈數。至於 6 的因數有 1、2、3、6，1+2+3=6，所以 6 是完全數(它也是第一個完全數)。
現在請你寫一個程式，輸入一個正整數 N，然後印出它是盈數、虧數還是完全數。
**範例輸入**
30
26
28
**範例輸出**
盈數
虧數
完全數
**解題思路**
關鍵在於找出N的所有因數，即可用選擇結構判斷N為盈數、虧數還是完全數，並輸出相對應的輸出。
:::info
**注意事項**
找出一數的所有因數不只一種解法，我的解法是用逐一檢查的。設x為小於等於N的正整數，設y為N除以x所得的除數。因為y為整數型態的變數，因此當N無法被x整除的時候，y值會自動無條件捨去到整數([參d827:買鉛筆的注意事項](https://hackmd.io/PiBwttGcSKOkL1VIshPI_w?view#d827買鉛筆))，也就是說此時的y值已經與除數不同。故當N=x * y時，代表N可被x整除，即x為N的因數 ; 當N≠x * y時，代表N不可被x整除，即不為N的因數。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int N; //宣告變數N，代表要判斷的正整數
while(cin >> N){
int S=0; //宣告變數S，代表N的因數和
for(int x=1;x<N;x++){ //宣告變數x，代表小於等於N的正整數，並且透過for迴圈讓x值逐次加一
int y=N/x; //宣告變數y為N除以x的除數。由於y為整數行變數，因此運算後所得的值若非整數，將自動無條件捨去(參買鉛筆的注意事項)
if(N==x*y) //當N=x*y時，x為N的因數
S=S+x; //S值加上x
}
if(S>N) //當S>N時
cout << "盈數" << endl; //N為盈數
else if(S==N) //當S=N時
cout << "完全數" << endl; //N為完全數
else if(S<N) //當S<N時
cout << "虧數" << endl; //N為虧數
}
return 0; //返回值設為零
}
```
### [a040:阿姆斯壯數](https://zerojudge.tw/ShowProblem?problemid=a040)
**<題目>**
所謂 Armstrong number 指的是一個 n 位數的整數，它的所有位數的 n 次方和恰好等於自己。
如；1634 = 1^4^+6^4^+3^4^+4^4^
請依題目需求在一定範圍內找出該範圍內的所有 armstrong numbers.
**輸入說明**
輸入共一行包含兩個數字n, m(n<m, n>0, m<=1000000)，代表所有尋找 armstrong number 的範圍
**範例輸入**
100 999
**輸出說明**
將所有範圍內的 armstrong number 依序由小到大輸出，如果沒有找到請輸出 none.
**範例輸出**
153 370 371 407
**解題思路**
由題目可知阿姆斯壯數的判斷方法為將待判斷的數字依照位數分拆成各個數字後，依照待判斷數字的位數n次方後，再判斷各位數的次方和是否等於待判斷的數字。故本題的關鍵在於判斷輸入數字的位數，才能知道要幾次方。
以下的程式碼中，第二個while迴圈(第19行到第24行)和第三個while迴圈(第29行到第35行)的程式雖然長得很像，功能也差不多，但對於程式碼的意義不太一樣。第二個while迴圈是在判斷輸入數字的位數，而第三個while迴圈是利用第二個while迴圈求得的位數，求出其各個數字的位數次方和。
:::info
**注意事項**
本題也是難題，尤其迴圈的使用量龐大，在變數宣告與定義初始值時須特別留意要寫在迴圈內還是迴圈外，如果變數在接下來的運算中還會用到，但初始值已經被在經過前一次的運算後改變了，就必須重新定義初始值。
另外本題中使用了pow函數，用來表示指數，一樣並非標準函式庫裡的函數，使用前必須先引用cmath函式庫
:::
**程式碼**
```C++=
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n,m; //宣告變數n,m
cin >> n >> m;
int W, w; //宣告變數W,w。注意在這裡先不要急著定義初始值，因為每次執行底下的while迴圈，W和w的值都會改變，必須再次定義，因此須在while迴圈裡定義W和w的初始值
int x=n; //宣告變數x，代表要判斷的數字。初始值為n，其值必小於m
int j=0; //宣告變數j，用來計數
while(x<m){
W = x;
w = x;
int i = 0; //宣告變數i，用來計數。因為每一輪都會重新計算位數，所以必須在此定義初始值為0(歸零)
while(W>0){ //判斷輸入數字的位數。注意直觀上可能會把while迴圈的執行條件寫成w>=10，但要小心這樣寫的話會少算到個位數，導致計算出的位數比實際位數少1
int y=W/10; //整數除法時，用/除法會自動無條件捨去至整數
int z=W-10*y;
W=y;
i++;
}
int sum = 0;//sum每次也要重新計算，所以在此歸零
int y, z, c; //宣告變數y,z,c
while(w>0){ //判斷各項數字的位數次方和
y=w/10;
z=w-10*y;
c=pow(z,i); //pow函數可以用來表示任何數字的任何次方，寫法為pow(底數(變數值),次方數)
sum=sum+c;
w=y;
}
if(sum==x){ //若各位數字的位數次方和和等於待測數字，即為阿姆斯壯數
cout << x << " "; //輸出此次判斷的數字
j++;
}
x++;
}
if(j==0) //若無阿姆斯壯數
cout << "none" << endl; //輸出none
return 0; //返回值設為零
}
```
## 一維陣列
### [d074:電腦教室](https://zerojudge.tw/ShowProblem?problemid=d074)
**<題目>**
蝸牛老師在一所優質高中擔任電腦老師，在學校裡有一間他專用的電腦教室。最近學校有一筆經費要幫這個電腦教室更新電腦。學校的原則是，每個上課的學生都要有自己的電腦，但是不希望購買多餘的電腦。給你蝸牛老師的任教班級數及每班人數，請你幫他算出要買幾部新電腦給學生使用。
**輸入說明**
輸入只有兩行。第一行有一個正整數 n (n≤10)，代表蝸牛老師的任教班級數。第二行有 n 個由空白隔開的正整數，代表各班人數。
**範例輸入**
5
42 39 41 43 30
**輸出說明**
輸出需購買的電腦數量。
**範例輸出**
43
**解題思路**
每個上課的學生都要有自己的電腦，但又不希望購買多餘的電腦，代表電腦總數必須恰等於人數最多的班級的人數，因此本題的關鍵其實是在輸入的諸多數字中找出最大值。
我們可以利用陣列，將輸入的諸多數字逐一對應到陣列的各元素中儲存起來。先設變數max為陣列的各元素中的最大的值，並將之定義為第一個元素，然後由此往後，逐一檢查，只要有元素的值大於max，就將之定義為max的新值。如此，最後的max值就是各元素中的最大值。
:::info
**注意事項**
一般來說，程式碼的變數大多為單個字元，但其我們也可以將之用字串表示，如以下程式碼的"max"即是如此。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
long long n; //宣告變數n，代表蝸牛老師的任教班級數(等等宣告的陣列的大小)
cin >> n;
long long CC[n]; //宣告陣列cc[]，代表各班人數，同時宣告大小
for(long long i=0;i<n;i++){
cin >> CC[i]; //輸入數字(各班人數)，並將之儲存到對應的陣列元素中
}
long long max=CC[0]; //宣告變數max，代表人數最多的班級的人數。此時暫且將之設為CC[0]，等等在for迴圈中會逐一檢查
for(long long j=1;j<n;j++){ //逐一檢查陣列各元素
if(CC[j]>max) //若有元素大於現在的max值
max=CC[j]; //將之定義為新的max
}
cout << max << endl;
return 0; //返回值設為零
}
```
## CH4 TOI競賽
### [衛星列車 (Comet)](https://zerojudge.tw/ShowProblem?problemid=g496)
**<題目>**
彗星姊姊最近製造了一台列車,並以其名命名為「彗星列車」,這台彗星列車最大的特點就是會以每秒固定的加速度不斷提升速度。舉例來說,如果彗星列車想要從靜止加速到 100 km/s (秒速 100 公里),且列車的加速度是 25 km/s,只需要 4 秒就可以達到目標。
給定彗星列車每秒的加速度以及列車預期達到的速度,請你撰寫程式計算花費幾秒鐘列車便可達到指定速度。
**輸入說明**
輸入有兩個整數A(1≤ A ≤ 108)、S(1≤ S ≤ 109),A代表的是列車每秒的加速度,S代表的是列車預期達到的速度,兩個數字以一個空白隔開。
**範例輸入**
25 100
**輸出說明**
輸出一個整數,代表在最少幾秒後可達到預期的目標速度。
**範例輸出**
4
**解題思路**
設初速為v，末速為v'，加速度為a，加速所需時間為t，則由等加速度運動的公式可知v'=v+at ; 又本題中初速v=0，末速v'≥S，加速度a=A，可知S≤At。
我們可以利用while迴圈，設定當At<S時執行while迴圈，當At≥S時，輸出t值。
:::info
**注意事項**
本題為基本寫法，若是在講求速度的競賽遇到此題，可以使用更快的做法以減少測資(測試資料)時間。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int A,S; //宣告變數A，代表加速度;變數S，代表末速
cin >> A >> S;
int t=0; //宣告變數t，代表加速所需時間
while(A*t<S){ //由等加速度運動的公式可知v'=v+at，又v=0，可知S=At
t=t+1; //當At<S時，重複執行t+1，1並在每次執行while迴圈以前檢查At是否<S
}
cout << t; //當At≥S時，輸出t值
return 0; //返回值設為零
}
```
### [電梯 (Elevator)](https://zerojudge.tw/ShowProblem?problemid=g497)
**<題目>**
小明工作的大樓只有一部電梯,上下班期間常常因人潮而需排隊久候。早上他因為怕遲到,總是選擇走樓梯以節省時間。有一天小明在報導中發現:電梯上升一層樓耗電 3 度,下降一層耗電 2 度電,看到電梯如此龐大的耗電量,愛地球的小明決定以後都開始走樓梯。
小明心裡計算著,電梯每天從一樓開始運作,一天上上下下那麼多次,到底電梯一天的耗電量是多少,請你幫他寫一支程式計算。
**輸入說明**
輸入第一行為一個整數 N (2 ≤ N ≤ 5000) 代表一天中電梯的升降次數,第二行有 N 個正整數 xi (1 ≤ xi ≤ 1000, 1 ≤ i ≤ N) 表示電梯停留的樓層。
**範例輸入**
4
4 5 6 7
**輸出說明**
輸出一行表示電梯一天升降的耗電量。
**範例輸出**
18
**解題思路**
由題目可知電梯上升和下降一層樓的耗電度數不同,故必須先利用選擇結構判斷電梯是上樓還是下樓。當抵達樓層數字大於原先樓層時，電梯為上樓;當抵達樓層數字小於原先樓層時，電梯為下樓。
:::info
**注意事項**
本題使用大量陣列技巧，有關陣列的細節須多加留意，不然除錯會很花時間，像是陣列的首項是a[0]，不是a[1]。
:::
**程式碼**
```C++=
#include<iostream>
using namespace std;
int main(){
int E=0; //宣告變數E，代表電梯一天升降的耗電量
int N; //宣告變數N，代表電梯升降次數
cin >> N;
int a[N+1]; //宣告陣列a[]，代表樓層，同時宣告大小(電梯每升降一次就會有一個新的抵達樓層，再加上初始樓層(1樓)，樓層總數為n+1個)
for(int i=1;i<=N;i++){
a[0]=1;
cin >> a[i];
if(a[i]>a[i-1]) //當抵達樓層大於原先樓層時，電梯為上樓
E=E+3*(a[i]-a[i-1]);
else //當抵達樓層小於原先樓層時，電梯為下樓
E=E+2*(a[i-1]-a[i]);
}
cout << E << endl;
return 0; //返回值設為零
}
```
## 附錄
考量到這篇解題報告撰寫的時間有點長，成長的過程中一直在嘗試錯誤並從中修正，裡面可能會有前後語氣、程式寫法與習慣等不太連貫的缺點，基本上已經盡力檢查，如有疏漏還請多包涵，不吝指教。
另外因為這篇解題報告的時候希望能以淺顯易懂為優先，讓初學者也能順利學習，因此有些題目的解題手法可能稍嫌繁雜，若要將本篇的解題方法應用在程式語言競賽，如APCS、TOI等，測資可能會耗費較久時間，需特別留意。
感謝指導老師 方珮雯老師持續從旁協助!
2022.01.24 12:00留
Google Drive
Gist
Clipboard
Sign in with Wallet
