從零開始的演算法競賽入門教學
0%

0-5 進階運算

發表於 更新於

浮點數運算誤差處理

使用 double 進行加減乘除時，多少會產生一點誤差，例如，100.0 * 99.0 可能被誤算為 9899.9999999。

此時，若運算中含有 == 等符號，將會出現問題。因此我們不以 == 進行浮點數是否等於的判斷。

取而代之，我們判斷兩個浮點數是否相等，只需判斷他們之間的差的絕對值是否小於某個特定值即可，這個值我們稱作 epsilon，以eps在程式中出現，一般為 10 的 -9 次方，寫作 1e-9。

1
2
3
4
5
6
7
double a, b, c;
double eps = 1e-9;
cin>>a>>b>>c;
if(c - a*b <= eps && c - a*b >= -eps){ // a * b == c is not good
    cout<<"Equal!\n";
}

字元運算

其實，字元可以加減！

ASCII TABLE

字元在運算的時候，將會被視為其ASCII碼！例如：

1
cout<<'a'+10<<'\n';

輸出將會是：

1
107

因為 ‘a’ 的 ASCII 碼是 97，在運算時便將其視為 97 了！

知道這個之後，可以做什麼呢？

可以注意到，**’A’～’Z’以及’a’～’z’以及’0’～’9’，在ASCII table的位置是連續的**，因此若將 ‘a’ 加上 4，就會變成在小寫字母裡，排在 ‘a’ 後面 4 個位置的 ‘e’ 。

1
2
3
char c = 'a';
c += 4;
cout<<c<<'\n';

輸出：

1
e

大寫轉小寫

1
2
3
4
char c;
cin>>c;
c += 'a' - 'A'
cout<<c<<'\n';

將輸入進來的大寫字母，加上 ‘a’(ASCII碼：97) 與 ‘A’(ASCII碼：65) 間的差距，就可以將其轉為大寫了！

字元比較

字元的比較，以其 ASCII 碼為準。

例如，’Z’ 的 ASCII 碼是 90，’a’ 是 97，因此 ‘Z’ < ‘a’。

字串運算

字串可以進行加法，意思為在其後方串接另一字串。

例如：

1
2
3
4
5
6
7
string s = "abc";
s += "def";
cout<<s<<'\n';
s += 'a';
cout<<s<<'\n';
s = s + s + s;
cout<<s<<'\n';

輸出：

1
2
3
abcdef
abcdefa
abcdefaabcdefaabcdefa

但要注意，字串只有加法，沒有減、乘、除法。

字串比較

字串比較的原則是這樣的：先比第一個字元、一樣的話比第二個、之後比第三個……。如果那個位置是空的，那它比任何字元都小

例如：

“abc” < “baa” (第一個字元，’a’ < ‘b’)

“abc” < “abd” (第三個字元，’c’ < ‘d’)

“abc” < “abcd” (比到第四個時，前面那個字串已經到尾了)

如果打開一本英文辭典，會發現單字就是照著這樣的規則排列的，因此這種方法稱為字典序。

bool的特殊用法

1
2
3
4
5
6
bool x = 5;
cout<<x<<'\n';
x = -1;
cout<<x<<'\n';
x = 0;
cout<<x<<'\n';

輸出：

1
2
3
1
1
0

bool的值只有 1 或是 0 。當一個int被指派給 bool，只要那個int不是0，無論正負，bool值都會是1。

因此，很多時候我們可以這樣寫：

1
2
3
4
5
if(a){
    ......
}

//相同於 if(a!=0)

位元運算

在電腦中，數值以二進位儲存，所謂位元運算，指的就是以一個一個只有 0 或 1 的位元為單位進行運算。

對整數而言，我們有以下幾種位元運算：

  1. and &
  2. or |
  3. xor ^
  4. not ~

and &

以位元為單位的and運算

1 & 1 -> 1

1 & 0 -> 0

0 & 0 -> 0

在對兩個整數進行 & 運算時，先將其分解為二進位，接著逐位進行 & 運算。

例如： 6 & 5

將 6 分解為二進位，是 110

將 5 分解為二進位，是 101

逐位進行 & 運算，只有最高位數兩者同時為1，得到結果為 100，為 4 的二進位表示法。

因此， 6 & 5 == 4

or |

以位元為單位的or運算

1 | 1 -> 1

1 | 0 -> 1

0 | 0 -> 0

例如： 6 | 5

將 6 分解為二進位，是 110

將 5 分解為二進位，是 101

110 與 101，在任何一個位數都至少有一個 1，因此 | 運算的結果為 111，為 7 的二進位表示法。

因此， 6 | 5 == 7

xor ^

不要把它當作次方！C++並沒有次方的運算子！

一樣是位元運算，xor是什麼意思呢？

1 ^ 1 -> 0

1 ^ 0 -> 1

0 ^ 0 -> 0

只有一個值為 1 的時候，結果才會為 1，若兩邊同時為 1 或 0，結果都是 0。

例如： 6 ^ 5

將 6 分解為二進位，是 110

將 5 分解為二進位，是 101

110 與 101，在最高位兩者皆為 1 ，在其他位數只有其中一方為 1 ，因此 ^ 運算的結果為 011，為 3 的二進位表示法。

因此， 6 ^ 5 == 3

位元運算的交換律與結合律

同種位元運算間，皆具有交換律與結合律，例如：

3 & 5 & 6 == 6 & 3 & 5

3 ^ (5 ^ 6) == 6 ^ (3 ^ 5)

3 | 5 | 6 == 6 | 3 | 5

但不同種位元運算之間則無結合律，例如：

(7 | 5) & 10 != 7 | (5 & 10)

xor 特別的地方

x ^ x == 0

因此， (a ^ x) ^ x == a ^ (x ^ x) == a ^ 0 == a

以及若 a ^ b = c， a ^ b ^ a = c ^ a，b = c ^ a

正是因為這樣的有趣性質，使得 xor 出現於許多加密演算法中。

練習

TOJ 99

TOJ 100

TOJ 101

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//TOJ 99
#include<iostream>
using namespace std;
double a,b,c,d;
double eps = 1e-9;

int main() {
    cin>>a>>b>>c>>d;
    double det = a*d - b*c; 
    if(det < eps && det > -eps){
        cout<<0<<'\n';
    }
    else{
        cout<<1<<'\n';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// TOJ 100
#include<iostream>
using namespace std;
char c;

int main() {
    cin >> c;
    if(c == 'A'){
        cout<<'@'<<'\n';
    }
    else{
        c--;
        cout<<c<<'\n';
    }
}
1
2
3
4
5
6
7
8
9
10
// TOJ 101
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    char c = n + 'A' - 1;
    // 5 + 'A' - 1 = 'A' + 4 = 'E'
    cout << c << '\n';
}