【個人筆記】C++ ZeroJudge 基礎題庫解題(純練習) - part 4

a022.：https://zerojudge.tw/ShowProblem?problemid=a022

難度：★☆☆☆☆

#include <bits/stdc++.h>

using namespace std;

int main(){
    bool re = true;
    int count;
    string input;
    cin >> input;
    count = input.size();
    char result[count];
    strcpy(result, input.c_str());
    for (int i = 0; i < floor(count / 2); i++){
        if (result[i] != result[count-1-i]){
            re = false;
        }
    }
    cout << (re ? "yes" : "no");
    return 0;
}

這邊用到了 bool 資料型態，表示是不是迴文，預設為 true，也就是迴文的意思。

而 strcpy 的部分需要注意，務必將 input 的 string 型態轉為 char，使用到函數 c_str()。

而 for 迴圈裡面的 floor(count / 2) 表示向下取整，如果直接寫 count / 2 也是可以，但是會耗損較多時間。

for 下面的條件判斷就是判斷前半部分是否與後半部分相同，如果不同就將 re 設為 false。

最後三元運算子有個小細節，由於運算子優先順序的原因，<< 的優先級大於 ? : 所以如果單純寫：cout << re ? "yes" : "no"; 輸出只會有 1 跟 0。

因此最後輸出部分的三元運算子需要加上小括號。

a024.：https://zerojudge.tw/ShowProblem?problemid=a024

難度：★☆☆☆☆

內建函式庫寫法：

// C++ 14 寫法（因為zerojudge僅支援 C++ 14）
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x, y;
    cin >> x >> y;
    cout << __gcd(x, y);
    return 0;
}

輾轉相除法寫法（for迴圈）：

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x, y, temp;
    cin >> x >> y;
    while (y != 0) { // (a, b) = (b, a % b)
        temp = y;
        y = x % y;
        x = temp;
    }
    cout << x;
}

遞迴寫法：

#include <iostream>

using namespace std;

int gcd(int x, int y) {
   if (x % y == 0) return y;
   return gcd(y, x % y);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x, y;
    cin >> x >> y;
    cout << gcd(x, y);
    return 0;
}

a034.：https://zerojudge.tw/ShowProblem?problemid=a034

難度：★★☆☆☆

使用 bitset 容器解（比較難的是如何移除前導 0）：

#include <iostream>
#include <bitset>

using namespace std;

int main() {
    int decimal;
    while (cin >> decimal){
        bitset<32> binary(decimal);
        string binary_str = binary.to_string();
        // size_t 為 unsigned int
        size_t first_one = binary_str.find('1'); // 找到第一個 1
        // 以下判斷是移除前導 0 的步驟
        if (first_one != string::npos) {
            binary_str = binary_str.substr(first_one);
        } else {
            binary_str = "0";
        }
        cout << binary_str << "\n";
    }
    return 0;
}

:::info
string::npos 用在 string.find() 函數上，表示查找失敗，因為它通常被定義成 static const size_t npos = -1;。
:::

不用函式庫的寫法：

#include <iostream>

using namespace std;

void decimalToBinary(int n) {
    if (n == 0) {
        cout << "0";
        return;
    }

    int binary[32];
    int index = 0;

    while (n > 0) {
        binary[index] = n % 2;
        n = n / 2;
        index++;
    }

    for (int i = index - 1; i >= 0; i--) {
        cout << binary[i];
    }
    
    cout << "\n";
}

int main() {
    int decimal;
    while(cin >> decimal){
        decimalToBinary(decimal);
    }
    return 0;
}

a038.：https://zerojudge.tw/ShowProblem?problemid=a038

難度：★★☆☆☆

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    if (n == 0) {
        cout << 0;
        return 0; // 加上 return 0; 使程式提前結束
    }

    int reversed = 0;
    while (n != 0) {
        int digit = n % 10;
        reversed = reversed * 10 + digit;
        n /= 10;
    }

    cout << reversed;
    return 0;
}

程式碼說明：

1. while 的地方，每次取 % 10，一次拿最右邊的一位數字出來。
2. 把拿出來的數字，累積放到新的數字後面（乘 10，讓位置往左移）。
3. 原來的數字除以 10，把剛剛處理過的那一位刪掉。
4. 重複這個動作直到原數字變成 0。

如 12345：

1. 先把 5 拿出來。
2. reversed 經過計算後等於 5。
3. n 除以 10，變成 1234。
4. 接下來以此類推，再把最後的 4 拿出來，reversed 計算後變成 50 + 4 = 54。

a040.：https://zerojudge.tw/ShowProblem?problemid=a040

難度：★★☆☆☆

這是一道很經典的窮舉題目。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

bool isArmstrong(int num) { // 判斷是否為阿姆斯壯數
    int original = num; // 保留原始數字（比較用）
    int sum = 0;
    int digits = 0;
    int temp = num;
    
    while (temp > 0) { // 算有幾位數
        digits++;
        temp /= 10;
    }
    
    temp = num;
    while (temp > 0) { // 計算每位數的 n 次方總和
        int digit = temp % 10;
        sum += pow(digit, digits);
        temp /= 10;
    }
    
    return sum == original;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> armstrongNumbers;
    
    for (int i = n; i <= m; ++i) {
        if (isArmstrong(i)) {
            armstrongNumbers.push_back(i);
        }
    }
    
    if (armstrongNumbers.empty()) {
        cout << "none";
    } else {
        // size_t 就是 unsigned int
        for (size_t i = 0; i < armstrongNumbers.size(); ++i) {
            cout << armstrongNumbers[i];
            if (i != armstrongNumbers.size() - 1) {
                cout << " ";
            }
        }
    }
    
    return 0;
}