從零開始的演算法競賽入門教學
0%

發表於 更新於

vector

可隨時改變長度的陣列！

宣告

1
vector<int> v;

這時的 v 是空的，若要宣告大小為 n，可以：

1
2
vector<int> v;
v.resize(n);

或者：

1
vector<int> v(n);

也可以直接：

1
vector<int> v = {1, 2, 5};

填滿

1
vector<int> v(12,10);

宣告長度為 12 的 vector，並將值全部設為 10，後面參數沒有傳入的話，預設是 0。

1
2
vector<int> v(12);
fill(v.begin(), v.end(), 10);

使用 fill，並傳入 vector 的頭、尾、以及要填入的值也可以。

尾端加入元素

1
2
3
vector<int> v;
v.push_back(10);
v.emplace_back(45);

push_back 與 emplace_back 功能相同，但 emplace_back 速度稍快，push_back 比較好打

移除尾端

1
2
3
4
vector<int> v;
v.push_back(10);
v.emplace_back(45);
v.pop_back();

前端加入元素

無法

前端移除元素

無法

取得第 k 項

1
2
vector<int> v = {1, 2, 3};
cout << v[1] << '\n';

若索引值超過範圍，會噴 RE。

取得大小

1
2
vector<int> v = {1, 2, 3};
cout << v.size() << '\n';

是否為空

1
2
vector<int> v;
if(v.empty()) cout << "Empty!\n";

排序

1
2
3
4
int arr[] = {2, 1, 3, 8, -15};
vector<int> v = {2, 1, 3, 8, -15};
sort(v.begin(), v.end());
sort(arr, arr+5);

跟陣列相同，但開頭與結尾改為 begin 與 end。

反轉

1
2
vector<int> v = {2, 1, 3, 8, -15};
reverse(v.begin(), v.end());

意外的常用。

最小元素

1
2
3
vector<int> v = {2, 1, 3, 8, -15};
cout << *min_element(v.begin(), v.end()) << '\n';
cout << min_element(v.begin(), v.end()) - v.begin() << '\n';

若沒有*，回傳的是位址，可透過減掉 v.begin() 知道最小值所在的 index。

輸出所有 vector 裡的元素

1
2
3
vector<int> v = {1, 3, 2};
for(int i=0;i<v.size();i++) cout << v[i] << "\n";
for(int i:v) cout << i << "\n"; // C++ 11 以上

相信第一種寫法各位已經熟悉。

第二種寫法效果與第一種相同，但短很多，在 vector 等 STL 容器中非常好用，由於它是 C++ 11 以後才有的功能，若無法編譯可能要調整編譯器參數。

使用vector時機

隨時。

當你想在函式內傳入二維陣列時使用 vector，因為一般的二維陣列無法傳入

當你需要很多個一維陣列，但每個陣列長度不一，最大可能很大(ex： 1000000)但不會每個都這麼大，直接開二維陣列記憶體會爆炸。這時就是 vector 的出場時機。

例題(花了我的兩個小時QQ)

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int N, K;
vector<int> pal[1000005];

int main(){
    cin >> N >> K;
    for(int i=0,a,b;i<K;i++){
        cin >> a >> b;
        pal[a].push_back(b); // pal[a] 存放 a 的朋友。 將 b 放入 pal[a] 的最後方
        pal[b].push_back(a); 
    }
    for(int i=1;i<=N;i++) sort(pal[i].begin(), pal[i].end());
    for(int i=1;i<=N;i++){
        for(int j=0;j<(int)pal[i].size();j++){
            if(j != 0) cout << " ";
            cout << pal[i][j];
        }
        cout << '\n';
    }
}

練習

把之前 array 的練習題，用 vector 去寫寫看吧！

發表於

STL 是什麼？

wiki

STL 簡單來說，就是容器，裝資料的容器。

之前，我們學習過的容器只有array而已，array的缺點有幾個：

  1. 不能改變大小
  2. 不能從前面插入元素(從前面插等於將整個陣列往後，可以想像，這超慢)
  3. 不能自動排序好元素(也就是，插入一個數字後要重新排序很慢)

但STL裡的容器很特別，他有：

  • 可以改變陣列大小的 vector
  • 可以從前方插入或移除元素的 deque、queue
  • 可以邊插入邊移除，一邊很快的排序的 set、map，以及priority_queue
  • 可以對 bool 陣列進行位元運算，大幅加快速度的 bitset

因此，學習使用 STL，能讓你的實力更上一層樓！

宣告

STL 的語法大致相近。

1
2
3
vector<int> v;
vector<string> ss;
vector<vector<int>> v2;

其中，想特別講一下<>。這是 C++ 裡的 template 功能，要用什麼型態就放在裡面，非常自由。想用二維陣列的話，就在 vector 裡面再包一個 vector 吧！

迭代器(iterator)

STL 中，有一個新的概念：迭代器。

寫得很好的教學文

以往，如果要找到一個陣列 arr 開頭的位置，我們可以直接寫 arr，因為 arr 本身其實只是一個指標而已。要找到陣列第 N 項的位置，就是 arr+N，因為記憶體在陣列裡是連續的，所以可以直接加，但這些在 STL 中是做不到的。

假設你宣告了一個 vector 名為 v，那這個 v 在之後的程式中，不是代表記憶體，而是整個容器。

因此若需要得到 v 開頭的位置，要寫： v.begin()。v 結束的位置要寫 v.end()。在 set 與 map 中將會有迭代器的進階應用。

成員函式(member function)

1
2
3
4
5
6
7
struct my_struct{
    int a, b, c;
} s;

int main(){
    s.a = 10;
}

像是之前的 struct，假設我要得到 s 裡的 a 這個值，要寫 s.a。

STL 中也有類似的概念，但是，裡面包的是函式！比如剛剛的 .begin()，呼叫它，得到的回傳值就是這個容器的開始位置。

因為是函式，所以會有()的存在。有些函式需要傳入參數，就像正常使用函式那樣，在()中傳入就可以了。

常見的成員函式有：

  • .begin()：容器的開始位置
  • .end() ：容器的結束位置
  • .size() ：回傳容器大小，型態是 unsigned int，拿來跟 int 比較(.size() > 5)沒有問題，但編譯器會噴警告。拿來進行運算則存在 overflow 風險(<0的時候，unsigned int 就 overflow)。
  • .empty() ：回傳容器是否為空，型態是 bool，盡量多使用 .empty()，而非 .size() == 0。
  • (vector).push_back(x)：在後方加入元素 x
  • (vector).pop_back()：移除最後方元素
  • (set map).insert(x)：加入元素 x

總結

STL 超好用的！

從下一章開始，將會一個一個介紹常用的 STL，請不知道是否存在的長期讀者們稍等一下！

發表於

你現在的能力

如果我說，你現在所學會的東西，足夠你進入奧林匹亞選訓營，你相信嗎？

相信的人，要不是天真，就是愚蠢。過度的自信可是一點好處都沒有的。

那麼，你跟演算法競賽選手比起來，到底差在哪裡呢？

是學的東西不夠多嗎？比如說什麼定理、什麼帶人名的演算法、什麼現象不能解釋、什麼特例、什麼公式……等等，知道的還不夠多嗎？

即使這句話有一定的正確性，知道一定數量的演算法對想到題目的解答的確有幫助，但我仍想否定它。

高中時期大多數的題目，不需要任何艱深的演算法

來看看剛結束的 NPSC 初賽 吧 ~

這份題本中，B 題應該是現在的你可以解出的。(提示：一個數會被減幾次？會被加幾次？)，而 A、C、G，是可以不需要任何前面有掛人名的算法解出的。

高中程式競賽的目的，是在考驗自行設計方法解決問題的能力，而非知識量的多寡，請各位務必要記著，思考才是演算法競賽的重點。

未來的練習題，難度會逐漸提升，但希望各位若以本系列做為程式競賽入門時，不要輕易的跳過任何一題 3 星以下的題目。或許，在以前你學習的所有事情中，每一件都是可以直接掃過去，快速看完，也不會漏掉太多東西。但在這份教學這樣做的話，你的收穫將會少非常多。大約 60% 的知識，藏在例題裡。

你的迷惘

  • 要怎麼知道自己的學習成效到底好不好？
  • 我一天練習兩小時，真的有進步嗎？
  • (雖然有點早)我可以放棄課業，全力投入演算法競賽，拚特選/保送嗎？

針對前兩個問題，我建議可以報名 APCS，或是 TOI 線上練習賽與海選。他們共同的特點，是定期舉行、以及題目較為基本等，是個自我評量的好選擇。

加入很多初學者們的新手村(目前來看應該是 APCS 的討論社群)，看看裡面被討論的題目，看看自己能否成功解出，並試著將自己的想法具體為文字，與他人交流解法，也是個不錯的方式。

或許不少人聽過 Codeforces 這個平台，也可能打過幾場線上競賽。這是一個相當棒的程式解題平台，定時舉辦題目品質不錯的競賽，但我不建議初學者參加過多。

我認為學習是需要有基底的，不停參加競賽，比如一個想學習數學知識的人，整天只刷考古題，刷完了，不會還是不會，但看完題解後又感覺自己懂了，於是再刷下一份。這樣的學習方式並不健康，而且容易導致根基不穩。

有關 Codeforces，在後續的教學中，可能會有一個章節，來介紹這個平台，以及我使用它的方式。

第三個問題，我的回答是：當然可以，但我並不建議。

選擇放棄課業，是個人的事情，我並沒有理由阻攔，所以我會說可以。但我不建議的原因是，演算法競賽是活的、多變的。這樣一件需要創造力與想像力的事情，若是背上了升學的沉重壓力，那雙還沒有完全伸展開的翅膀，還能無所顧忌的在藍天中自由飛行嗎？

給可能頭腦只有 0 跟 1 的人的翻譯：壓力太大打不好競賽啦

一些心得

開始做這個 blog 也已經一個多月了，想來說說為什麼要有這個系列。

我的高中是台南一中，是目前濁水溪以南，資訊資源最豐富的學校之一。在高一時，我加入了資訊社，從而第一次有機會接觸到程式設計與演算法競賽，在此之前，我甚至不知道有 C++ 這個語言，也未曾寫過任何一行程式。在傳統的教育體制底下，相信著：你什麼都不用管，好好讀書，考上大學，然後人生勝利。

不是每個學習演算法競賽的人，都要當奧林匹亞金牌。作為接觸程式設計的起點、以及邏輯思考的練習，我認為演算法競賽，是相當有趣的，也應該被更多高中生認識。

然而，大多數人並沒有這種機會，特別是南部學生。若沒有台南一中資訊社的資源，我不可能踏入門檻這麼高的演算法競賽領域。網路上雖然有學習資源，但要不是已經是寫給稍有程度的人，要不就是散落在各個網站，沒有一個有辦法帶領像兩年前的我一樣的初學者，認識演算法競賽的趣味。看看全國賽、NPSC、與奧林匹亞的名單，便可略知一二。難道除了建中與竹科實中以外，所有人都是笨蛋嗎？當然不是。武陵高中的學生不可能是笨蛋，但在過去幾年，武陵高中幾乎沒有學生進入選訓營與 NPSC 決賽。

高中演算法競賽，目前缺少了一個引路人，將而我期許自己能成為他

在拿到銀牌後，透過保送制度，我在開學的一年前，就得到了台大資工教室裡的一個位置。這一年，要做什麼呢？除了持續閱讀、建構自己的世界觀之外，我希望能對世界有所貢獻，畢竟一路走來，我得到的太多、付出的卻太少。在演算法競賽之路上，接受了許多學長們的幫助，卻無以回報。而如今正好有著這一段自由時間，這時不做，更待何時？謹以此系列教學文，向演算法競賽的前輩們，表達我的感謝。

這系列的文章定位為入門導向，希望能帶領更多學生(特別是南部)走入演算法競賽。在學習的過程中，一定有失敗、有挫折，但唯有高溫，才能讓肉片，散發美味的香氣(沒錯現在12:30 我好餓)。期待在完成這系列的旅程中，與各位讀者攜手前行、共同成長。也請大家不吝提出意見，讓這份教學能真正貼近初學者的需求！

2020.11.23 emanlaicepsa 於台南一中資訊社部

發表於

前面提到了函式的概念，相信大家已經都對函式有了基本的了解，也在上一章中詳細介紹了 sort 這個函式的用法。今天，將要介紹的是一些常用的 C++ 的內建函式。適當的使用內建函式，不僅可以減少出 bug 的機會，更可以增加程式的可讀性，並且通常具有良好的時間複雜度。因此，在了解背後原理的前提下，請多多利用內建函式。

這裡的函式，在第一眼時，可能不會覺得它很好用，或是不知會在什麼情況下用到。可以等一陣子以後，再回來看看有哪些常常需要的功能，其實是有內建函式的喔！

min/max

用法：min(a,b) 回傳 a, b 中較小者。若要傳入三個以上的值，則須用大括號包住。

範例：

1
2
3
int a = 5, b = 10, c = 15;
cout << min(a, b) << '\n';
cout << max({a, b, c}) << '\n';

注意事項：比較的值型態需相同，即使 long long 跟 int 也不能比，可以在 int 前加上 (long long) 或乘上 1LL 以強制轉型。

1
2
3
4
5
6
long long a = 10;
int b = 15;

cout << max(a, b) << '\n'; // CE
cout << max(a, (long long)b) << '\n'; // ok
cout << max(a, 1LL*b) << '\n'; // ok

abs

用法：abs(x) 回傳 x 的絕對值，型態與 x 相同。

範例：

1
2
3
int a = 10;
double b = -1.546;
cout << abs(a) << abs(b) << '\n';

swap

用法：交換兩數。swap(a, b)後，a、b 互換，十分常用。

範例：

1
2
3
int a = 3, b = 4;
swap(a, b);
cout << a << b << '\n';

注意事項：兩個長度相同的 array 也可以交換，但複雜度是 $O(N)$。

1
2
3
4
5
6
int arr[] = {3,1,4,2};

int main(){
	sort(arr, arr+4);
	for(int i=0;i<4;i++) cout << arr[i] << '\n';
}

sqrt

用法：sqrt(x) 得到 x 開根號後的值。型態與 x 相同，複雜度 $O(logx)$。

範例：

1
2
3
int x = 5;
double y = 45.1321;
cout << sqrt(x) << " " << sqrt(y) << '\n';

pow

用法：pow(a,b)回傳 a 的 b 次方。複雜度根據底層結構不同，會有差異，暫時把它當成$O(1)$或$O(log)$等級的就好。但因為它是以浮點數進行運算，存在誤差，因此在整數世界不常使用。

範例：

1
2
3
4
int x = 3, y = 5;
double a = 1.256, b = 1234.456
cout << pow(x, y) << '\n';
cout << pow(a, b) << '\n';

注意事項：整數次方我們通常使用自己寫的快速冪技巧，不會使用pow函數。pow函數僅在小數次方使用。

__gcd

用法：__gcd(a, b)回傳 a 與 b 的最大公因數，複雜度 $O(log max(a, b))$。

範例：

1
2
int x = 3, y = 5;
cout << __gcd(x, y) << '\n';

__lg

用法：__lg(x) 回傳 x 以 2 為底的對數值取整，輸入必須是整數。複雜度$O(logx)$。

範例：

1
2
int x = 50;
cout << __lg(x) << '\n'; // 5

log

用法：log(x) 回傳 x 以 e 為底的對數值，是浮點數運算，複雜度$O(logx)$。

範例：

1
2
double x = 50.456;
cout << log(x) << '\n'; // 5

注意事項：
以 10 為底的 log 值可用 log10(x) 函數，其餘底則可使用對數基礎換底公式求得。

sort

用法：sort(a, b) 代表把從 a 位置(包含)到 b 位置(不含)之間的元素由小到大排序，詳細用法請見0-13。

範例：

1
2
3
4
5
6
int arr[] = {3,1,4,2};

int main(){
	sort(arr, arr+4);
	for(int i=0;i<4;i++) cout << arr[i] << '\n';
}

reverse

用法：reverse(a, b) 代表把從 a 位置(包含)到 b 位置(不含)之間的元素反轉，常用於字串。

範例：

1
2
3
4
5
6
int arr[] = {3,1,4,2};

int main(){
	reverse(arr+1, arr+4);
	for(int i=0;i<4;i++) cout << arr[i] << '\n'; // 3 2 4 1
}

min_element / max_element

用法：min_element(a, b) 回傳從 a 位置(包含)到 b 位置(不含)之間的最小值的指標，可用*加於其之前以得到值。

範例：

1
2
3
4
5
6
int arr[] = {3,4,1,2};

int main(){
	cout << *min_element(arr, arr+4) << '\n'; // 1
    cout << min_element(arr, arr+4) - arr << '\n'; // 2 (減掉arr得到index)
}

fill

用法：fill(a, b, c) 將 a 位置(包含)到 b 位置(不含)之間的所有元素全部變成 c。

範例：

1
2
3
4
5
6
int arr[] = {3,4,1,2};

int main(){
	fill(arr, arr+3, 321);
    for(int i=0;i<4;i++) cout << arr[i] << '\n'; // 321 321 321 2
}

lower_bound / upper_bound

用法：

lower_bound(a, b, c) 回傳在 a 位置(包含)到 b 位置(不含)之間第一個大於等於 c 的元素的位置。

upper_bound(a, b, c) 回傳在 a 位置(包含)到 b 位置(不含)之間第一個大於 c 的元素的位置。

需在由小到大排列好的陣列中才可使用。

若回傳的值是 b，代表沒有符合的元素。

同樣，可透過*取值。

範例：

1
2
3
4
5
6
7
8
9
int arr[] = {3,5,1,2};

int main(){
    sort(arr, arr+4);
	cout << *lower_bound(arr, arr+4, 3) << '\n'; // 3
    cout << *lower_bound(arr, arr+4, 2) << '\n'; // 3
    cout << *upper_bound(arr, arr+4, 3) << '\n'; // 5
    cout << *lower_bound(arr, arr+4, 6) << '\n'; // 超出範圍 值不定 
}

練習

TOJ 55

TOJ 47

##

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// TOJ 55
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
int arr[1000005];

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> arr[i];
	sort(arr+1, arr+1+n);
	cin >> m;
	for(int i=1,x;i<=m;i++){
		cin >> x;
		cout << upper_bound(arr+1, arr+1+n, x) - lower_bound(arr+1, arr+1+n, x) << '\n';
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// TOJ 47
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
int arr[1000005];

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> arr[i];
	sort(arr+1, arr+1+n);
	cin >> m;
	for(int i=1,x;i<=m;i++){
		cin >> x;
		int *big = lower_bound(arr+1, arr+1+n, x); // * 表示這是一個儲存位址的變數
		int *small = big-1;
		if(*big == x) cout << x << '\n'; // 對位址變數使用 * 代表取值
		else{
			if(small == arr) cout << "no ";
			else cout << *small << " ";
			if(big == arr+1+n) cout << "no\n";
			else cout << *big << '\n';
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// TOJ 47 no 指標
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
int arr[1000005];

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> arr[i];
	sort(arr+1, arr+1+n);
	cin >> m;
	for(int i=1,x;i<=m;i++){
		cin >> x;
		if(*lower_bound(arr+1, arr+1+n, x) == x) cout << x << '\n';
		else{
			if(x < arr[1]) cout << "no ";
			else cout << *(lower_bound(arr+1, arr+1+n, x)-1) << " ";
			if(x > arr[n]) cout << "no\n";
			else cout << *(lower_bound(arr+1, arr+1+n, x)) << '\n';
		}
	}
}

發表於 更新於

排序

其實這有點算是演算法的範圍，不過因為我認為排序對於基礎演算法、時間複雜度、分治、二分搜、常用函式等等主題來說，都是相當好的範例，因此，決定將其置於此。

這篇中，將會帶大家認識時間複雜度的概念、以泡沫排序介紹演算法、使用預設的sort函式及自定義比較函式。進階的排序方法與逆序數對等主題，將會於下一本書中介紹。

排序是什麼

把一堆東西，按照某個特定的規則排好。例如：由小排到大或由大排到小等等。

來看一下這個題目：

ZeroJudge a104

1
2
3
4
5
有多筆測資以EOF為結束

第一行有一個正整數n(1<=n<=1000)，代表有幾個數字要請你幫忙排

第二行有n個可以用int儲存的正整數

假設輸入是：

1
1 3 2 4 5

你當然可以說，那我把2、3交換位置，就排好了。

但是今天，程式要做的，是對於所有在限制範圍內的輸入，都要能夠在限制時間內，輸出正確解答。也就是說，要有一個通解程式！

而這，就是演算法的基本概念，演算法，就是解決問題的方法。

直接將輸入原封不動的輸出，對於特定測試資料(例如：本來就已經排好)的輸出答案會是正確的，但它並不會對於所有輸入都能夠產生正確解答。這也是為什麼你的程式常常能夠通過範例測試，但卻在 Online Judge 上一直 WA 的原因。因為你的程式通過範例只是運氣好，它沒有辦法對任意輸入都輸出正確解。

思考一下吧

先想個三分鐘，想想看如何運用簡單的陣列、迴圈，寫出針對上題的排序演算法吧！

範例程式碼會在最下方提供。這裡，我想提供兩種想法。

1. 選擇排序法(Selection Sort)

每次找到陣列中最小的值，將其放入新的陣列後，從原本的陣列移除，若原陣列長度為 N，重複執行 N 次後，當所有的元素都從原本的陣列移除後，我們就排序好了！

但其實，我們不用開新的陣列，只需要在第 i 次執行時，將找到的那個值，換到第 i 個位置。在下一次尋找時，從 i+1 位置開始尋找就好，可以省下約兩倍的時間與空間。

選擇排序法圖解

2. 泡沫排序法

不停的掃過整條陣列，當發現左邊的數字比右邊的還要大的時候，就交換兩數，直到再也找不到這樣的數字為止。

但實作上有個優化，每次從左往右掃，並交換需要交換的數字。先看位置 1 是否比位置 2 大，如果是的話就交換，再看 2 跟 3，3 跟 4，……最後看 N-1 跟 N。

可以發現，在從左往右掃完一次陣列時，最大的數字，一定可以成功被換到最右邊。所以第二次時，就只需考慮 1 ~ N-1 的陣列了。從左往右掃完第二次陣列時，第二大的數字，就會成功被換到 N-1 的位置。

就這樣執行 N (其實是N-1) 次後，陣列就順利排序好了！

泡沫排序法圖解

複雜度

在 AC 了剛剛那一題後(請先 AC 上面那一題再繼續看下去)，拿原本的 code 傳這一題看看：

ZeroJudge a223

奇怪，怎麼 TLE 了？

這應該是你遇到的第 2、3 個 TLE，前面的章節的練習裡，會出現 TLE 的原因是什麼呢？

啊！對了！是輸入太慢！

於是，你加上輸入優化，但還是沒過。為什麼呢？

這裡，來稍微介紹一下複雜度的概念。複雜度，就是你的程式在最差情況下，會執行多少次基本操作。

什麼是基本操作呢？

1
2
3
4
5
a++;
b--;
c*=5;
a+=9*45/7;
a[1] = a[0];

這些只需要一步就能完成的動作，我們叫它基本操作。其實，非基本操作好像都還沒出現在這本講義~

電腦一秒鐘能執行的基本動作數量，大約是 $10^8$ 左右。這下，明白為什麼題目要設置時間限制了嗎？

演算法不僅要正確，速度也是很重要的！

現在，我們就試著分析一下選擇排序法的複雜度。

選擇排序法的主要概念，便是重複 N 次找最大值的過程。在每一次的過程中，程式需要去遍歷整個陣列。那麼，基本操作在哪裡？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// ZJ a104 selection sort
#include<bits/stdc++.h>
using namespace std;

int n, arr[1005];

int main(){
	while(cin >> n){
		for(int i=1;i<=n;i++) cin >> arr[i];
		for(int i=1;i<=n;i++){
			int mn = arr[i], id = i;
			for(int j=i+1;j<=n;j++){
				if(arr[j] < mn) id = j, mn = arr[j];
			}
			swap(arr[i], arr[id]);
		}
		for(int i=1;i<=n;i++){
			cout << arr[i];
			if(i < n) cout<<" ";
			else cout<<'\n';
		}
	}
}

j++，arr[j] < mn，swap(arr[i], arr[id])，這些全部都是基本操作。其中，前兩個基本操作，在第 i 回合時，都會執行到 N-i 次。因此，我們知道，j++ 總共被執行的數量，應該是 1 + 2 + 3 + 4…… + N-1 = (N) * (N-1) / 2 次。

在 N = 1000，也就是上題的限制時，總共約需要執行 500000 次的 j++，但電腦一秒可以跑 $10^8$ 次，因此能夠順利通過前一題。

但在本題的最大範圍： N = 1000000 下，總共約需要執行 $5 \times 10^{11}$ 次 j++，因此，光是 j++ 這個動作，電腦就需要花上 5000 秒，想當然，這就是 TLE 的原因。

$O(N)$? $O(N^2)$?

但要是我們將所有基本操作都列入計算，例如：i++ 執行 N 次，if(arr[j] > mx)執行 N * (N-1) / 2 次，可能光算出來就花很久了，而且，我們也不需要那麼精密的計算，估個大概就好。

因此，我們捨棄所有跟題目限制沒有關係的常數，以最高次項為代表。

假設算出來程式會執行 $2 \times N^2 + 60 \times N + 7895$ 次，我們就直接捨棄 $N^2$ 以外的東西，畢竟，在 N 高達數千、甚至數萬的情況下，$60 \times N$ 再怎麼大，都遠小於 $N^2$，因此在估算上，直接捨去就好。

所以，要是一個演算法的最高次項是 $N^2$，我們就會說： 這是一個 $O(N^2)$ 的演算法

$O(N)$這個符號，其實是有嚴格的定義的，有興趣的可以點這裡，不過這邊就容我略過了。

sort函式

知道時間複雜度的概念以後，應該可以知道TLE的原因了吧！那，要如何通過這題呢？顯然我們需要一個比 $O(N^2)$ 還要快的排序演算法。

排序演算法在極限情況下，可以在 $O(NlogN)$ 的時間內完成排序工作。常見的 $O(NlogN)$ 排序有 quick sort 以及 merge sort 等等。但由於其概念較難懂，將放至下一本說明，有興趣的話可以點進連結。

這裡要介紹的，是 C++ 內建的函式：sort。

1
sort(arr+1, arr+1+N);

這樣，就sort好了。更棒的是，它的時間複雜度是 $O(NlogN)$。因此，就順利的通過了這題。

sort函式中，需要傳入兩個參數：開始與結束位置。而由於採用左閉右開(左界包含，右界不含)的設計，開始位置是有放東西的第一格，結束位置是最後一個有放東西的位置的下一格。

假設現在我有長度為 4 的陣列 arr，並從 1 開始放了 3 個數字在 arr[1], arr[2], arr[3] 的位置，那在 sort 時，就寫：

1
2
sort(arr+1, arr+4);
//    開始   結束

假設我從 0 開始，放在 arr[0], arr[1], arr[2]，那在 sort 時，就寫：

1
sort(arr, arr+3)

那如果我從 1 開始放，放 N 個，當然就是這樣寫啦：

1
sort(arr+1, arr+1+N);

這行執行完後，你就會神奇的發現，陣列排序好了！

自定義比較函式

sort 預設是由小排到大。那如果我現在要由大排到小，要怎麼做呢？

sort 隱藏的第三個參數，是比較函式。若在排序後的陣列中 A 必定要置於 B 之前，那麼此函式在接收到 A, B 時，必須回傳 true。否則回傳 false。

範例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

int n, arr[1000005];

bool cmp(int a,int b){
    return a > b;
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> arr[i];
    sort(arr+1, arr+1+n, cmp);
    for(int i=1;i<=n;i++) cout << arr[i] << " ";
}

注意的一點是，回傳 true 的條件是，A 必定要置於 B 之前。因此若 A == B，是不可以回傳 true 的。回傳 true 的話，由於不管傳入 (A, B) 或是 (B, A) 都回傳 true，程式會停不下來，通常會導致 Runtime Error 的結果。

不單純的 sort

來看看這題：

ZeroJudge a915

(請自動忽略簡體字)

1
給你 n 個二維平面上的點，要求你把他們按照以x軸坐標為第一關鍵字，y軸坐標為第二關鍵字的方式從小到大來進行排序。

也就是說，先比 x，x 一樣的話再比 y。

二維平面上的點是由兩個整數組成，要怎麼將兩個整數合起來視為一個點？如果將 x 跟 y 分開存，sort 後不是會跑掉嗎？

所以，我們使用上一節教的 struct。

1
2
3
4
5
struct Point{
    int x, y;
};

Point arr[1005];

那要怎麼 sort 呢？要 sort 的條件是，必須要有 < 這個運算子，這樣程式才知道怎麼排嘛。還記得上一節教的定義運算子嗎？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Point{
    int x, y;
    bool operator<(Point b){
        if(x != b.x) return x < b.x;
        else return y < b.y;
    }
};

Point arr[1005];
int n;

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> arr[i].x >> arr[i].y;
    }
    sort(arr+1, arr+1+n);
}

這樣，就可以使用 sort 了。

另一種方法

如果將 x 跟 y 分開存，能 sort 嗎？

當然，只是我們不能對存他們的陣列 sort，但是我們可以另外開一個裡面是 1~N 的陣列，代表他們的位置。接著，透過自定義比較函式，比較 a 與 b 時，我們就比較 x[a] 跟 x[b] 誰比較小，如果一樣的話再比 y[a] 跟 y[b]，這樣 sort 出來的陣列，就是他們由小排到大的順序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int x[1005], y[1005], idx[1005], n;

bool cmp(int a, int b){
    if(x[a] != x[b]) return x[a] < x[b];
    else return y[a] < y[b];
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> x[i] >> y[i];
        idx[i] = i;
    }
    sort(idx+1, idx+1+n, cmp);
    for(int i=1;i<=n;i++){
        cout << x[idx[i]] << " " << y[idx[i]] << '\n';
    }
}

內建這麼好用，全部都用內建的 sort 就好啦

恩，你先寫寫看例題吧。

例題

ZeroJudge a104

ZeroJudge a233

ZeroJudge a915

★★ TOJ 15

★★★ TOJ 539

★★★★ ZeroJudge 471

Hint: 找到 A 必定要置於 B 之前的條件

★★★★★ TOJ 11

Hint: 如果我只要問：最小的數字在這過程中，會需要交換幾次呢？

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// ZJ a104 selection sort
#include<bits/stdc++.h>
using namespace std;

int n, arr[1005];

int main(){
	while(cin >> n){
		for(int i=1;i<=n;i++) cin >> arr[i];
		for(int i=1;i<=n;i++){
			int mn = arr[i], id = i;
			for(int j=i+1;j<=n;j++){
				if(arr[j] < mn) id = j, mn = arr[j];
			}
			swap(arr[i], arr[id]);
		}
		for(int i=1;i<=n;i++){
			cout << arr[i];
			if(i < n) cout<<" ";
			else cout<<'\n';
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// ZJ a104 bubble sort

#include<bits/stdc++.h>
using namespace std;

int n, arr[1005];

int main(){
	while(cin >> n){
		for(int i=1;i<=n;i++) cin >> arr[i];
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n-i;j++){
				if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
			}
		}
		for(int i=1;i<=n;i++){
			cout << arr[i];
			if(i < n) cout<<" ";
			else cout<<'\n';
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// ZJ a233
#include<bits/stdc++.h>
using namespace std;

int n, arr[1000005];

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> arr[i];
	sort(arr+1, arr+1+n);
	for(int i=1;i<=n;i++){
		cout << arr[i];
		if(i < n) cout << " ";
		else cout << '\n';
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// ZJ a915 struct
#include<bits/stdc++.h>
using namespace std;
struct Point{
    int x, y;
    bool operator<(Point b){
        if(x != b.x) return x < b.x;
        else return y < b.y;
    }
};

Point arr[1005];
int n;

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> arr[i].x >> arr[i].y;
    }
    sort(arr+1, arr+1+n);
    for(int i=1;i<=n;i++){
        cout << arr[i].x << " " << arr[i].y << '\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ZJ a915 no struct
#include<bits/stdc++.h>
using namespace std;
int x[1005], y[1005], idx[1005], n;

bool cmp(int a, int b){
    if(x[a] != x[b]) return x[a] < x[b];
    else return y[a] < y[b];
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> x[i] >> y[i];
        idx[i] = i;
    }
    sort(idx+1, idx+1+n, cmp);
    for(int i=1;i<=n;i++){
        cout << x[idx[i]] << " " << y[idx[i]] << '\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//TOJ 15
#include<bits/stdc++.h>
using namespace std;

struct cat{
	int rk, age;
	string name;
	bool operator<(cat b){
		if(rk != b.rk) return rk < b.rk;
		else if(age != b.age){
			if(rk == 5) return age < b.age;
			else return age > b.age;
		}
		else return name < b.name;
	}
};

cat arr[10005];
int n, m;
string ord = " enkwamdl"; // first char of their work

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	while(cin >> n >> m){
		for(int i=1,age;i<=n;i++){
			string name, work;
			cin >> name >> work >> age;
			for(int j=1;j<=8;j++){
				if(work[0] == ord[j]){
					arr[i] = {j, age, name};
				}
			}
		}
		sort(arr+1, arr+1+n);
		if(n < m) m = n;
		for(int i=1;i<=m;i++){
			cout << arr[i].name << '\n';
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// TOJ 539
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n, k, arr[200005][2], dif[200005];

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    ll tot = 0;
    for(int i=1;i<=n;i++) cin >> arr[i][0];
    for(int i=1;i<=n;i++) cin >> arr[i][1], tot += arr[i][1];
    for(int i=1;i<=n;i++) dif[i] = arr[i][1] - arr[i][0];
    sort(dif+1, dif+1+n);
    for(int i=1;i<=n;i++){
        if(tot - dif[i] < k){
            cout << i-1 << '\n';
            return 0;
        }
        tot -= dif[i];
    }
    cout << n << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// ZJ c471
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n, w[100005], f[100005], id[100005];

bool cmp(int a,int b){
	return f[a] * w[b] > f[b] * w[a]; 
    // 如果 f[a] * w[b] > f[b] * w[a]，那麼 a 一定會排在 b 的上面，否則交換 a, b 後，答案會更小
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> w[i];
	for(int i=1;i<=n;i++) cin >> f[i], id[i] = i;
	sort(id+1, id+1+n, cmp);
	ll top = 0, ans = 0;
	for(int i=1;i<=n;i++){
		ans += top * f[id[i]];
		top += w[id[i]];
	}
	cout << ans << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// TOJ 11 關鍵字：逆序數對/ counting inversion
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int arr[2000005], tmp[2000005], n;
ll ans;

void merge_sort(int l, int r){
    if(l == r) return;
    int m = (l+r)/2;
    merge_sort(l, m);
    merge_sort(m+1, r);
    int lid = l, rid = m+1, id = l;
    while(lid <= m && rid <= r){
        if(arr[lid] <= arr[rid]) tmp[id++] = arr[lid++]; // tmp[id] = arr[lid], id++, lid++;
        else tmp[id++] = arr[rid++], ans += m+1-lid;
    }
    while(lid <= m) tmp[id++] = arr[lid++];// tmp[id] = arr[lid], id++, lid++;
    while(rid <= r) tmp[id++] = arr[rid++];
    for(int i=l;i<=r;i++) arr[i] = tmp[i];
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    while(cin>>n){
        ans = 0;
        for(int i=1;i<=n;i++) cin >> arr[i];
        merge_sort(1, n);
        cout << ans << '\n';
    }
}

發表於

余柏序學長的教學文

作用範圍

變數是會失效的！如果有認真寫題目的人，應該會發現這一點。在之前的迴圈、陣列等也有提過區域變數與全域變數。不要將陣列宣告在 main 函式內，而是宣告於全域的其中一個理由就是：如果你的程式裡面需要用到函式，那這個寫在 main 函數外的函式就沒有辦法使用這個陣列裡的資訊了！那麼，現在就來看看，變數的作用範圍，大概是怎麼一回事吧！

最懶的判斷法

一個變數的作用範圍，自其宣告開始，到其所屬的右大括號為止

比如：

1
2
3
4
5
6
7
int main(){
    int a;
    for(int b=0;b<n;b++){
        int c = 5;
        cout << c << '\n';
    }
}

這個 a 的作用範圍，就是 main 函式結尾，而 b 與 c 的範圍，則到 for 迴圈結束為止。

有大括號的東西，例如 if、for、while、函式…… 都適用這個規則。並且不會因為省略大括號而有改變，也就是說，即使這樣：

1
if(9 > 5) int b = 6;

因為 if 只有一行而省略大括號，但變數 b 的作用範圍仍然只在這個 if 中。

1
2
if(9 > 5) int b = 6;
cout << b << '\n';

這樣是會 CE 的，因為在 cout 那行，這個 b 已經失效，是找不到 b 的。

更多範例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int a = 1;

void f(){
    int g = 7;
}

int main(){
    int b = 2;
    if(a > b){
        int c = 3;
    }
    for(int i=0;i<a;i++){
        int d = 4;
    }
    while(a--){
        int e = 5;
    }
    f();
}

以上各變數的作用範圍，分別是哪裡呢？

答案：

  • a ： 3 ~ end
  • b ： 10 ~ 21
  • c ： 12 ~ 13
  • d ： 15 ~ 16
  • e ： 18 ~ 19
  • f 是函式名稱，不是變數
  • g ： 6 ~ 7

這樣，對變數的作用範圍，有大致的了解了嗎？

接下來，我們就來看看，這樣會造成什麼問題。

重複宣告

一般來說，我們無法宣告具有相同名稱之變數，例如：

1
2
int a = 5;
int a = 3;

這是一段會 CE 的程式碼。

但若作用範圍不同，則可以順利編譯執行。這會導致程式的執行結果與心中所想的不同，而且不太容易 debug。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int a = 1;

void print(){
    cout << a << '\n'; // 1
}

int main(){
    cout << a << '\n'; // 1
    int a = 2;
    cout << a << '\n'; // 2
    for(int i=0;i<3;i++){
        int a = 3;
        cout << a << '\n'; // 3
    }
    cout << a << '\n'; // 2
    print(); // go out of main function
}

輸出：

1
2
3
4
5
6
7
1
2
3
3
3
2
1

這段程式碼當中，總共出現了三種不同的 a，但因為他們作用範圍不同，因此不會有編譯錯誤。

大範圍的變數與小範圍的同時出現時，會優先以小的為主。因此在 11 行的 a 宣告後，雖然第 3 行的 a 仍在作用範圍，但在 11 行的 a 於 main 函式結尾失效前，都會暫時被覆蓋。在此期間，只要程式碼有提到 a，編譯器一律不會當成第 3 行的 a。

應盡量避免這樣的狀況發生，可於編譯指令中加上 -Wshadow 以自動偵測是否有變數同名。但仍建議平常在練習時養成變數命名的好習慣，勿隨意命名變數。

若只是用來代表目前迴圈跑到哪裡的 i, j, k 變數等，我會於迴圈的一開始宣告。這樣，兩個不同迴圈中的 i 才不會互相形成干擾。

練習

檢查自己過去的程式碼，有沒有重複命名的現象？是否曾因為重複命名而產生過 bug ？

發表於

被遞迴摧殘後的大家還好嗎？放心，最難的一章過了，之後的會輕鬆許多。

這是在 11/11 更新的第 11 小節！

struct 是什麼？

這篇寫得太好，偷懶一下XD。這篇由於使用的是 C 語言，因此寫法略有不同，但概念是一樣的。

總之，struct 的出現，讓我們可以自己定義一個新的變數型態，而這個型態能夠把很多不同的變數包在一起，甚至可以定義自己的函式與運算子。

基礎語法

語法是這樣的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

struct my_struct{
    int x;
    double y;
    string s;
} c;//要有分號

int main(){
    my_struct a;
    a.x = 45;
    a.y = 55.232;
    a.s = "This is a string";

    my_struct b{1,1.23,"Another way of declaration."}; // 另一種宣告方法

    cout<<a.x<<" "<<a.y<<" "<<a.s<<'\n';
    cout<<b.x<<" "<<b.y<<" "<<b.s<<'\n';
    c.x = 10;
    cout<<c.x<<'\n';
}

輸出：

1
2
45 55.232 This is a string
1 1.23 Another way of declaration.

宣告部分，可以像一般宣告變數那樣，直接 my_struct a。也可以在後方加上大括號{}以傳入值。特別的是，可以直接在 struct 的最後宣告。

使用上，以 . 來取得元素，a.x 代表的就是 a 的 x 項，可參考上方 code。

自定義比較

要如何比較兩個 struct 的大小呢？我們需要告訴程式”怎麼樣是比較小的”。語法稍微有點複雜，也不常用到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;

struct my_struct{
    int x;
    double y;
    string s;
    bool operator <(my_struct b){
        return x < b.x; // 定義小於為 x 較另一個人的 x 小
    }
};//要有分號

int main(){
    my_struct a;
    a.x = 45;
    a.y = 55.232;
    a.s = "This is a string";

    my_struct b{221,1.23,"Another way of declaration."}; // 另一種宣告方法

    if(a < b){
        cout << "A is smaller than B\n";
    }
    else{
        cout << "A is not smaller than B\n";
    }
}

輸出：

1
A is smaller than B

自定義加減

當然，我也可以重定義加減。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;

struct my_struct{
    int x;
    double y;
    string s;
    bool operator <(my_struct b){
        return x < b.x; // 定義小於為 x 較另一個人的 x 小
    }
    my_struct operator +(my_struct b){
        return {x+b.x, y+b.y, s+b.s};
    }
};//要有分號

int main(){
    my_struct a;
    a.x = 45;
    a.y = 55.232;
    a.s = "This is a string";

    my_struct b{221,1.23,"Another way of declaration."}; // 另一種宣告方法

    a = a + b; // 不可寫 a += b 因為你只定義 + 沒有定義 +=
    cout<<a.x<<" "<<a.y<<" "<<a.s<<'\n';
}

輸出：

1
2
3
266
56.462
This is a string, Another way of declaration.

建構子

告訴程式在指定其中幾個值的情況下，struct 中的每個變數是多少，語法有點像函式：my_struct(……){}。

提醒一下，若未自己寫建構子，系統會預設每一個值都是該型態放在全域變數的預設值，例如 int 是 0，string 是 “” 等等。

但若自己寫了任何一個，則不會預設，也就是說，如果你寫了一個需要傳入預設值的建構子，之後在沒有值的情況下單獨宣告：my_struct a，這時，a 裡面所有變數的值將會是未知數，而這是很恐怖的。因此，如果要寫建構子，記得一定要多寫在不傳入任何參數下的預設。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;

struct my_struct{
    int x;
    double y;
    string s;
	my_struct(){ // 多寫的預設建構子
		x = 45;
		y = 1.23;
		s = "sdaf";
	}
	my_struct(int a,double b,string c){
		x = a;
		y = b;
		c = "safasf";
	}
};//要有分號

int main(){
    my_struct a;
	my_struct b(45,45.45455,"sdfsd");
    cout<<a.x<<" \n"<<a.y<<" \n"<<a.s<<'\n';
    cout<<b.x<<" \n"<<b.y<<" \n"<<b.s<<'\n';
}

輸出：

1
2
45 1.23 sdaf
12 1.2536 sdfsd

struct 的使用時機

其實大概可以感覺的出來，struct不會太常用到。但有時，總是會遇到一些時候，我們需要同時儲存超過一個變數，例如：要儲存三維空間中的點(x,y,z)，我們可以這樣寫：

1
2
3
struct Point{
    int x, y, z;
};

這樣的話，我就成功將三個整數包在一起，代表空間中的一個點了！

練習

老樣子，因為很多使用struct的時機是在排序時，因此併入下一章節。

發表於

遞迴是什麼

狹義的遞迴，指的是一個函式，在運行過程中，直接或間接的去呼叫了自己這個函式。沒錯，這是可以的，且是許多演算法實作過程的一部分。

但其實，遞迴不僅僅是語法，而是一種概念。將一個問題，歸約到一個或多個規模較小的子問題，不管它的實作方式是使用遞迴還是迴圈，我認為都可以算是遞迴的一部份。遞迴的這個概念，在演算法競賽裡非常重要。未來在第二、三章節，會一次又一次的，以不同模樣出現，DP根本就是遞迴，排序、資料結構在實作的過程中，亦有許多遞迴的影子。

但現在，我們就來看看狹義遞迴的語法吧

語法

1
2
3
4
void func(){
    //...
    func();
}

基本上，概念是這樣的。當然，如果沒有自己設定，遞迴是不可能停下來的。由於非常容易掛掉以及 debug 較為困難，因此遞迴成為了不少人的惡夢。

在撰寫遞迴程式時，務必再三確認是否有設定中止條件，以及其是否正確，不然要是停不下來的話就糟糕了。

範例

今天，我要印出從 1 ~ n 裡的每一個整數。當然，我可以使用迴圈實作，而且迴圈也是更好的作法。但為了使讀者更明白遞迴的過程，這裡使用遞迴撰寫。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x){
    cout << x << '\n';
    if(x == n) return; // 中止條件 相當重要
    print(x + 1);
}

int main(){
    print(1);
}

問題相對直觀，得到參數 x 後，輸出它，並且以 x + 1 作為參數呼叫下一次遞迴，直到 x 等於 5 時才停下。輸出為：

1
2
3
4
5
1
2
3
4
5

但如果今天程式是這樣呢？

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x){
    if(x < n) print(x + 1);
    cout << x << '\n';
}

int main(){
    print(1);
}

這時候，變成我先呼叫 print(x + 1)後，再輸出 x，這樣的輸出會是什麼呢？稍微有點難想，但若從 5 反推回來，print(5)只輸出 5，print(4) 是 print(5) 後輸出 4，print(3) 是 print(4) 後輸出 3，可以發現，輸出應該就是：

1
2
3
4
5
5
4
3
2
1

困難的來了，如果我的程式是這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x){
    if(x < n){
        print(x + 1);
        print(x + 2);
    }
    cout << x << '\n';
}

int main(){
    print(1);
}

這就不是個簡單的遞迴函式了，事實上，我也無法在不借助紙筆的方式下，得知它的輸出。呼叫 print(1) 時，我先呼叫了 print(2)，這時 print(2) 會一直遞迴下去，直到 print(2) 完全結束以後，再呼叫 print(3)。等到 print(3) 結束後，最後輸出 1。

最後的輸出長這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5
6
4
5
3
5
6
4
2
5
6
4
5
3
1

很難理解吧！我們嘗試透過一些輔助的文字去幫助理解，紀錄一個值d，代表我現在處於遞迴中的第d層，輸出該數前，我先輸出d個空格，以此區分不同層的輸出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x, int d){
    if(x < n){
        print(x + 1, d + 1);
        print(x + 2, d + 1);
    }
    for(int i=0;i<d;i++) cout<<" ";
    cout << x << '\n';
}

int main(){
    print(1, 0);
}

輸出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    5
    6
   4
   5
  3
   5
   6
  4
 2
   5
   6
  4
  5
 3
1

恩…還是有點難懂，不然我們在呼叫print(x+1)跟print(x+2)時，都輸出一句話好了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n = 5;

void print(int x, int d){
    if(x < n){
        for(int i=0;i<d;i++) cout<<" ";
        cout<<"x = " << x <<", print(x+1):\n";
        print(x + 1, d + 1);
        for(int i=0;i<d;i++) cout<<" ";
        cout<<"x = " << x <<", print(x+2):\n";
        print(x + 2, d + 1);
    }
    for(int i=0;i<d;i++) cout<<" ";
    cout << x << '\n';
}

int main(){
    print(1, 0);
}

輸出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
x = 1, print(x+1): // a
 x = 2, print(x+1): // b
  x = 3, print(x+1): // c
   x = 4, print(x+1): // d
    5
   x = 4, print(x+2): // d
    6
   4
  x = 3, print(x+2): // c
   5
  3
 x = 2, print(x+2): // b
  x = 4, print(x+1):
   5
  x = 4, print(x+2):
   6
  4
 2
x = 1, print(x+2): // a
 x = 3, print(x+1):
  x = 4, print(x+1):
   5
  x = 4, print(x+2):
   6
  4
 x = 3, print(x+2):
  5
 3
1

其中，// 後方的字相同者，表示其分別是同一層中的 print(x+1) 與 print(x+2) 兩個函式，不是程式實際輸出。

遞迴的思考相當抽象，建議搭配影片理解。

但也因為這樣，遞迴可以用來解一般正常思考下想不到或難解決的問題，下方練習題皆為遞迴經典題，具有相當的難度，但理解後，會發現，用遞迴寫，原來這麼簡潔、乾淨、漂亮！

遞迴是…

我覺得，解決遞迴問題的過程，就像是人生。未來過於遙遠，無法想像、無法預測，我們唯一能夠改變的，只有每個當下的自己。不需要去猜測未來到底會變得如何，我們所能做的一切，只是把握此時此刻，努力面對並解決今天遇到的問題。並且相信：明天一定會更好的！

唯一不同的是，人生會在執行到一半時，突然發生大量意外，但程式基本上不會，除非你寫爛了。

練習題

河內塔問題(易 建議完全了解此題)：
ZeroJudge a227

合成函數：(中偏難) : tcirc d002

約瑟夫問題 定時K彈(難 有興趣可寫)：ZeroJudge c296

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// ZeroJudge a227
#include<bits/stdc++.h>
using namespace std;

int n;

void hanoi(int n, char from, char to, char mid){
	if(n == 1){ // 遞迴停止條件即為只需移一個盤子
		cout<< "Move ring " << n << " from " << from << " to " << to << '\n';
		return;
	}
	hanoi(n-1, from, mid, to); // 先想辦法把前面 n-1 個搬到中間那根柱子
	cout<< "Move ring " << n << " from " << from << " to " << to << '\n'; 
	hanoi(n-1, mid, to, from); // 把前面 n-1 個柱子從中間搬到目標上
}

int main(){
	while(cin>>n){
		hanoi(n,'A','C','B');
		cout<<'\n';
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 合成函數
#include<bits/stdc++.h>
#define ll long long // 將程式裡的 ll 視為 long long 的意思
using namespace std;

ll n;
string s;

ll str_to_int(string s){ // 將字串轉為整數
	ll ans = 0, st = 0;
	bool neg = 0;
	if(s[st] == '-') neg = 1, st++;
	for(int i=st;i<s.size();i++) ans = ans * 10 + s[i] - '0';
	if(neg) ans = -ans;
	return ans;
}

ll solve(){
	cin >> s; // 讀入下一個
	if(s == "f"){
		ll x = solve(); // f 後面 有 1 個參數
		return x * 2 - 3;
	}
	else if(s == "g"){
		ll x = solve(); // g 後面 有 2 個參數
		ll y = solve();
		return x * 2 + y - 7;
	}
	else if(s == "h"){
		ll x = solve(); // h 後面 有 3 個參數
		ll y = solve();
		ll z = solve();
		return 3 * x - 2 * y + z;
	}
	else return str_to_int(s); // 是數字的話 就直接回傳
}

int main(){
	cout<<solve()<<'\n';
}

定時K彈詳解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 定時K彈 最短的最難 https://www.facebook.com/nthuioncamp/posts/438261166736061
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N, M, K;

int solve(int N, int M, int K){
	if(K == 0) return 0;
	return (solve(N-1, M, K-1) + M) % N;
}

int main(){
	cin >> N >> M >> K;
	cout << solve(N, M, K) + 1 << '\n';
}

發表於 更新於

函式是什麼

函式就像一台大機器，接受輸入(有時也可以沒有輸入)，回傳輸出給使用者。發現了嗎？其實到目前為止，你寫的每一個程式，都是函式，因為它接收了一些東西，並輸出結果。

適當的使用函式，可以使程式碼更為簡潔，可讀性更高。不僅這樣，在下一章的遞迴中，函式這個工具是無法替代的必要基礎，因此，讓我們一起來看看函式怎麼寫吧！

語法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

//一般寫在main函式前

int biggest(int a, int b, int c){
    if(a >= b && a >= c) return a;
    else if(b >= a && b >= c) return b;
    else return c;
}

int main(){
    int x, y, z;
    cin >> x >> y >> z;
    cout << biggest(x, y, z) << '\n';
}

輸入：

1
5 8 9

輸出：

1
9

這個函式接收三個數，並回傳三者的最大值。下面就來一一介紹每個片段的意思。

回傳值型態

位於函式最前方的 int，代表此函式的回傳值型態。也就是，我回傳(return)給使用者的東西會是什麼型態的。

在本範例中，函式接收三個整數，並回傳三者的最大值，這個最大值自然也是一個整數，所以我們使用 int 作為回傳值。

常見的回傳值就跟變數型態一樣，int、double、string、char、bool 全部都可以作為回傳值。

不過，函式也不一定要 return 東西，如果我只是想單純執行某些指令，不須回傳，就可以使用 void 作為型態，結束時只需寫 return 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

//一般寫在main函式前

void print(int a, int b, int c){
    cout << "a = " << a << "\nb = "<< b << "\nc = " << c << '\n';
    return; // (void 函式可省略)
}

int main(){
    int x, y, z;
    cin >> x >> y >> z;
    print(x, y, z);
}

回傳值與輸入值，並沒有一定要是相同型態，輸入值為 int，也可以回傳 string。

名稱

範例中的名稱即為函式名稱，命名上與變數命名相同，不要碰到關鍵字，其他都可以。

但建議函式最好命名成讓人知道這個函式在做什麼，避免 ‘a’, ‘owo’ 之類的名稱出現。

參數

由括號包住的部分，即為傳入之參數，數量沒有限制，要幾個就幾個。不必與傳入時變數名稱相同，但數量一定要相同，不然會CE。

參數需要宣告型態，傳入時，需與參數型態相同，如果不相同，傳入的數字會自動轉型，如果無法轉型，會導致 CE。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

//一般寫在main函式前

int biggest(int a, int b, int c){
    if(a >= b && a >= c) return a;
    else if(b >= a && b >= c) return b;
    else return c;
}

int main(){
    double x, y;
    cin >> x >> y;
    cout << biggest(x, y, 1.12) << '\n';
}

輸入：

1
2.35 2.54

輸出：

1
2

於進入函式時，double 已被轉型為 int，因此在 biggest 函式中的 a, b, c，是 2, 2, 1。

傳入的方式，其實是將原資料複製一次以後，再拿複製出來的版本給函式中的變數，因此，函式中不管對變數進行了什麼操作，對原資料都是沒有影響的。將變數命名為相同名稱也沒有用，即使有著相同名稱，由於作用範圍不同，他們也不是相同的變數。這部分將於之後”變數的作用範圍”中進一步的探討。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

//一般寫在main函式前

void nothing_happened(int a){
    a -= 2;
    a = a * 9;
}

int main(){
    int a = 3;
    nothing_happened(a);
    cout<<a<<'\n';
}

輸出：

1
3

不過，其實也是有辦法直接傳那個變數的，使用參照(reference)，可以告訴程式，我不要複製，我就是要直接改這個變數！方法也很簡單，只需要加一個&，變成這樣：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

//一般寫在main函式前

void nothing_happened(int a){
    a -= 2;
    a = a * 9;
}

void something_happened(int &a){
    a -= 2;
    a = a * 9;
}

int main(){
    int a = 3;
    nothing_happened(a);
    cout<<a<<'\n';
    something_happened(a);
    cout<<a<<'\n';
}

輸出：

1
2
3
9

函式也可以沒有輸入：

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;

void say_hello(){
    cout << "hello!\n";
}

int main(){
    say_hello();
}

輸出：

1
hello!

函式主體

大致上，你平常怎麼做，函式裡就怎麼寫。if/else、迴圈…全部都跟在main函式裡一樣用就好。

想特別提出來講的一點是，可以使用哪些變數。在main函式中的變數，是無法使用的，函式可以使用的變數，是傳入的參數、在函式裡自己宣告的變數、以及全域且在函式之前宣告的變數。例如：

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;

void say_A(){
    cout << A << "\n";
}

int main(){
    int A = 5;
    say_A();
}

這是一個會 CE 的程式碼，因為 A 是屬於 main 函式的。

你可以這樣寫：

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;

void say_A(int A){
    cout << A << "\n";
}

int main(){
    int A = 5;
    say_A(A);
}

將 A 作為參數傳入，或者是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;

int A = 5;

void say_A(){
    cout << A << "\n";
}

int main(){
    say_A();
    A = 3;
    say_A();
}

輸出：

1
2
5
3

將 A 宣告於全域變數，這樣它就是 “大家的A” 了！

這也是建議陣列應該宣告於全域變數的原因，這樣在使用函式時比較方便。雖然陣列也能透過傳遞指標的方式作為參數傳入，但較為麻煩，因此建議大型陣列一律開在全域，以方便函式使用。

回傳值

return即為回傳的意思，與break等不同，return會直接結束整個函式並回傳其後方接著的值給呼叫它的人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

//一般寫在main函式前

int biggest(int a, int b, int c){
    if(a >= b && a >= c) return a;
    else if(b >= a && b >= c) return b;
    else return c;
}

int main(){
    int x, y;
    cin >> x >> y;
    int n = biggest(x, y, 9);
}

main 函式最後一行，其意思即為，將 n 設為 biggest(x, y, 9) 的回傳值。

回傳值的型態，必須與宣告的回傳型態相同，否則一樣會進行型態轉換，無法轉換則會 CE 。

在型態是 void 的函式中，return 的意思僅為結束函式，畢竟沒有回傳值嘛。

函式中呼叫另一函式

比較少見的情況，不過如果 A 函式中需要用到 B 函式，那 B 函式必須在 A 函式以前宣告，否則會 CE，因為在編譯到 A 函式內部的時候，編譯器還不知道有 B 函式，所以會跳錯誤。

錯誤範例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

void A(){
    for(int i=0;i<5;i++){
        B(i);
    }
}

void B(int x){
    cout<<x<<"\n";
}

int main(){
    A();
}

正確：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

void B(int x){
    cout<<x<<"\n";
}

void A(){
    for(int i=0;i<5;i++){
        B(i);
    }
}

int main(){
    A();
}

那如果，A 函式中需要用到 B 函式，B 函式中也需要用到 A 函式呢？

這其實就有點遞迴的感覺了，下一章會詳細介紹，不過我們先來解決語法問題。

其實，在宣告函式時，可以先不寫內容，之後再寫！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;

void A();
void B(int x);

void A(){
    for(int i=0;i<5;i++){
        B(i);
    }
}

void B(int x){
    if(x == 4) A();
    cout<<x<<"\n";
}

int main(){
    A();
}

只是執行這段程式會停不下來就是了XD。

使用時機

  1. 避免重複寫多次相同的式子。例如，我們需要輸入a, b, c，並計算其三次方加一時，比起這樣：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include<bits/stdc++.h>
    using namespace std;

    int main(){
        int a, b, c;
        cin >> a >> b >> c;
        a = a * a * a + 1;
        b = b * b * b + 1;
        c = c * c * c + 1;
        cout << a << b << c << '\n';
    }

    這樣寫可以避免重複：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include<bits/stdc++.h>
    using namespace std;

    int func(int x){
        return x * x * x + 1;
    }

    int main(){
        int a, b, c;
        cin >> a >> b >> c;
        a = func(a);
        b = func(b);
        c = func(c);
        cout << a << b << c << '\n';
    }

  2. 於大型程式，例如超過200行的程式裡，使用函式將大問題拆解成小問題分別處理，增加程式的可讀性。

  3. 進行遞迴

    下一章再見！

練習

TOJ 170

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
using namespace std;

int A(int n){ 
    for(int g=1;g<=n;g++)
    {
        for(int j=1;j<=n-g;j++){
            cout<<" ";
        }
        for(int j=1;j<=2*g-1;j++){
            cout<<"*";
        }
        cout<<"\n";
    }
}
//1
int B(int n){ 
    for(int z=1;z<=2;z++){
        for(int g=1;g<=n;g++)
        {
            for(int j=1;j<=n-g;j++){
                cout<<" ";
            }
            for(int j=1;j<=2*g-1;j++){
                cout<<"*";
            }
            cout<<"\n";
        }
    }
}
//2
int C(int n){ 
    for(int z=1;z<=n;z++){
        for(int g=1;g<=z;g++)
        {
            for(int j=1;j<=n-g;j++){
                cout<<" ";
            }
            for(int j=1;j<=2*g-1;j++){
                cout<<"*";
            }
            cout<<"\n";
        }
    }    
}
//3
int D(int n){
    A(10*n);
}
//4
int E(int n){ 
    for(int g=1;g<=n;g++)
    {
        for(int j=1;j<=n-g+2;j++){
            cout<<" ";
        }
        for(int j=1;j<=2*g-1;j++){
            cout<<"*";
        }
        cout<<"\n";
    }
    for(int z=1;z<=2*n+3;z++){
        cout<<"#";
    }
    cout<<"\n";
}
//5
int I(int n){ 
    for(int g=1;g<=n;g++)
    {
        for(int j=1;j<=n-g;j++){
            cout<<" ";
        }
        for(int j=1;j<=2*g-1;j++){
            cout<<"*";
        }
        cout<<"\n";
    }
}

int T;
char k;

int main() {
    cin>>T;
    for(int i=1, x;i<=T;i++){
        cin>>c>>x;
        if (k=='A') A(x);
        else if (k=='B') B(x);
        else if (k=='C') C(x);
        else if (k=='D') D(x);
        else if (k=='E') E(x);
        else if (k=='F') A(2*x);
        else if (k=='G') A(3*x);
        else if (k=='H') A(7*x);
        else if (k=='I') I(4*x-1);
        cout << '\n';
    }    
}

發表於 更新於

迴圈

有時候，我們要重複做一件事很多次，比如說，我們要輸入從arr[0] ~ arr[99]的每一個數字，但我們總不能這樣寫：

1
2
3
4
5
6
7
cin>>arr[0];
cin>>arr[1];
cin>>arr[2];
.
.
.
cin>>arr[99];

於是迴圈出現，拯救世界！

for 迴圈

for 迴圈可以說是最常見的迴圈，語法如下：

1
2
3
for(int i=0;i<10;i++){
    // do something...
}

其中，由兩個分號分開的三段，分別代表著以下的意思：

第一個分號前

for(int i=0;i<10;i++)

代表程式執行到迴圈時，第一件要做的事，在範例中，我宣告了一個整數名為 i，並將其值設為 0。

第一個分號到第二個分號間

for(int i=0;i<10;i++)

代表迴圈持續進行的條件，如果不滿足這個條件，程式便會離開迴圈。在範例中，只要 i < 10，我的程式便會一直停在迴圈中。

第二個分號後

for(int i=0;i<10;i++)

代表迴圈每次運行到結尾時，要做的動作。在範例中，我將 i 的值增加了 1。

運行順序

假設將其編號為 0 ~ 2，迴圈內部的程式編號為 3，那麼程式在執行時會這樣跑：

0 (把 i 設為 0) -> 1(判斷 i 是否小於 10) -> 3(內部) -> 2(將i+1) -> 1 -> 3 -> 2……

實例

假如我要印出從 1 ~ 10 的數字，我可以這樣寫：

1
2
3
for(int i=1;i<=10;i++){
    cout<<i<<" ";
}

輸出：

1
1 2 3 4 5 6 7 8 9 10

多層迴圈

迴圈當然可以包住其他迴圈！

1
2
3
4
5
for(int i=0;i<3;i++){
    for(int j=0;j<2;j++){
        cout<<i<<" "<<j<<'\n';
    }
}

輸出：

1
2
3
4
5
6
0 0
0 1
1 0
1 1
2 0
2 1

迴圈變數命名

一般來說，最外層的變數為 i，往內圈是 j, k, l……

因為大家都這樣寫，所以就這樣寫吧XD

在其他地方盡量避免使用到i, j, k等名字，它是留給迴圈用的！

有趣的地方

可以發現，在學完迴圈與陣列後，程式能做的事情根本是指數級增長啊！各位程式設計師，準備好開始動腦想了嗎？之後的題目，可不是這麼簡單就能解決的喔！

while 迴圈

有時候，我們的迴圈不需要用到變數，所以我們的程式可能會寫成這樣：

1
for(;n<10;n++)

這看起來是不是不太好看？所以，while 迴圈出現了！

1
2
3
while(n<10){
    //....
}

只保留了for迴圈中，判斷是否要繼續迴圈的部分，這就是while迴圈！

while 迴圈的特殊應用

while(cin>>n)

cin這個函式其實是會回傳true或false的，如果正確讀到了整數，會回傳true，否則回傳false。而while迴圈接到false時，就會離開迴圈！

所以，假設有這樣一個題目：

讀入不定數量的整數後，輸出他們的總和

就可以這樣寫：

1
2
3
int tot = 0;
while(cin>>n) tot += n;
cout<<tot<<'\n';

這還蠻重要的，因為如果不這樣做的話，可能就要使用 getline，當作字串讀進來後，再自己想辦法切了，使用while(cin>>)可以節省很多時間。

while(t–)

有時，我們要做一件事 t 次，所以我們可能會這樣寫：

1
for(int i=0;i<t;i++)

或

1
2
3
while(t>0){
    t--;
}

而t–，其實就是第二種的縮寫版

我們這樣寫，有相同的效果：

1
2
3
while(t--){

}

t– 遇上while要判斷時，會先判斷它是不是true，之後再把它減 1。在前面的單元有說過，一個整數只要不是 0，它的值都是true，所以假設 t 是 1，那麼程式會先判斷 t 是否不是 0，再將其減一。

跟 t– 相反的是 –t，它會先把 t 減 1 後，再判斷 t 是否不是 0。所以對於一個正整數 t，while(–t) 只會執行 t-1 次。

break

我們也可以在迴圈內的代碼中，使用break來離開整個迴圈。像這樣：

1
2
3
4
5
6
7
for(int i=0;i<5;i++){
    if(i==3){
        cout<<"Break!\n";
        break;
    }
    cout<<i<<'\n';
}

輸出：

1
2
3
4
0
1
2
Break!

break會直接跳出整個迴圈，不過請適當使用，如果是可以放在for迴圈判斷式裡的，就請不要濫用break，否則程式可讀性會降低

1
2
3
4
5
//錯誤示範
for(int i=1;;i++){
    cout<<i<<'\n';
    if(i%3==0) break;
}
1
2
3
4
//正確
for(int i=1;i%3!=0;i++){
    cout<<i<<'\n';
}

多層迴圈中的break，只會跳出自己那一層，不會將全部一起跳出，要特別注意！

例如：

1
2
3
4
5
6
for(int i=0;i<3;i++){
    for(int j=0;j<2;j++){
        if(i==1) break;
        cout<<i<<" "<<j<<'\n';
    }
}

輸出：

1
2
3
4
0 0
0 1
2 0
2 1

continue

相較於break，continue不會跳出整個迴圈，而是像略過一樣，直接略過那一次的迴圈。

1
2
3
4
5
6
for(int i=0;i<5;i++){
    if(i==3){
        continue;
    }
    cout<<i<<'\n';
}

輸出：

1
2
3
4
0
1
2
4

continue後，程式忽略該行以下所有迴圈內的程式碼，直接執行i++後，判斷是否 < 5，接著進入下一次的迴圈。

適當運用 break 與 continue，對於設計程式有著不少幫助。

停不下來

寫迴圈，編譯執行以後，發現程式停不下來，怎麼辦？

一定有地方寫爛了，而且高機率是判斷式，如果一個判斷迴圈是否要繼續的判斷式恆為true，那麼這程式不可能停下來。

常見的錯誤包括：

1
for(int i=0;i<5;i--)

i<5 恆成立，因為 i 只會變小，不會變大(執行2147483648次後會因為int overflow停下來啦XD)

或者：

1
for(int i=5;i=5;i++)

這裡，判斷式做的事情，不是判斷i是否等於5，因為那是 == 。

判斷式將 5 指派給 i 後，判斷 i 是否是 true，因為 i 才剛剛被指派成 5，所以它當然是true啊，所以，這程式就停不下來了。

當程式停不下來的時候，有可能就一直不顯示，或者也有可能 RE，要特別注意。

來創造世界吧！

學到這，基本上，已經能用程式做很多事了，接下來就讓你的想像力，奔馳在鍵盤上吧！

練習(極大量，但建議兩星以下的題都寫)

TOJ 104

TOJ 106

TOJ 107

TOJ 110

TOJ 114

TOJ 117

TOJ 119

★★ TOJ 3

★★ TOJ 8

★★★ TOJ 120

本題 (TOJ 120) 小提醒：電腦的速度，可以用一秒 $10^8$ 估算，若電腦需要進行 $10^{10}$ 次運算，可能會花上 100 秒，導致 TLE。

★★★ TOJ 485

★★★★★ TOJ 501

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//TOJ 104
#include<bits/stdc++.h>
using namespace std;

int n;

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n-i-1;j++) cout<<" ";
        for(int j=0;j<2*i+1;j++) cout<<"*";
        cout<<'\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
//TOJ 106
#include<bits/stdc++.h>
using namespace std;

int n=2;

int main(){
    while(n%71!=0) n = n*2+1;
    if(n%3==0) cout<<"right\n";
    else cout<<"left\n";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//TOJ 107
#include<bits/stdc++.h>
using namespace std;

int n=30, ans;

int main(){
	for(int i=1;i<=n;i++){
		int son = 1;
		int dau = i;
		int son_son = i * (i * (i+1) / 2);
		ans += son + dau + son_son;
	}
	cout<<ans<<'\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//TOJ 3
#include<bits/stdc++.h>
using namespace std;

int a, b, t;

int main(){
    cin>>t;
    while(t--){ // 這句看不懂的話往上翻
        cin>>a>>b;
        while(a!=0 && b!=0){ // 關鍵字：輾轉相除法
            if(a > b) a %= b;
            else b %= a;
        }
        if(a > 0) cout<<a<<'\n';
        else cout<<b<<'\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//TOJ 8
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string s;
    while(cin >> n){ // 多筆測資
        cin.ignore(); // 看不懂的話，複習0-6進階輸入輸出
        getline(cin,s);
        int x = s.size()/n;
        for(int i=0; i<n; i++) {
            for(int j=0; j<x; j++) {
                cout << s[i+n*j];
            }
        }
        cout << '\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//TOJ 110
#include <iostream>
using namespace std;

int t, n;

int main(){
    cin >> t;
    while(t--){
        cin >> n;
        
        // 上面三角
        for(int i=1, j=n-1, k=1; i<=n-3; i++, j--, k+=2){
            for(int l=1; l<=j; l++) cout << ' ';
            for(int l=1; l<=k; l++) cout << '*';
            cout << '\n';
        }
        
        // 中間三行-1
        for(int i=1;i<=2*n-1;i++) cout<<'*';
        cout<<'\n';
        // 中間三行-2
        cout<<' ';
        for(int i=1;i<=2*n-3;i++) cout<<'*';
        cout<<'\n';
        // 中間三行-3
        for(int i=1;i<=2*n-1;i++) cout<<'*';
        cout<<'\n';
        // 下面三角
        for(int i=1, j=3, k=2*n-7; i<=n-3; i++, j++, k-=2){
            for(int l=1; l<=j; l++) cout << ' ';
            for(int l=1; l<=k; l++) cout << '*';
            cout << '\n';
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// TOJ 114
#include<bits/stdc++.h>
using namespace std;

int ans=0, arr[5][6];
int main(){
    for(int i=0;i<5;i++){
        for(int j=0;j<6;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<4;j++){
            if(arr[i][j]==arr[i][j+1] && arr[i][j]==arr[i][j+2]) ans++;
            if(arr[i][j]==arr[i+1][j] && arr[i][j]==arr[i+2][j]) ans++;
        }
    }
    if(ans>0) cout<<"Yes\n";
    else cout<<"No\n";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// TOJ 117
#include <iostream>
using namespace std;
int n, ans;

int main(){
    cin >> n;
    for (int i=0,tmp;i<n;i++){
        cin >> tmp;
        if(tmp > ans) ans = tmp;
    }
    cout << ans << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// TOJ 119
#include<bits/stdc++.h>
using namespace std;

int n, arr[200005], q;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>arr[i];
	cin>>q;

	bool ok = 1;
	for(int i=0,l,r;i<q;i++){
		cin>>l>>r;
		if(abs(l-r) > 8){ // abs: 絕對值函數
			ok = 0;
			break;
		}
		swap(arr[l], arr[r]); //swap: 交換
	}

	if(ok) cout<<"SORTED!\n";
	else cout<<"I QUIT!\n";
	for(int i=1;i<=n;i++){
		cout<<arr[i];
		if(i<n) cout<<" ";
		else cout<<'\n';
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// TOJ 120
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n, q, arr[200005], pre[200005]; //關鍵字：前綴和

int main(){
    ios::sync_with_stdio(0), cin.tie(0);// 看不懂的話，複習0-6進階輸入輸出
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i], pre[i] = pre[i-1] + arr[i];
    cin>>q;
    for(int i=1,l,r;i<=q;i++){
        cin>>l>>r;
        if(l>r) swap(l, r);
        cout<<pre[r] - pre[l-1]<<'\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// TOJ 485
#include<bits/stdc++.h>
using namespace std;

int n;
string s;

int main(){
    cin>>n>>s;
    int ans = n-1;
    for(int i=n-1;i>=0;i--){
        bool is_p = 1;
        for(int l=i,r=n-1;l<r;l++,r--){
            if(s[l]!=s[r]){
                is_p = 0;
                break;
            }
        }
        if(is_p){
            ans = i;
        }
    }
    cout<<ans<<'\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// TOJ 501 難度很高 之後dp時會教到這題
#include<bits/stdc++.h>
using namespace std;

int n, ans, arr[200005];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i], arr[i+n] = arr[i];        
    int ans = 0;
    for(int i=1,cur=0;i<=2*n;i++){
        cur = min(cur+1,arr[i]);
        ans = max(ans,cur);
    }
    cout<<min(ans,n)<<'\n';
}