# 初學者也適用的ZeroJudge C語言詳解
一個程式小白的學習紀錄，希望能以最基本的文字與思路，幫助到其他程式初學者！
## [Codebar 程式酒吧](https://noah-0831.github.io/)
由於版面設計，為了提供更完整的文章分類與更新，歡迎移駕到我的[新部落格](https://noah-0831.github.io/)！
## a系列
### [a001. 哈囉](https://noah-0831.github.io/a001-%E5%93%88%E5%9B%89)
### [a002. 簡易加法](https://noah-0831.github.io/a002-%E7%B0%A1%E6%98%93%E5%8A%A0%E6%B3%95/)
### [a003. 兩光法師占卜術](https://noah-0831.github.io/a003-%E5%85%A9%E5%85%89%E6%B3%95%E5%B8%AB%E5%8D%A0%E5%8D%9C%E8%A1%93/)
### [a004. 文文的求婚](https://noah-0831.github.io/a004-%E6%96%87%E6%96%87%E7%9A%84%E6%B1%82%E5%A9%9A/)
### [a005. Eva的回家作業](https://noah-0831.github.io/a005-Eva%E7%9A%84%E5%9B%9E%E5%AE%B6%E4%BD%9C%E6%A5%AD/)
### [a006 一元二次方程式](https://noah-0831.github.io/a006-%E4%B8%80%E5%85%83%E4%BA%8C%E6%AC%A1%E6%96%B9%E7%A8%8B%E5%BC%8F/)
### [a009. 解碼器](https://noah-0831.github.io/a009-%E8%A7%A3%E7%A2%BC%E5%99%A8/)
### [a010. 因數分解](https://noah-0831.github.io/a010-%E5%9B%A0%E6%95%B8%E5%88%86%E8%A7%A3/)
**連結題目：[a740. 质因数之和](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a740-%E8%B4%A8%E5%9B%A0%E6%95%B0%E4%B9%8B%E5%92%8C)**
### [a013. 羅馬數字](https://noah-0831.github.io/a013-%E7%BE%85%E9%A6%AC%E6%95%B8%E5%AD%97/)
### [a015. 矩陣的翻轉](https://noah-0831.github.io/a015-%E7%9F%A9%E9%99%A3%E7%9A%84%E7%BF%BB%E8%BD%89/)
### [a020. 身分證檢驗](https://noah-0831.github.io/a020-%E8%BA%AB%E5%88%86%E8%AD%89%E6%AA%A2%E9%A9%97/)
**連結題目：[a054. 電話客服中心](https://noah-0831.github.io/a054-%E9%9B%BB%E8%A9%B1%E5%AE%A2%E6%9C%8D%E4%B8%AD%E5%BF%83/)**
### [a022. 迴文](https://noah-0831.github.io/a022-%E8%BF%B4%E6%96%87/)
**連結題目：[a224. 明明愛明明](https://noah-0831.github.io/a224-%E6%98%8E%E6%98%8E%E6%84%9B%E6%98%8E%E6%98%8E/)**
### [a024. 最大公因數(GCD)](https://noah-0831.github.io/a024-%E6%9C%80%E5%A4%A7%E5%85%AC%E5%9B%A0%E6%95%B8(GCD)/)
### [a034. 二進位制轉換](https://noah-0831.github.io/a034-%E4%BA%8C%E9%80%B2%E4%BD%8D%E5%88%B6%E8%BD%89%E6%8F%9B/)
### [a038. 數字翻轉](https://noah-0831.github.io/a038-%E6%95%B8%E5%AD%97%E7%BF%BB%E8%BD%89/)
### [a040. 阿姆斯壯數](https://noah-0831.github.io/a040-%E9%98%BF%E5%A7%86%E6%96%AF%E5%A3%AF%E6%95%B8/)
### [a042. 平面圓形切割](https://noah-0831.github.io/a042-%E5%B9%B3%E9%9D%A2%E5%9C%93%E5%BD%A2%E5%88%87%E5%89%B2/)
### [a044. 空間切割](https://noah-0831.github.io/a044-%E7%A9%BA%E9%96%93%E5%88%87%E5%89%B2/)
### [a053. Sagit's 計分程式](https://noah-0831.github.io/a053-Sagit-s-%E8%A8%88%E5%88%86%E7%A8%8B%E5%BC%8F/)
### [a054. 電話客服中心](https://noah-0831.github.io/a054-%E9%9B%BB%E8%A9%B1%E5%AE%A2%E6%9C%8D%E4%B8%AD%E5%BF%83/)
**連結題目：[a020. 身分證檢驗](https://noah-0831.github.io/a020-%E8%BA%AB%E5%88%86%E8%AD%89%E6%AA%A2%E9%A9%97/)**
### [a058. MOD3](https://noah-0831.github.io/a058-MOD3/)
### [a059. 完全平方和](https://noah-0831.github.io/a059-%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E5%92%8C/)
### [a065. 提款卡密碼](https://noah-0831.github.io/a065-%E6%8F%90%E6%AC%BE%E5%8D%A1%E5%AF%86%E7%A2%BC/)
### [a104. 排序](https://noah-0831.github.io/a104-%E6%8E%92%E5%BA%8F/)
**連結題目：[a225. 明明愛排列](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a225-%E6%98%8E%E6%98%8E%E6%84%9B%E6%8E%92%E5%88%97)**
### [a121. 質數又來囉](https://noah-0831.github.io/a121-%E8%B3%AA%E6%95%B8%E5%8F%88%E4%BE%86%E5%9B%89)
### [a147. Print it all](https://noah-0831.github.io/a147-Print-it-all/)
### [a148. You Cannot Pass?!](https://noah-0831.github.io/a148-You-Cannot-Pass/)
### [a149. 乘乘樂](https://noah-0831.github.io/a149-%E4%B9%98%E4%B9%98%E6%A8%82/)
### [a215. 明明愛數數](https://noah-0831.github.io/a215-%E6%98%8E%E6%98%8E%E6%84%9B%E6%95%B8%E6%95%B8/)
### [a216. 數數愛明明](https://noah-0831.github.io/a216-%E6%95%B8%E6%95%B8%E6%84%9B%E6%98%8E%E6%98%8E/)
### [a224. 明明愛明明](https://noah-0831.github.io/a224-%E6%98%8E%E6%98%8E%E6%84%9B%E6%98%8E%E6%98%8E/)
**連結題目：[a022. 迴文](https://noah-0831.github.io/a022-%E8%BF%B4%E6%96%87/)**
### [a225. 明明愛排列](https://noah-0831.github.io/a225-%E6%98%8E%E6%98%8E%E6%84%9B%E6%8E%92%E5%88%97/)
**連結題目：[a104. 排序](https://noah-0831.github.io/a104-%E6%8E%92%E5%BA%8F/)**
### [a229. 括號匹配問題](https://zerojudge.tw/ShowProblem?problemid=a229)
**連結題目：[a524. 手機之謎](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a524-%E6%89%8B%E6%A9%9F%E4%B9%8B%E8%AC%8E)**
## 以下施工中
### [a240. 1/17小數第 n 位](https://zerojudge.tw/ShowProblem?problemid=a240)
**連結題目：[a248. 新手訓練 ~ 陣列應用](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a248-%E6%96%B0%E6%89%8B%E8%A8%93%E7%B7%B4--%E9%99%A3%E5%88%97%E6%87%89%E7%94%A8)**
**解題思路**
我們可以模擬直式除法，將運算過程拆成一位一位來看，每次都先將現在的數字乘上10倍作被除數，取商數後將其存進陣列中，再將餘令為新的被除數，最後輸出陣列即可得商。
舉例來說，我們先將1乘以10變10，10除以17得0，因此1除以17的小數點後第一位即為0。接者我們再將10乘以10變100作新的被除數，100除以17得5，即為1除以17的小數點後第二位。接著我們將100減去17乘5後得15，再乘以10就會是新的被除數150，以此類推。
:::info
**注意事項**
這一題和[a248. 新手訓練 ~ 陣列應用](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a248-%E6%96%B0%E6%89%8B%E8%A8%93%E7%B7%B4--%E9%99%A3%E5%88%97%E6%87%89%E7%94%A8)的概念十分相似。或者說，本題其實就是a248在a=1，b=17時的情況。因此，如果已經寫完本題的人，可以試著挑戰a248。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int t;
scanf("%d", &t);
for(int i=0;i<t;i++) {
int n;
scanf("%d", &n);
int num=1, ans[n], sum=0;
for(int i=0;i<n;i++) {
num*=10;
ans[i]=num/17;
num-=ans[i]*17;
sum+=ans[i];
}
printf("%d %d\n", ans[n-1], sum);
}
return 0;
}
```
### [a244. 新手訓練 ~ for + if](https://zerojudge.tw/ShowProblem?problemid=a244)
**解題思路**
偵測到輸入的a值後，依a值進行不同種類的運算。
:::info
**注意事項**
本題測資較大，部分測資的運算結果會超過int型態變數所能儲存的最大數值，因此需使用long long型態變數，寫法是%lld。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int N;
scanf("%d", &N);
for(int i=0;i<N;i++) {
long long a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
switch(a) {
case 1:
printf("%lld\n", b+c);
break;
case 2:
printf("%lld\n", b-c);
break;
case 3:
printf("%lld\n", b*c);
break;
case 4:
printf("%lld\n", b/c);
break;
}
}
return 0;
}
```
### [a248. 新手訓練 ~ 陣列應用](https://zerojudge.tw/ShowProblem?problemid=a248)
**連結題目：[a240. 1/17小數第 n 位](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a240-117%E5%B0%8F%E6%95%B8%E7%AC%AC-n-%E4%BD%8D)**
**解題思路**
一般來說，要顯示除法運算後所得的商數，可以直接用將商數用一浮點數型態的變數儲存起來，在輸出時再設定要顯示到第幾位。然而根據輸出說明，本題最多要顯示到小數點後第10000位，明顯超出任何資料型態的變數的儲存範圍。因此，我們可以改模擬直式除法，將運算過程拆成一位一位來看，每次都先將現在的數字乘上10倍作被除數，取商數後將其存進陣列中，再將餘令為新的被除數，最後輸出陣列即可得商。
舉1除以17為例，我們先將1乘以10變10，10除以17得0，因此1除以17的小數點後第一位即為0。接者我們再將10乘以10變100作新的被除數，100除以17得5，即為1除以17的小數點後第二位。接著我們將100減去17乘5後得15，再乘以10就會是新的被除數150，以此類推。
:::info
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用[EOF寫法](
https://www.796t.com/content/1544817994.html)判斷程式執行的條件。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int a, b, N;
while(scanf("%d%d%d", &a, &b, &N)!=EOF) {
printf("%d.", a/b);
a%=b;
int ans[N];
for(int i=0;i<N;i++) {
a*=10;
ans[i]=a/b;
a-=ans[i]*b;
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}
```
### [a263. 日期差幾天](https://zerojudge.tw/ShowProblem?problemid=a263)
**解題思路**
根據題意，我們必須求出兩個日期相差幾天。因為對我們來說，完整的一年或是一個月的天數比較好算，所以我們先算從第一筆日期的下個到第二筆日期的上個月之間的天數，再把頭尾沒算到的天數補上。
舉例來說，假如測資的兩個日期分別是2020年1月28日和2023年4月3日，我們可以先算2020年2月初到2023年3月底的天數，也就是335+365+365+90=1155天。接著我們再算剛剛還沒算到的頭尾的天數，也就是3+3=6天。據此，可知2020年1月28日到2023年4月3日共相差1155+6=1161天。
:::info
**注意事項**
注意第二筆日期未必比第一筆日期晚。因此如果我們要用第二筆日期減去第一筆日期來計算兩者間隔幾天，需先檢查兩筆日期何者較晚。若第二筆日期比第一筆日期早，須將兩者交換。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int year1, month1, date1, year2, month2, date2;
while(scanf("%d%d%d%d%d%d", &year1, &month1, &date1, &year2, &month2, &date2)!=EOF) {
if(year1>year2) {
int temp=year1;
year1=year2;
year2=temp;
temp=month1;
month1=month2;
month2=temp;
temp=date1;
date1=date2;
date2=temp;
}
else if(year1==year2 && month1>month2) {
int temp=month1;
month1=month2;
month2=temp;
}
else if(year1==year2 && month1==month2 && date1>date2) {
int temp=date1;
date1=date2;
date2=temp;
}
int output=0;
for(int i=year1+1;i<year2;i++) {
if(i%4==0 && i%100!=0 || i%100==0 && i%400==0)
output+=366;
else
output+=365;
}
output=output-date1;
for(int i=month1;i<=12;i++) {
if(i==1 || i==3 || i==5 || i==7 || i==8 || i==10 || i==12)
output+=31;
else if(i==2) {
if(year1%4==0 && year1%100!=0 || year1%100==0 && year1%400==0)
output+=29;
else
output+=28;
}
else
output+=30;
}
for(int i=1;i<month2;i++) {
if(i==1 || i==3 || i==5 || i==7 || i==8 || i==10 || i==12)
output+=31;
else if(i==2) {
if(year2%4==0 && year2%100!=0 || year2%100==0 && year2%400==0)
output+=29;
else
output+=28;
}
else
output+=30;
}
output+=date2;
if(year1==year2)
if(year1%4==0 && year1%100!=0 || year1%100==0 && year1%400==0)
output-=366;
else
output-=365;
printf("%d\n", output);
}
return 0;
}
```
### [a271. 彩色蘿蔔](https://zerojudge.tw/ShowProblem?problemid=a271)
**解題思路**
在此先感謝M_SQRT大幫忙!
根據題意，本題有多筆測資。
每筆測資的第一行有x, y, z, w, n, m六個數字，分別代表:
x:吃紅蘿蔔後，體重+x公斤
y:吃白蘿蔔後，體重+y公斤
z:吃黃蘿蔔後，體重-z公斤
w:吃黑蘿蔔後，體重-w公斤，並且進入中毒狀態(可疊加)
n:進入中毒狀態後，體重每日-n公斤
m:兔子初始的體重
每筆測資的第二行有未知個數字(可能沒有數字)，分別代表:
0:沒吃蘿蔔
1:吃紅蘿蔔
2:吃白蘿蔔
3:吃黃蘿蔔
4:吃黑蘿蔔
而我們的目標是計算並輸出兔子的體重，一旦過程中兔子體重小於等於0，則必須立即輸出「bye~Rabbit」。
比起體重的計算，本題最困難的地方在於讀取輸入測資，有兩個比較需要注意的地方。第一是**測資第一行和第二行之間存在回車鍵(\n)**，因此為了避免在讀取每日吃的蘿蔔種類時將其讀入，我們可以先將其用字元變數c讀起來 ; 第二是**每筆測資的第二行數字的數量並不固定，甚至有可能沒有輸入**。如果用常見的scanf()函式偵測輸入，我們會不知道要在哪裡停止偵測而TLE。這裡的做法是使用gets()函式將整行輸入連同空白，以字串的形式讀進來。
再讀取到輸入以後，我們可以用for迴圈從第0項開始，以switch()函式判斷每日吃的蘿蔔種類，再對體重進行相對應的運算。這裡比較需要注意的地方有三個。第一是**空白項的避免**。因為剛剛讀取輸入的時候是整行連同空白讀進來，因此每項之間會夾雜一項空格，可以使用continue敘述略過對空白項的判斷，或是直接將for迴圈控制變數的遞增條件設定成+=2跳過空白項 ; 第二是**中毒狀態的計算**。因為兔子是早上先中毒，晚上才吃東西，所以吃到黑蘿蔔後要到隔天早上才會進入中毒狀態，吃黑蘿蔔當天的體重不會-n。第三是**兔子是否死亡的判斷**，兔子可能死亡的情況有兩個，分別是因中毒狀態而死，以及吃到不好的蘿蔔後體重減輕而死。因此在判斷兔子因中毒狀態導致的體重變化和吃完蘿蔔後的體重判斷後，都必須判斷兔子體重是否小於等於0。在注意上述幾點後，相信你也可以AC的!
:::info
**注意事項**
本程式碼使用了strlen()函式表示字串的長度。由於strlen()函式並非標準函式庫裡的函式，使用前必須引用<string.h>函式庫。
:::
**程式碼**
```C==
#include <stdio.h>
#include <string.h>
int main() {
int N;
scanf("%d", &N);
for(int i=0;i<N;i++) {
int x, y, z, w, n, m, poison=0;
scanf("%d%d%d%d%d%d", &x, &y, &z, &w, &n, &m); /*讀取測資第一行的輸入*/
char c=getchar(); /*讀取測資第一行和第二行之間的回車鍵，避免在讀取每日吃到的蘿蔔種類時讀到*/
char carrot[1000]={}; /*注意這裡的測資數量較大，因此這裡的陣列大小也要令大一點，否則會出現記憶體區段錯誤，系統會呼叫abort()函式中斷程式執行*/
gets(carrot); /*讀取測資第二行的輸入，直接以字串形式整行連同空白讀進來*/
for(int j=0;j<strlen(carrot);j+=2) { /*因為剛剛有讀到空白，因此設定i+=2跳過空白項*/
m-=poison*n; /*早上進入中毒狀態，體重因中毒而減輕*/
if(m<=0) { /*判斷兔子是否因中毒狀態而死*/
printf("bye~Rabbit\n");
break;
}
switch(carrot[j]) { /*根據兔子每日吃的蘿蔔種類，對體重進行相對應的運算*/
case '0': /*沒吃蘿蔔*/
break;
case '1': /*吃紅蘿蔔*/
m+=x; /*體重+x公斤*/
break;
case '2': /*吃白蘿蔔*/
m+=y; /*體重+y公斤*/
break;
case '3': /*吃黃蘿蔔*/
m-=z; /*體重-z公斤*/
break;
case '4': /*吃黑蘿蔔*/
m-=w; /*體重-w公斤*/
poison++; /*隔天早上才進入中毒狀態，因此先註記起來但不用減少體重*/
break;
}
if(m<=0) { /*判斷兔子是否因吃到不好的蘿蔔後體重減輕而死*/
printf("bye~Rabbit\n");
break;
}
}
if(m>0)
printf("%dg\n", m);
}
return 0;
}
```
### [a291. nAnB problem](https://zerojudge.tw/ShowProblem?problemid=a291)
**解題思路**
由題目可知輸入的數字可以被分為三種情況。第一種是A，代表該數字有出現在密碼中，且位置與密碼相同；第二種是B，代表該數字有出現在密碼中，但位置與密碼不同；第三種是該數字並未出現在密碼中。而我們的目標，是找到並輸出A與B的數量。
其中A的部分只要用for迴圈檢查輸入數列與密碼在各個位置相同的數量即可，但B的數量就比較難判斷了，因為可能有「該數字的確有出現在密碼中，可是數量沒這麼多」的情況。舉密碼為1234，輸入數列為1111的情況為例，雖然輸入數列的四個數字都有出現在密碼中，但密碼只有一個1，因此正確答案應該是1A0B，而不是1A3B。為了避免誤判這樣的情況，這裡的想法是先比對密碼與輸入數列各個數字的數量，由兩者中較小的值可知該數字重複出現在兩者的次數，也就是A+B，減去A之後就可以得到B了!
:::info
**注意事項**
在本程式碼第101行，我們會看到「[條件運算子](https://shengyu7697.github.io/cpp-ternary-operator/)」的寫法，也就是「(條件)？(敘述1)：(敘述2)」。在執行到這行程式的時候，會依據條件決定接下來的動作。如果符合條件就回傳敘述1的值，否則回傳敘述2的值。以本程式碼為例，若password_class[i]大於等於input_class[i]，那麼q的值將會加上input_class[i]，否則會加上password_class[i]。
雖然對於初學者來說，這的確是一個較少機會接觸的寫法。但因為概念簡單且使用便利，在這裡就先介紹給大家了。事實上用if條件句也可以達成一樣的功能，只是程式碼會比較長，就看各位的取捨了。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int temp;
while(scanf("%d", &temp)!=EOF) {
int password_class[10];
for(int i=0;i<10;i++)
password_class[i]=0;
int password[4];
for(int i=0;i<4;i++) {
if(i==0)
password[i]=temp;
else
scanf("%d", &password[i]);
switch(password[i]) {
case 0:
password_class[0]++;
break;
case 1:
password_class[1]++;
break;
case 2:
password_class[2]++;
break;
case 3:
password_class[3]++;
break;
case 4:
password_class[4]++;
break;
case 5:
password_class[5]++;
break;
case 6:
password_class[6]++;
break;
case 7:
password_class[7]++;
break;
case 8:
password_class[8]++;
break;
case 9:
password_class[9]++;
break;
}
}
int n;
scanf("%d", &n);
for(int i=0;i<n;i++) {
int input_class[10];
for(int i=0;i<10;i++)
input_class[i]=0;
int input[4], p=0, q=0;
for(int j=0;j<4;j++) {
scanf("%d", &input[j]);
if(input[j]==password[j])
p++;
switch(input[j]) {
case 0:
input_class[0]++;
break;
case 1:
input_class[1]++;
break;
case 2:
input_class[2]++;
break;
case 3:
input_class[3]++;
break;
case 4:
input_class[4]++;
break;
case 5:
input_class[5]++;
break;
case 6:
input_class[6]++;
break;
case 7:
input_class[7]++;
break;
case 8:
input_class[8]++;
break;
case 9:
input_class[9]++;
break;
}
}
for(int i=0;i<10;i++)
q+=(password_class[i]>=input_class[i]) ? input_class[i] : password_class[i];
q-=p;
printf("%dA%dB\n", p, q);
}
}
return 0;
}
```
### [a410. 解方程](https://zerojudge.tw/ShowProblem?problemid=a410)
**解題思路**
根據國中所學，二元一次聯立方程式解的情形有三種，分別是恰一組解、無(實數)解或是有無限多組解。本程式碼採用[克拉瑪公式](https://www.ehanlin.com.tw/app/keyword/%E9%AB%98%E4%B8%AD/%E6%95%B8%E5%AD%B8/%E5%85%8B%E6%8B%89%E7%91%AA%E5%85%AC%E5%BC%8F.html)，是一種利用兩方程式的係數比關係，判斷二元一次聯立方程式解的情況的方法。在確定方程式恰有一組解後，就可以利用加減消去法、代入消去法等方式求解了。
:::info
**注意事項**
本題要求輸出解至小數點後二位，但方程式的係數是整數。而我們知道如果將兩int型態的變數相除，商也會是int型態，也就是說程式會自動將其無條件捨去至整數位。因此求解的時候須注意資料型態的轉換。
另外在本程式碼第8行，我們會看到「%.2」。這是一個特殊寫法，可以控制讀取與輸入的精確度。以「%a.b」來說，a代表的是總長度，b是精確度，即小數點後的位數。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int a, b, c, d, e, f;
scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
float x, y;
if(a*e-b*d!=0) /*利用克拉瑪公式判斷解的情形*/
printf("x=%.2f\ny=%.2f\n", (float)(c*e-f*b)/(float)(a*e-d*b), (float)(c*d-f*a)/(float)(b*d-e*a)); /*利用加減消去法求解*/
else if(a*e-b*d==0 && (a*e-b*d!=0) || (a*f-c*d!=0))
printf("No answer");
else
printf("Too many");
return 0;
}
```
### [a414. 位元運算之進位篇](https://zerojudge.tw/ShowProblem?problemid=a414)
**解題思路**
根據題意，我們必須求出一個十進制數字加1後，在二進制中進位的次數。而因為在二進制中，只要該位數的數值大於等於二就會進位，因此所謂「加1後在二進制中進位的次數」，其實就是「該數字在二進制中，從右側數來連續的1的個數」。舉例來說，十進制的11在二進制中為1011，從右側數來連續的1有2個，因此可知需進位2次。
據此，我們可以藉由將輸入的數字不斷除以2，從該數字在二進制中最高的位數開始降次檢查。並藉由該數字除以2是否餘1，判斷該數字在二進制中最右側的數字是否為1。進而得知該數字在二進制中，從右側數來連續的1的個數。
:::info
**注意事項**
布林代數是一種變數，可分為0和1，當其值為0的時候代表false，為1(或其他正整數)時代表true。在下面的程式碼中，我們會看到while(1){}的寫法，這裡的1即為布林值，也就是說這個while迴圈的條件永遠成立，會不斷執行下去，直到遇到break敘述為止。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
while(1) {
int num, time=0;
scanf("%d", &num);
if(num==0)
break;
while(num%2==1) {
num/=2;
time++;
}
printf("%d\n", time);
}
return 0;
}
```
### [a417. 螺旋矩陣](https://zerojudge.tw/ShowProblem?problemid=a417)
**解題思路**
透過觀察規律可知，本題螺旋矩陣中的元素是從1到N^2^的連續正整數。順序是從左上角的1開始，若方向是順時鐘則先往右、再往下、再往左、再往上，若方向是逆時鐘則則先往下、再往右、再往上、再往左，逐一填入元素，形成一個循環。因此，我們可以宣告一個二維陣列，從(0,0)開始，藉由迴圈與條件句，判斷下一步移動的方向，進而填完整個陣列。
本題的解題關鍵是判斷要移動幾步再變換方向。第一次移動時會移動N步再換方向，接下來的步數從N-1開始，每兩次遞減。舉N=3、M=1的情況微例，因為是順時鐘方向，因此從(0,0)出發，先往右3步到(2,0)，再往下2步到(2,2)，再往左2步到(0,2)，再往上1步到(0,1)，最後再往右一步到(1,1)。
:::info
**注意事項**
根據題意，矩陣值之間寬度為5。因此在本程式碼第59行，我們會看到「printf("%5d", arr[row][column]);」的寫法，其中%5d的5指的就是每筆輸出之間的距離，會以空白補上。(注意不要用手動輸出空白的方式，很容易出錯)
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int T;
scanf("%d", &T);
for(int i=0;i<T;i++) {
int N, M;
scanf("%d %d", &N, &M);
int arr[N][N], direction=0, row=0, column=0, length=N, test=1, time=0;
for(int j=0;j<N*N;j++) {
arr[row][column]=j+1;
test++;
if(M==1)
switch(direction) {
case 0:
column++;
break;
case 1:
row++;
break;
case 2:
column--;
break;
case 3:
row--;
break;
}
else if(M==2)
switch(direction) {
case 0:
row++;
break;
case 1:
column++;
break;
case 2:
row--;
break;
case 3:
column--;
break;
}
if(test==length) {
direction++;
direction%=4;
time++;
test=1;
if((time==3 && length==N) || (time==2 && length!=N)) {
length--;
time=0;
}
}
}
for(row=0;row<N;row++) {
printf("%d", arr[row][0]);
for(column=1;column<N;column++)
printf("%5d", arr[row][column]);
printf("\n");
}
printf("\n");
}
return 0;
}
```
### [a524. 手機之謎](https://zerojudge.tw/ShowProblem?problemid=a524)
**連結題目：[a981. 求和問題](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a981-%E6%B1%82%E5%92%8C%E5%95%8F%E9%A1%8C)**
**解題思路**
根據題意，本題希望我們列舉出從1到n的連續正整數集合可能的排列情形。因為我們必須排除已經輸出的情況，列舉出所有的可能性，因此我們採用[遞迴](https://medium.com/appworks-school/%E9%80%B2%E5%85%A5%E9%81%9E%E8%BF%B4-recursion-%E7%9A%84%E4%B8%96%E7%95%8C-%E4%B8%80-59fa4b394ef6)來解決這題。具體的想法是從n開始檢查，若該數字未被輸出過則將其輸出並加以後標註，直到組成1個長度為n的陣列後輸出結果並返回，藉由遞迴走過所有可能性。
:::info
**注意事項**
[遞迴](https://medium.com/appworks-school/%E9%80%B2%E5%85%A5%E9%81%9E%E8%BF%B4-recursion-%E7%9A%84%E4%B8%96%E7%95%8C-%E4%B8%80-59fa4b394ef6)是一種基本的程式運用，概念是先宣告一個函式，藉由在函式內呼叫函式本身，形成一個可以不斷重複執行的循環。作為一種重複執行的方式，遞迴常會被和迴圈比較，但遞迴因為會返回距離最近的「節點」，可以完成具有「分支」的討論，並進一步運用在[深度優先演算法(DFS)](https://dotblogs.com.tw/ilikedogs/2020/03/23/151856)上。因此，希望大家在熟練條件句與迴圈的運用後，可以開始學習遞迴!
:::
**程式碼**
```C==
#include <stdio.h>
int n, step[9], check[9]={};
void dfs(int now) {
if(now==n+1) { /*若已經走過n個數字，代表已經完成一種情況的討論，輸出後返回*/
for(int i=1;i<=n;i++)
printf("%d", step[i]);
printf("\n");
return;
}
for(int i=n;i>0;i--) /*從n開始檢查*/
if(check[i]==0) { /*若該數還未走過*/
step[now]=i; /*將陣列當下的項設為該數*/
check[i]=1; /*將該數標記為走過*/
dfs(now+1); /*遞迴*/
check[i]=0; /*遞迴完是新的情況討論，須將該數是否走過的標記歸零*/
}
}
int main() {
while(scanf("%d", &n)!=EOF)
dfs(1);
return 0;
}
```
### [a647. 投資專家](https://zerojudge.tw/ShowProblem?problemid=a647)
**解題思路**
由題意可知本題測資會有n、m、p三種數字。其中n代表測資數量，m代表當時買進藝術品的成本，p代表該藝術品現在的價值。我們必須計算從m到p的獲利率，並根據獲利率的數值決定是否出售。因此，只要用p/m-1計算出獲利率，再根據其數值輸出相對應的數值即可。
:::info
**注意事項**
感謝k963852741大的解題報告!
可能很多人的獲利率會在第三筆測資出錯，這是因為所謂「精度」的問題。當進行除法運算，商數的位數超出其資料型態所能儲存的最大位數時，會將其後的數字無條件捨去。然而本題要求四捨五入，因此當無條件捨去與四捨五入所得數值存在誤差時就會WA。如0.249999...這樣後面為9循環的小數，在數學上應被判讀為0.25，但若是變數的資料型態只能存到小數點後第二位，會自動從小數點第二位無條件捨去而被儲存為0.24，進而產生誤差。
對此，本程式碼採用的解法是，根據獲利率的正負加減一值極小的小數如0.0001，使其在不影響大部分測資獲利率數值的情況下，能在獲利率是後面為9循環的小數時強制進位，以確保四捨五入的正確性。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
for(int i=0;i<n;i++) {
int m, p;
scanf("%d %d", &m, &p);
float x=(((float)p/(float)m-1)*100);
if(x>=0)
x+=+0.00001;
else
x-=+0.00001;
char c='%';
printf("%.2f%c ", x, c);
if(x>=10.00 || x<=-7.00)
printf("dispose\n");
else
printf("keep\n");
}
return 0;
}
```
### [a693. 吞食天地](https://zerojudge.tw/ShowProblem?problemid=a693)
**連結題目：[a694. 吞食天地二](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a694-%E5%90%9E%E9%A3%9F%E5%A4%A9%E5%9C%B0%E4%BA%8C)**
**解題思路**
本題會有多組測資，我們必須找出輸入的數列中，第l項到第r項之間的和。
可能有些人會想用迴圈從第i項到第r項逐項累加，但從題目的輸入說明可知，本題測資最多達100000筆，每筆測資的食物的數量最多達100000個，如果用迴圈運算的話很可能超時。因此，在這裡要介紹一個新的概念:[前綴和 (preflix sum)](https://cp.wiwiho.me/prefix-sum/)。
前綴和是指數列在此項以前(含)所有元素的總和，比如說前綴和n就是數列從第一項加到第n項的和。由此可知，數列第l項到第r項之間的和，其實就是前綴和r與前綴和l-1的差。由於前綴和的計算可以在讀取數列時候一併完成，在讀取到l和r的數值後只需把兩者的前綴和相減，運算複雜度及所需時間比用迴圈逐項累加要少很多，就可以順利避免超時的問題了!
:::info
**注意事項**
在上面的解題思路有提到，使用迴圈累加的運算時間較前綴和相減長。雖然這是很直觀的想法，但背後其實牽涉到[時間複雜度](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-%E5%BE%9E%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6%E8%AA%8D%E8%AD%98%E5%B8%B8%E8%A6%8B%E6%BC%94%E7%AE%97%E6%B3%95-%E4%B8%80-b46fece65ba5)的概念。考量到對於進階的題目，或甚至是程式競賽來說，縮短程式的運行時間是很重要的，建議程式基礎較強的人可以參考看看。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int n, m;
while(scanf("%d%d", &n, &m)!=EOF) {
int food[n], sum[n];
/*本題若直接用迴圈計算兩數間的的飽足感數，會因數字間距過大而超時，因此需用前綴和的概念解題。
在讀取陣列時先得出前綴和的陣列，將兩前綴和相減即得算兩排間的飽足感數*/
for(int i=0;i<n;i++) {
scanf("%d", &food[i]);
sum[i+1]=sum[i]+food[i];
}
for(int i=0;i<m;i++) {
int l, r;
scanf("%d%d", &l ,&r);
printf("%d\n", sum[r]-sum[l-1]);
}
}
return 0;
}
```
### [a694. 吞食天地二](https://zerojudge.tw/ShowProblem?problemid=a694)
**連結題目：[a693. 吞食天地](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a693-%E5%90%9E%E9%A3%9F%E5%A4%A9%E5%9C%B0)**
**解題思路**
本題會有多組測資，我們必須找出輸入的數列中，第(x1,y1)項到第(x2,y2)項之間的和。
可能有些人會想用雙層迴圈從第(x1,y1)項到第(x2,y2)項逐項累加，但從題目的輸入說明可知，本題測資最多達100000筆，每筆測資的食物的數量最多達500x500個，如果用雙層迴圈運算的話很可能超時。因此，在這裡要介紹一個新的概念:[前綴和 (preflix sum)](https://cp.wiwiho.me/prefix-sum/)。
前綴和是指數列在此項以前(含)所有元素的總和，比如說前綴和n就是數列從第一項加到第n項的和。由此可知，數列第y1項到第y2項之間的和，其實就是前綴和y2與前綴和y1-1的差。據此，我們可以將二維陣列分行做前綴和，運算複雜度及所需時間比用迴圈逐項累加要少很多，就可以順利避免超時的問題了!
:::info
**注意事項**
在上面的解題思路有提到，使用迴圈累加的運算時間較前綴和相減長。雖然這是很直觀的想法，但背後其實牽涉到[時間複雜度](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-%E5%BE%9E%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6%E8%AA%8D%E8%AD%98%E5%B8%B8%E8%A6%8B%E6%BC%94%E7%AE%97%E6%B3%95-%E4%B8%80-b46fece65ba5)的概念。考量到對於進階的題目，或甚至是程式競賽來說，縮短程式的運行時間是很重要的，建議程式基礎較強的人可以參考看看。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int n, m;
while(scanf("%d%d", &n, &m)!=EOF) {
int food[n][n], sum[n+1][n+1];
for(int row=0;row<n+1;row++)
for(int column=0;column<n+1;column++)
sum[row][column]=0;
for(int row=0;row<n;row++)
for(int column=0;column<n;column++) {
scanf("%d", &food[row][column]);
sum[row+1][column+1]=sum[row+1][column]+food[row][column];
}
for(int i=0;i<m;i++) {
int x1, y1, x2, y2, output=0;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
for(int row=x1;row<=x2;row++)
output+=sum[row][y2]-sum[row][y1-1];
printf("%d\n", output);
}
}
return 0;
}
```
### [a738. 最大公约数](https://zerojudge.tw/ShowProblem?problemid=a738)
除了有多筆測資直到EOF結束以外，本題的概念與[a024](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a024%E6%9C%80%E5%A4%A7%E5%85%AC%E5%9B%A0%E6%95%B8GCD)完全相同，可以點擊藍色字體的連結參考!
**程式碼**
```C==
#include <stdio.h>
int main() {
int a, b, big, small;
while(scanf("%d%d", &a, &b)!=EOF) {
if(a>b) {
big=a;
small=b;
}
else {
big=b;
small=a;
}
while(small!=0) {
int temp=big;
big=small;
small=temp%small;
}
printf("%d\n", big);
}
return 0;
}
```
### [a740. 质因数之和](https://zerojudge.tw/ShowProblem?problemid=a740)
**連結題目：[a010. 因數分解](https://noah-0831.github.io/a010-%E5%9B%A0%E6%95%B8%E5%88%86%E8%A7%A3/)**
**解題思路**
本題希望我們能得出輸入數字的質因數之和，因此我們必須對輸入數字做質因數分解。具體的做法是從最小的質數開始檢查，當遇到該數的因數時，就把該數除以此質數得到商數，然後再重複上述動作，直到確定商數已經不能再被此質數整除為止。重複上述動作直到商數剩下一為止，即完成因數分解。
:::info
**注意事項**
注意本題要求的不是「因數和」，而是「質因數和」，因此1不能計入!
:::
**程式碼**
```C==
#include <stdio.h>
#include <math.h>
int main() {
long long x;
while(scanf("%lld", &x)!=EOF) {
long long sum=0, r;
for(int i=2;i<=sqrt(x);i++) {
r=x%i;
while(r==0) {
sum+=i;
x/=i;
r=x%i;
}
}
if(x!=1) /*若x不等於1，代表x本身為質數*/
sum+=x;
printf("%lld\n", sum);
}
return 0;
}
```
### [a746. 画蛇添足](https://zerojudge.tw/ShowProblem?problemid=a746)
**解題思路**
在此先感謝M_SQRT大幫忙!
本題希望我們可以將二維陣列的外框分別用-和|表示，內部的點若特別被提到則用*表示並連線，否則輸出空白。
首先，我們可以宣告一大小為[N+2][N+2]的二維陣列，並將column=0和column=N+1的點設值為|，將row=0和row=N+1的點設值為-，而內部的點則設為空白。
再來，既然題目保證前一個點和後一個點所確定的線段一定平行於圍欄的一邊，代表前後兩點一定擁有相同的x座標或y座標。因此，我們可以根據前後兩點相同的是x座標還y座標將情況分為鉛直線和水平線兩類，將兩點所連成的線段上的點都設為*。
最後，在將二為陣列的點設值完成後，再輸出二維陣列即可。
:::info
**注意事項**
在二維陣列的表示法中，前面的參數代表行數(y)，後面代表列數(x)。而在數學的坐標系中，前面的參數代表的是x，後面代表y。兩者恰好順序相反，在寫程式的時候別搞錯了!
:::
**程式碼**
```C==
#include <stdio.h>
int main () {
int n, m;
while(scanf("%d%d", &n, &m)!=EOF) {
char matrix[n+2][n+2]; /*建立包含外框的初始二維陣列*/
for(int row=0;row<n+2;row++)
for(int column=0;column<n+2;column++)
matrix[column][row]=' ';
for(int i=0;i<n+2;i++) {
matrix[0][i]='|';
matrix[n+1][i]='|';
}
for(int i=0;i<n+2;i++) {
matrix[i][0]='-';
matrix[i][n+1]='-';
}
int x[m], y[m]; /*讀取輸入的點，兩點連成一線*/
for(int i=0;i<m;i++)
scanf("%d%d", &x[i], &y[i]);
for(int i=0;i<m-1;i++) {
if(x[i]==x[i+1]) {
int start=(y[i]<y[i+1]) ? y[i] : y[i+1];
int end=(y[i]<y[i+1]) ? y[i+1] : y[i];
for(int j=start;j<=end;j++)
matrix[j][x[i]]='*';
}
else if(y[i]==y[i+1]) {
int start=(x[i]<x[i+1]) ? x[i] : x[i+1];
int end=(x[i]<x[i+1]) ? x[i+1] : x[i];
for(int j=start;j<=end;j++)
matrix[y[i]][j]='*';
}
}
for(int row=0;row<n+2;row++) { /*輸出二維陣列*/
for(int column=0;column<n+2;column++)
printf("%c", matrix[column][row]);
printf("\n");
}
}
return 0;
}
```
### [a799. 正值國](https://zerojudge.tw/ShowProblem?problemid=a799)
**解題思路**
將題目輸入的測資取絕對值後輸出。
:::info
**注意事項**
本程式碼使用了abs()函式表示絕對值寫法。由於abs()函式並非標準函式庫裡的函式，使用前必須引用<math.h>函式庫。
:::
**程式碼**
```C==
#include <stdio.h>
#include <math.h>
int main() {
int N;
scanf("%d", &N);
printf("%d\n", abs(N));
return 0;
}
```
### [a915. 二维点排序](https://zerojudge.tw/ShowProblem?problemid=a915)
**連結題目：[a225. 明明愛排列](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a225-%E6%98%8E%E6%98%8E%E6%84%9B%E6%8E%92%E5%88%97)**
**解題思路**
根據題意，我們必須將輸入的點座標按x座標的大小，由小到大排列。而若是x座標的大小相同，再按y座標的大小由大到小排列。
[為數字排序的方法](https://totoroliu.medium.com/%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-sorting-algorithm-dfd8af673f3a)有很多種，而本題採用[氣泡排序法](https://medium.com/@oturngo/study-note-01-%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95-bubble-sort-ee534b6f91eb)，具體的作法是從第一個元素開始往下檢查，如果兩者的相對順序錯誤，就將兩者的位置對調，接著重新檢查，直到最後一個元素的位置也被確認正確無誤為止。
以由小到大排列為例，我們會從第二個數字開始檢查，若它比前一個數字，也就是第一個數字還大的話，代表檢查到目前為止，它在數列中的位置是正確的，我們就不會移動他的位置，繼續檢查下去 ; 反之，如果它比後一個數字還小，代表它在數列中的位置不符合題目希望由小到大排序的要求，因此我們會將它與前一個數字的位置對調，然後重新檢查。
:::info
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用[EOF寫法](
https://www.796t.com/content/1544817994.html)判斷程式執行的條件。
:::
**程式碼**
```C==
#include <stdio.h>
int main() {
int n;
while(scanf("%d", &n)!=EOF) {
int x[n], y[n];
for(int i=0;i<n;i++)
scanf("%d %d", &x[i], &y[i]);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(x[i]>x[j] || (x[i]==x[j] && y[i]>y[j])) {
int temp=x[i];
x[i]=x[j];
x[j]=temp;
temp=y[i];
y[i]=y[j];
y[j]=temp;
}
for(int i=0;i<n;i++)
printf("%d %d\n", x[i], y[i]);
}
return 0;
}
```
### [a981. 求和問題](https://zerojudge.tw/ShowProblem?problemid=a981)
**連結題目：[a524. 手機之謎](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a524-%E6%89%8B%E6%A9%9F%E4%B9%8B%E8%AC%8E)**
**解題思路**
根據題意，本題希望我們列舉出總和恰好為m的所有可能。因為我們必須排除已經輸出的情況，列舉出所有的可能性，因此我們採用遞迴來解決這題。具體的想法是從第一項數字開始，決定是否要選取該數字，直到所有數字都跑完為止，若總和為m則輸出組合後返回，若否則直接返回。
:::info
**注意事項**
從遞迴會運算每種可能性的特質可知其所需的運算時間較久，因此我們常會進行「剪枝」，也就是終止討論確定不可能的情況，直接返回並進入下一次討論。以本程式碼來說，由於題目希望我們輸出總合為m的情況，因此若是還沒討論完總和就已經大於m，就可以直接返回並進行下一次遞迴。
:::
**程式碼**
```C==
#include <stdio.h>
int n, m, arr[31], step[31]={}, check[31]={}, no_solution=1;
void dfs(int now, int sum) {
if(now==n) {
if(sum==m) {
int test=0;
for(int i=0;i<n;i++) {
if(check[i]!=0) {
if(test==1)
printf(" ");
printf("%d", arr[i]);
test=1;
}
}
printf("\n");
no_solution=0;
}
return;
}
if(sum>m) /*若sum已經大於m，為不合法的可能，可以直接返回*/
return;
check[now]=1; /*選取該數字*/
dfs(now+1, sum+arr[now]); /*將sum加上該數字後進入下一項的討論*/
check[now]=0; /*不選該數字*/
dfs(now+1, sum); /*直接進入下一項的討論*/
}
int main() {
while(scanf("%d%d", &n, &m)!=EOF) {
int sum=0;
for(int i=0;i<n;i++) {
scanf("%d", &arr[i]);
sum+=arr[i];
}
if(sum<m) {
printf("-1\n");
continue;
}
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
if(arr[i]>arr[j]) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
dfs(0, 0);
if(no_solution==1)
printf("-1\n");
no_solution=1;
}
return 0;
}
```
Sign in with Wallet
Connect another wallet