迴圈
有時候，我們要重複做一件事很多次，比如說，我們要輸入從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++){
}
|
其中，由兩個分號分開的三段，分別代表著以下的意思：
第一個分號前
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
2
3
4
5
| for(int i=0;i<3;i++){
for(int j=0;j<2;j++){
cout<<i<<" "<<j<<'\n';
}
}
|
輸出：
迴圈變數命名
一般來說，最外層的變數為 i，往內圈是 j, k, l……
因為大家都這樣寫，所以就這樣寫吧XD
在其他地方盡量避免使用到i, j, k等名字，它是留給迴圈用的！
有趣的地方
可以發現，在學完迴圈與陣列後，程式能做的事情根本是指數級增長啊！各位程式設計師，準備好開始動腦想了嗎？之後的題目，可不是這麼簡單就能解決的喔！
while 迴圈
有時候，我們的迴圈不需要用到變數，所以我們的程式可能會寫成這樣：
這看起來是不是不太好看？所以，while 迴圈出現了！
只保留了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 次，所以我們可能會這樣寫：
或
而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';
}
|
輸出：
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';
}
}
|
輸出：
continue
相較於break，continue不會跳出整個迴圈，而是像略過一樣，直接略過那一次的迴圈。
1
2
3
4
5
6
| for(int i=0;i<5;i++){
if(i==3){
continue;
}
cout<<i<<'\n';
}
|
輸出：
continue後，程式忽略該行以下所有迴圈內的程式碼，直接執行i++後，判斷是否 < 5，接著進入下一次的迴圈。
適當運用 break 與 continue，對於設計程式有著不少幫助。
停不下來
寫迴圈，編譯執行以後，發現程式停不下來，怎麼辦？
一定有地方寫爛了，而且高機率是判斷式，如果一個判斷迴圈是否要繼續的判斷式恆為true，那麼這程式不可能停下來。
常見的錯誤包括：
i<5 恆成立，因為 i 只會變小，不會變大(執行2147483648次後會因為int overflow停下來啦XD)
或者：
這裡，判斷式做的事情，不是判斷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
|
#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
|
#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
|
#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
|
#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
|
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
while(cin >> n){
cin.ignore();
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
|
#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';
}
for(int i=1;i<=2*n-1;i++) cout<<'*';
cout<<'\n';
cout<<' ';
for(int i=1;i<=2*n-3;i++) cout<<'*';
cout<<'\n';
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
|
#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
|
#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
|
#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){
ok = 0;
break;
}
swap(arr[l], arr[r]);
}
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
|
#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);
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
|
#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
|
#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';
}
|