c184. 盈虧互補
n 的真因數：除了 n 本身以外的所有因數，包含 1。
友好數：如果 n 真因數和為 m，m 的真因數和為 n，則 n、m 互為「友好數」。
題目：給定 n，求 n 的友好數。若 n 的友好數為 n 本身，請輸出「=n」，若 n 沒有友好數，請輸出「0」。
這題可以用以下的程式碼來 AC。
//2007jfB. 友好數 by Snail
#include <iostream>
using namespace std;
int main () {
int n, n1, m, f;
while (cin >> n, n) {
m = 1; //加入因數 1
for (f=2; f*f<n; f++) //f(actor)--因數
if (n % f == 0) //若 f 為 n 的因數
m += f + n/f; // 加入 f 及 f/n
if (f*f == n) //若 n 為完全平方數
m += f; // 加入平方根
if (m == n) //若 n 的友好數為自身
cout << '=' << m << endl; // 加一個「=」
else {
n1 = 1; //求 m 的真因數和 n1
for (f=2; f*f<m; f++)
if (m % f == 0)
n1 += f + m/f;
if (f*f == m)
n1 += f;
if (n1 == n) //若 m 的真因數和為 n
cout << m << endl; // m 即是 n 的友好數
else //否則
cout << "0\n"; // n 沒有友好數
}
}
}
從上面的程式中，我們先求 n 的真因數和 m，再求 m 的真因數和 n1，求真因數和的動作做了兩次，相同的程式碼也寫了兩次。這樣的寫法除了浪費記憶體外，在軟體工程上也有它的問題，因為它會造成維護上的困擾。將來如果求真因數和的程式需要修改，那麼我們得修改兩處，萬一其中一處遺漏了，就會造成程式的錯誤。
因此，像這樣重覆使用的程式碼，應讓有一個機制讓它只寫一次就好，這個機制叫作「函數」。我們把上面的程式碼用「函數」改寫如下：
//2007jfB. 友好數 by Snail
#include <iostream>
using namespace std;
void sof () { //s(um) o(f) f(actors)
m = 1; //加入因數 1
for (f=2; f*f<n; f++) //f(actor)--因數
if (n % f == 0) //若 f 為 n 的因數
m += f + n/f; // 加入f 及 f/n
if (f*f == n) //若 n 為完全平方數
m += f; // 加入平方根
}
int main () {
int n, n1, m, f;
while (cin >> n, n) {
sof(); //呼叫 sof 函數
if (m == n) //若n 的友好數為自身
cout << '=' << m << endl; // 加一個「=」
else {
n1 = 1; //求m 的真因數和 n1
for (f=2; f*f<m; f++)
if (m % f == 0)
n1 += f + m/f;
if (f*f == m)
n1 += f;
if (n1 == n) //若m 的真因數和為 n
cout << m << endl; // m 即是 n 的友好數
else //否則
cout << "0\n"; // n 沒有友好數
}
}
}
在這個程式裡，一共有兩個「函數」(funtcion)：int main () 及 void sof ()。void 所代表的意義我們待會再討論。int main () 是程式的「入口」，程式執行時，會先執行這個「函數」。至於其他的函數，只有在被「呼叫」(call) 時才會執行。如果你寫了一個函數卻不去呼叫它，那麼它就不會被執行，等於是白寫。因此，在 int main () 中有一個呼叫 sof () 函數的陳述式：
sof(); //呼叫 sof 函數
執行到這行時，程式就會先跳到 void sof () 函數去，等 void sof () 裡的程式執行完後再跳回 int main ()。
不過，上面這個程式在編譯時得到以下的錯誤訊息：
1>d:\cpps\cpps\2007jfb. 友好數a.cpp(6) : error C2065: 'm' : 未宣告的識別項
1>d:\cpps\cpps\2007jfb. 友好數a.cpp(7) : error C2065: 'f' : 未宣告的識別項
1>d:\cpps\cpps\2007jfb. 友好數a.cpp(7) : error C2065: 'n' : 未宣告的識別項
在 int main () 的裡面我們定義了 4 個變數。
int n, n1, m, f;
這種定義在函數內部的變數我們稱之為「區域變數」，它的有效範圍僅限於該函數的內部。所以這 4 個變數是 int main () 自己的變數，void sof () 是存取不到的。因此當 void sof () 中使用到 n, m, f 等變數時，便會產生「未宣告的識別項」的錯誤。
你當然也可以在 void sof () 中自己定義這些變數：
void sof () { //s(um) o(f) f(actors)
int n, m, f;
m = 1; //加入因數 1
for (f=2; f*f<n; f++) //f(actor)--因數
if (n % f == 0) //若 f 為 n 的因數
m += f + n/f; // 加入f 及 f/n
if (f*f == n) //若 n 為完全平方數
m += f; // 加入平方根
}
這樣程式雖然通過編譯並執行，但是卻產生的下列的「警告」：
1>d:\cpps\cpps\2007jfb. 友好數a.cpp(8) : warning C4700: 使用了未初始化的區域變數 'n'
1>d:\cpps\cpps\2007jfb. 友好數a.cpp(19) : warning C4700: 使用了未初始化的區域變數 'm'
根據程式的邏輯，在 void sof () 所使用的 n 應該是在 int main () 所輸入的 n。我們另行在 void sof () 所宣告的 n 卻是另一個 n，儘管兩個變數名稱都是 n，但是它們卻是不同的個體。你在 int main () 輸入了 n，但是 void sof () 的 n 卻沒有改變。
要讓 int main () 和 void sof () 共用一個 n，你需要把它定義為「全域變數」，方法是把這個 n 宣告在兩個函數的「外面」：
//2007jfB. 友好數 by Snail
#include <iostream>
using namespace std;
int n, m;
void sof () { //s(um) o(f) f(actors)
int f;
m = 1; //加入因數 1
for (f=2; f*f<n; f++) //f(actor)--因數
if (n % f == 0) //若 f 為 n 的因數
m += f + n/f; // 加入f 及 f/n
if (f*f == n) //若 n 為完全平方數
m += f; // 加入平方根
}
int main () {
int n1, f;
while (cin >> n, n) {
sof(); //呼叫 sof 函數
if (m == n) //若n 的友好數為自身
cout << '=' << m << endl; // 加一個「=」
else {
n1 = 1; //求m 的真因數和 n1
for (f=2; f*f<m; f++)
if (m % f == 0)
n1 += f + m/f;
if (f*f == m)
n1 += f;
if (n1 == n) //若m 的真因數和為 n
cout << m << endl; // m 即是 n 的友好數
else //否則
cout << "0\n"; // n 沒有友好數
}
}
}
記得要同時把函數內的同名區域變數拿掉，否則程式會優先取用區域變數，而不是全域變數。
由於 int main () 和 void sof () 都會用到 n, m，所以這兩個全域變數的宣告要出現在這兩個函數之前，否則還是會出現「未宣告的識別項」的錯誤。同理，由於 int main () 中會去呼叫 sof ()，所以 void sof() 函數也要出現在 int main () 之前。
你可能會好奇，既然 n, m 要宣告為全域變數，為什麼不把 n1 和 f 也一起宣告為全域，這樣程式也比較簡短。基於易於維護的因素，除非真正必要的時候，我們通常會儘量避免全域變數的使用。由於每個函數都可以去修改全域變數的值，有時候甲函數修改了某變數的值，乙函數卻不知道，這就會造成一些錯誤了。在上面的程式中，int main () 輸入了 n 的值，而 void sof () 則需要求這個 n 的真因數和，void sof () 所求得的真因數和 m 也需要在 int main () 中做進一步的判斷與處理，所以這兩個變數一定要宣告成全域變數，其他的變數我們就宣告為區域變數。在這個程式中，即使你把 n, m, n1, f 都宣告為全域變數，程式仍能跑出正確的結果，但是基於培養良好的程式設計習慣，我們還是把 n1 和 f 宣告為區域變數比較好。
經過這番調整之後，這個程式終於可以正確執行了。但是我們當初寫 void sof () 這個函數的目的就是希望可以把相同的兩段程式碼簡化成一段，當我們試圖進一步用 void sof () 來求 m 的真因數和時，卻發現由於變數命名的關係， void sof () 只能用來求 n 的真因數和，沒有辦法用來求 m 的真因數和。為了解決這個問題，我們把 void sof () 所使用的變數名稱修改如下：
int p, q;
void sof () { //s(um) o(f) f(actors)
int f;
q = 1; //加入因數 1
for (f=2; f*f<p; f++) //f(actor)--因數
if (p % f == 0) //若 f 為 n 的因數
q += f + p/f; // 加入f 及 f/n
if (f*f == p) //若 n 為完全平方數
q += f; // 加入平方根
}
也就是說，我們用 p 來取代所有的 n、用 q 來取代所有的 m。然後我們在呼叫 void sof() 之前先把 n 代入 p，求出 p 的真因數和 q 之後，再把 q 代入 m：
p = n; //先把 n 代入 p
sof(); //求 p 的真因數和 q
m = q; //再把 q 代入 m
雖然這樣麻煩一點，但是如此一來，我們就可以用同一個 void sof () 來求 m 的真因數和了：
p = m; //先把 m 代入 p
sof(); //求 p 的真因數和 q
n1 = q; //再把 q 代入 n1
完整程式碼如下：
//2007jfB. 友好數 by Snail
#include <iostream>
using namespace std;
int p, q;
void sof () { //s(um) o(f) f(actors)
int f;
q = 1; //加入因數 1
for (f=2; f*f<p; f++) //f(actor)--因數
if (p % f == 0) //若 f 為 n 的因數
q += f + p/f; // 加入 f 及 f/n
if (f*f == p) //若 n 為完全平方數
q += f; // 加入平方根
}
int main () {
int n, n1, m, f;
while (cin >> n, n) {
p = n; //先把 n 代入 p
sof(); //求 p 的真因數和 q
m = q; //再把 q 代入 m
if (m == n) //若 n 的友好數為自身
cout << '=' << m << endl; // 加一個「=」
else {
p = m; //先把 m 代入 p
sof(); //求 p 的真因數和 q
n1 = q; //再把 q 代入 n1
if (n1 == n) //若 m 的真因數和為 n
cout << m << endl; // m 即是 n 的友好數
else //否則
cout << "0\n"; // n 沒有友好數
}
}
}
d255. 11417 - GCD
這一題，它把題目的要求都寫成程式給你了，你只要複製題目中的程式，再加上變數的宣告、0 尾版的迴圈、及結果的輸出，答案就出來了。
//11417 - GCD (by Snail)
#include <iostream>
using namespace std;
int main () {
int G, N, i, j; //變數的宣告
while (cin >> N, N) { //0 尾版的迴圈
G=0; //複製題目中的程式
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
G+=GCD(i,j);
}
cout << G << endl; //結果的輸出
}
}
但是再仔細看一下程式，其中用了一個 GCD 函數是 C++ 中沒有的。這時候你就得自己為它定義一個 GCD 函數來求最大公因數了。
上一章中我們用 <algorithm> 中的 sort 函數來排序。但是它只能依數值由小到大排序。可是如果遇到特殊條件的排序，Sort 就不知道要如何去排了。
d750. 11321 - Sort! Sort!! and Sort!!!
這題的排序條件很詭異。
//11321 - Sort! Sort!! and Sort!!! (by Snail)
#include <iostream>
#include <algorithm> //for sort
using namespace std;
int m; //cmp 中要用到m
//故宣告為全域
bool cmp (int a, int b) {
if (a%m != b%m) //若餘數不等
return a%m < b%m; // 按餘數排序
if ((a+b)%2) //若一奇一偶
return (a&1) > (b&1); // 奇數在前
if (a%2) //同為奇數
return a > b; // 大在前
return a < b; //否則小在前
}
int main () {
int i, n, a[10000];
while (cin >> n >> m, n) {
for (i=0; i<n; i++)
cin >> a[i];
sort (a, a+n, cmp);
cout << n << ' ' << m << endl;
for (i=0; i<n; i++)
cout << a[i] << endl;
}
cout << "0 0\n";
}
d731. 11039 - Building designing
b250. F. 風鈴
c129. Oil Deposits
本題重點在於,要用整張地圖遞迴下去
但若每次遞迴都建
一張地圖絕對會吃re的
這題的大概做法是:
先從第一個開始搜，一搜到"@"，就往下遞回直到沒有，答案加一，然後記得每找到ㄧ個"@"，都把它換成其他字元(建議不用"#"，因為DEBUG時比較好找到錯誤。