第五章 基礎資料型別

5.1 整數型態

5.1.1 無號整數

d984. 棄保效應

題目大意:給你三個整數代表 A, B, C 三個候選人的得票數 a, b, c,如果得票數最少的候選人的票數全部給得票數第二高的候選人的話,最後會是誰當選?

候選人 A 要贏得選舉的條件如下:

再次提醒,數學上的 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: 身分證檢驗

//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)