第五章 基礎資料型別
5.1 整數型態
5.1.1 無號整數
d984. 棄保效應
題目大意：給你三個整數代表 A, B, C 三個候選人的得票數 a, b, c，如果得票數最少的候選人的票數全部給得票數第二高的候選人的話，最後會是誰當選？
候選人 A 要贏得選舉的條件如下：
a > b + c，這樣不管有沒有棄保效應，A 一定會當選。(a>b+c)
如果 c > a > b，那麼就可以運作「棄 B 保 A」，此時若 a + b > c，A 就會當選。(c>a && a>b && a+b>c)
如果 b > a > c，那麼就可以運作「棄 C 保 A」，此時若 a + c > b，A 就會當選。(b>a && a>c && a+c>b)
再次提醒，數學上的 c > a > b 寫成程式時要寫成 c > a && a > b 而不是 c > a > b。
把以上三個條件用「或」運算子連接起來，就是 A 當選的條件了：
a>b+c || c>a && a>b && a+b>c || b>a && a>c && a+c>b
(只要其中之一成立A即可當選)
B 當選的條件也可以類推，寫成程式如下：
//d984. 棄保效應 by snail
#include <iostream>
using namespace std;
int main () {
int a, b, c;
while (cin >> a >> b >> c) {
if (a>b+c || c>a && a>b && a+b>c || b>a && a>c && a+c>b)
cout << "A\n"; //↑棄B保A ↑棄C保A
else if (b>a+c || c>b && b>a && b+a>c || a>b && b>c && b+c>a)
cout << "B\n"; //↑棄A保B ↑棄C保B
else
cout << "C\n";
}
}
可是當你把這個程式上傳時，你卻得了個「WA (line:49)」。基本上這個程式的邏輯上並沒有錯，問題出在 int 的範圍上。
雖然題目說 a, b, c 的值會 ≤ 2147483647，基本上它們並沒有超過 int 的範圍，可是當其中的兩數相加時，其結果就有可能超出範圍了。這一題的第 49 筆測試資料是
2147483647 2147483646 2
當我們在判斷 a > b + c 時，其中的 b + c 為 2147483646 + 2，所得的結果為 2147483648，因為已經超出 int 的範圍了，所以它變成了 -2147483648，導致 a > b + c 本來應該是「false」的，現在卻變成了「true」了，本來應該是 B 當選的，結果就輸出 A 了。
要解決這個問題，我們需要一個可以處理比 2147483647 更大的值的資料型態。
2147483647 = 231 - 1，轉成二進位是 1111111111111111111111111111111，也就是 31 個 1。事實上 int 資料型態在電腦裡佔用 4 個位元組 (Bytes)，也就是 32 個位元 (bits)，理論上它的最大值應該是 32 個 1，也就是 232 - 1，但是系統留了最左邊的那的位元來表示正負號，這個位元稱為「符號位元」(sign bit)，0 表示這個數字為正，1 則表示這個數字為負。
但是如果你的程式所處理的資料沒有負數，這個符號位元就不需要了，我們可以把全部的 32 個位元全部用來表示數字的大小，如此最大值就變成了 232 - 1了。要宣告這樣的變數，只要在 int 之前加上 unsigned (無號) 這個關鍵字就可以了。
也就是說，上面的程式只要把
int a, b, c;
這一行改成
unsigned int a, b, c;
就可以 AC 了。
a007. 判斷質數
題目大意：給你一個 ≧ 2 的整數 x，判斷 x 是不是質數。
質數的定義是：除了 1 和本身以外，沒有任何其他因數的整數。要判斷 x 是否質數，我們可以先用 2 去除，看看是否可以整除，如果不能整除的話，再用 3 去除除看，如果還不能整除，再用 4 去除除看……，以此類推，一直找到第一個整數為止。用這個方式可以找到 ≧ 2 的最小因數，如果這個因數就 = x，那麼 x 就是質數了。
#include <iostream>
using namespace std;
int main () {
int x, d;
while (cin >> x) {
d = 2;
while (x % d)
d++;
if (d == x)
cout << "質數\n";
else
cout << "非質數\n";
}
}
這個程式雖然可以判斷 x 是否為質數，但是上傳以後卻得了個「TLE (1s)」，意思是你的程式沒有辦法在所限定的 1 秒內跑出正確解答來。為什麼呢？
題目中說明 x 的最大值是 2147483647，我們就用這個值來輸入，在筆者的電腦上執行了大約 8.5 秒才輸出它是「質數」，但是題目的時間限制只有 1 秒。
由於 2147483647 是個質數，根據上面的程式，d 從 2 開始試著去除 x，迴圈要一直執行到 d = 2147483647 時才能整除 x，這時已經執行了 2147483646 次的除法，時間也早就超過了題目的限制。
其實，一個整數的因數是成對存在的。如果 d 是 x 的因數，那麼 x 也必有另一個因數為 x / d。而 d, x / d 這兩個因數一定有一個會 ≤。因此我們如果在 ≤ 的整數中如果找不到 x 的因數，那麼 x 就是質數。
可是我們到目前為止還沒有學到如何去開根號，那這題要如何處理？開根號的函數會稍後的章節中提到，到時候這個題目也會再拿出來討論，但是這題即使沒有使用開根號的函數也仍然可以完成。
雖然我們目前沒有辦法去判斷 d ≤，但是如果我們把這個關係式的兩邊都平方，不就成了 d2 ≤ x。根據這個關係式，我們把迴圈部份改寫如下：
d = 2;
while (x % d && d*d <= x)
d++;
如此一來，跳出迴圈的條件有兩個：d 可以整除 x，或 d > ，只要其中一個情況出現了，迴圈便會中止。以 x = 2147483647 為例，當 d = 46341 時，d*d 就會 > x，迴圈也就會中止。由於迴圈最多只執行 4 萬多次，而不是原先的 21 億次，程式會變得很快！
但是接下來要判斷 x 是否是質數時，就不能再用 (d == x) 了，因為跳出迴圈時，d = 46341，而不是 2147483647。這時候可以改用 (d*d > x) 來作為判斷質數的條件。整個程式修改後如下：
//a007. 判斷質數by Snail
#include <iostream>
using namespace std;
int main () {
int x, d;
while (cin >> x) {
d = 2;
while (x % d && d*d <= x)
d++;
if (d*d > x)
cout << "質數\n";
else
cout << "非質數\n";
}
}
當我們執行這個程式並輸入 2147483647 時，發現程式不但沒有變快，甚至答案也變成了「非質數」。
問題就發生在當所輸入的 x 是 int 的最大值時，只要 > x 的值就會溢位。觀察下表，當 d = 46340 時 d*d 仍小於 x 的 2147483647；可是當 d = 46341 時，d*d 就爆掉了而變成一個負數，而跳出迴圈的條件是 d*d > x，因此這個條件永遠不會成立，迴圈也不會在該中止的時候中止。
解決的辦法是，我們需要一個可以容納 2147488281 這個數字的資料型態。int 不行，但是 unsigned int (無號整數)可以。所以你只要把上列程式的 int 加上 unsigned 就可以 AC 了。
另外，我們可以利用 for 迴圈把 d 的變化範圍集中在一行，讓程式較具有可讀性：
//a007. 判斷質數by Snail
#include <iostream>
using namespace std;
int main () {
unsigned int x, d; //d(enominator)--除數
while (cin >> x) {
for (d=2; d*d<=x; d++) //d: 2 → √x
if (x % d == 0) //若 d 可整除 x
break; // 跳出迴圈
if (d*d > x) //若d > √x
cout << "質數\n";
else
cout << "非質數\n";
}
}
整數和無號整數在作運算時，如果沒有負數還好，一但有負數就會出現問題，例如以下範例：
int a=-12;
unsigned int b=12,c=12;
cout << a*b+c << endl;
正確結果應該是-132
但程式跑出的結果然是4294967164
這是由於進行運算時(unsigned int)*(signed int)結果會是(usingned int)，於是形成一個不容易察覺的singned、unsigned比較。由於程式在字面上看起來吻合撰寫者的邏輯，所以這個錯誤會非常難抓。如果將 b 和 c 強制轉換成signed的話就不會有這種問題了!
另外，有關於整數和無號整數的差別，有另一段程式碼可以解釋:
unsigned pos = 1024;
int neg = -5;
if (pos > neg) {
cout << pos << " is bigger.\n";
} else {
cout << neg << " is bigger.\n";
}
程式會告訴你-5比較大，因為當 signed 和 unsigned 一同做運算時，signed 會自動轉型成 unsigned，在 32 bit 機器上 -5 會變成 4294967291。
所以如果你不太會用unsigned int 時，或是你怕會搞錯，請你就用long long吧!以下會介紹
5.1.2 Long Long 整數
b077. C. 不公平的人，是誰？
題目大意：輸入兩個正整數 M, N，如果 M > N 就輸出 "Fair"，否則輸出 "Unfair"。
這題看起來相當簡單，但是如果你仔細看看 M, N 的範圍，最大到 4611686018427387904，也就是 262。這個值遠大於 int 的上限 2147483647，也就是 231 - 1。就算是上一節中所教的 unsigned int 的 232 -1 也還是不夠大。
其實在 C++ 裡的整數型態 int 除了可以用 signed, unsigned 來指定要不要正負號以外，還可以用 short, long, 及 long long 來指定變數的大小。因此，整個整數型態的名稱分成三個部分，我們稱之為「符號部」「大小部」及「型態部」，詳如下表：
由於符號部有兩種選擇、大小部有三種選擇，組合起來之後，C++ 的 int 一共有六種變化如下：
signed short int
signed long int
signed long long int
unsigned short int
unsigned long int
unsigned long long int
上面的 6 個型態名稱是完整的寫法，看起來有點冗長。於是 C++ 也把比較常用的選項設為可以省略的內定值。
「符號部」的內定值為 signed，因此如果符號部從缺時，系統便會視為有號整數。
「大小部」的內定值則是依硬體、作業系統、及編譯器而有所不同。筆者很久以前在 DOS 上用 Borland 公司的 Turbo C++ 寫程式時，這個部份如果省略的話，系統會視為 short，所宣告出來的變數只有 2 個位元組。更慘的是，在那個環境中，系統還不提供 long long 這個資料型態呢，遇到像 b077 這樣的題目就麻煩大了！
現在因為一般的電腦硬體、作業系統至少都是 32 位元，處理 32 位元的整數的效率和處理 16 位元整數的效率是一樣的，所以大多數的編譯器，包括 VC++ 2010 在內，如果你不指定大小的話，系統則內定為 long (4 個位元組)，也就是 32 個位元。
至於「型態部」的 int，是當然的內定值，所有的情況它都可以省略，唯一的條件是其他兩個部份不可以同時都省略。(這是廢話，三個部份都省略不就什麼都沒有了！)
根據以上說明，其實我們在第一到四章中所習慣的 int 型態，完整的三部份寫法是「signed long int」，只是我們把「signed」及「long」省略掉罷了。事實上，它一共有「int」、「long」、「signed」、「long int」、「signed int」、「signed long」、「signed long int」等 7 種寫法，但它們所代表的意義完全相同！
綜上所述，我們把這六種整數型態的特質整理如下表：
在「附錄 A 基礎資料型別」中列出了 C++ 語言所定義的型別，你可以在其中找到以上的六種資料型態。
(附註:263 - 1=9223372036854775807,而264 - 1=18446744073709551615)
對本題來說，long long 這個資料型別最大值為 263 - 1，足以處理這個題目的資料最大值 262。你可以把 M, N 宣告如下，再根據題意寫出程式就可以 AC 了。
long long m, n;
d127. 二、牧场面积
題目大意：給你矩形的周長，求最大面積。所給的周長一定為偶數，所圍的邊長必需是整數。
如果題目所給的周長保證是 4 的倍數，那麼這題就比較簡單了。但是題目只保證所給的周長是偶數，如果不是 4 的倍數的話，那麼這矩形的長就會比寬大 1。這個就有點小麻煩了，不過如果你夠聰明的話，也是可以用一個式子求出牧場面積的。
這個題目其實不難，之所以放在這一章才教，是因為它所給的周長會大於 4294967295，必需用 long long 才能 AC。
c005. 環保獎金
這個題目是從 UVa 的題庫出來的。它原來的總金總和是不會超出 int 的範圍的，但是 ZeroJudge 上的測試資料卻會使獎金總和超出 int 的上限，所以用來計算總和的那個變數要改用 long long。
浮點數就是帶有小數的數字。
d051. 糟糕，我發燒了！
題目大意：輸入華氏溫度 f，換算成攝氏溫度後輸出。攝氏 = ( 華氏 - 32 ) * 5 / 9 ，直接按題意寫成程式如下：
#include <iostream>
using namespace std;
int main (){
int f;
cin >> f;
cout <<(f-32)*5/9;
}
但是，" / "除完之後得到的是商，是一個整數，不是我們想要的答案。
那要讓它除出來的結果有小數要怎麼辦呢?則在這個運算式裡必須帶有浮點數。
所以我們可以把"5"改成 "5.0"或是直接打"5."就可以了。
#include <iostream>
using namespace std;
int main (){
int f;
cin >> f;
cout << (f-32)*5./9;
}
寫成這樣就差不多完成了，可是題目還有一個要求，只要取到小數以下第3位。
這時就要在cout你的答案之前，打上 << fixed << setprecision(3) 這樣他就會輸出至小數點後第三位。
要用 fixed setprecision() 之前，必須先 #include<iomanip>。
這樣這題就完成了：
#include <iostream>
#include <iomanip>
using namespace std;
int main (){
int f;
cin >> f;
cout << fixed << setprecision(3) << (f-32)*5./9;
}
d055. 11437 - Triangle Fun
之前學到的數字的資料型別，像 int 或 long long ，都是"整數"的資料型別，那帶小數點的數字呢?
帶有小數的資料型別(浮點數)只有兩種：
其實，PQR = ABC / 7，至於 ABC 的面積可以利用題目下面的提示所提供的公式去求，這樣就可以得到答案。但是這裡有一個小小的陷阱：
C++ 內建的 abs() 函數只能用來求整數的絕對值，如果你用浮點數代進去，它會先把小數部份無條件捨去並轉成整數型態後再取絕對值。
但是在 <cmath> 這個標頭檔中，包含了三個 abs() 的重載：
(待補)
x 的絕對值：abs(x)
#include <cmath>
(現在已改成#include<stdlib>)
(補充:如果學過副程式，你也可以自己寫，寫法如下:
int abs(int a){
if(a<0)return -a;
return a;
}
b227. F. 優惠方案Ⅱ
用c++進行開根號及平方
再一些程式語言中(ex.Visual Basic)，如果要求一些數的二次方或三次方，可以直接用上引號(ex.2^2=4)表示，但很可惜的是c++中並沒有這種功能，
這種時候，如果我們要對一個數二次方或三次方，除了使用n*n*n之外，還可以用cmath標頭檔裡的pow函數，格式如下:
22的5次方=22^5=pow(22,5)
22的0.5次方=22^0.5=pow(22,0.5)=sqrt(22)
a006. 一元二次方程式
//a006: 一元二次方程式by Snail
#include <iostream>
#include <cmath>
using namespace std;
int main () {
int a, b, c, d;
while (cin >> a >> b >> c) {
d = b*b - 4*a*c; //d(iscriminator)--判別式
if (d < 0)
cout << "No real root\n";
else if (d == 0)
cout << "Two same roots x=" << -b/(2*a) << endl;
else {
d = ( int) sqrt ((double)d);
cout << "Two different roots x1=" << (-b+d)/(2*a)
<< " , x2=" << (-b-d)/(2*a) << endl;
}
}
}
b004: 繩子上吃草的牛
//b004. 繩子上吃草的牛by Snail
#include <iostream>
#include <iomanip> //for setprecision()
#include <cmath> //for sqrt(), acos()
using namespace std;
int main () {
double D, L, r1, r2, area, PI=acos(-1.);
while (cin >> D >> L) {
r1 = L / 2; //長軸/2
r2 = sqrt (L*L - D*D) / 2; //短軸/2
area = PI * r1 * r2; //area--面積
cout << fixed << setprecision(3) << area << endl;
}
}
附註:橢圓形面積==PI*半長軸*半短軸==PI*a*b
(圖片來源:http://tw.knowledge.yahoo.com/question/question?qid=1509062705725)
//a020: 身分證檢驗 by Snail
#include <iostream>
using namespace std;
int main () {
int id, cs, i;
char c;
while (cin >> c) {
if (c == 'I')
cs = 34;
else if (c == 'O')
cs = 35;
else if (c == 'W')
cs = 32;
else if (c == 'Z')
cs = 33;
else {
cs = c - 55;
if (c > 'I')
cs--;
if (c > 'O')
cs--;
if (c > 'W')
cs--;
}
cs = cs%10 * 9 + cs / 10;
cin >> id;
cs += id % 10;
id /= 10;
for (i=1; i<=8; i++) {
cs += id%10 * i;
id /= 10;
}
if (cs % 10)
cout << "fake\n";
else
cout << "real\n";
}
}
c007: TeX Quotes
//c007. TeX Quotes.cpp (by Snail)
#include <iostream>
using namespace std;
int main () {
int n = 1;
char c;
while (cin.get(c)) {
if (c == '"')
if (n++ % 2)
cout << "``";
else
cout << "''";
else
cout << c;
}
}
d658. 11636 - Hello World!
a024. 最大公因數(GCD)