iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
自我挑戰組

用 C & C++ 帶你手把手解 UVa 一顆星選集系列 第 8

Day 0x8 UVa10193 All You Need Is Love

題意

  • 輸入兩字串 S1S2,問是否能找出對兩字串皆合法的 L
  • 需要注意的點有:
    1. 會先輸入一正整數 N 代表測資數
    2. 每兩行輸入為一筆測資
    3. 每筆測資的 S1S2 皆為二進位字串
    4. 每行輸入不超過 30 個字元
    5. 所有輸入皆為合法字串
      • 開頭不為 0
      • 至少兩位元
    6. 什麼是合法的 L
      • 重複 S - L (二進位減法) 直到 S = L
    7. 輸出格式
      • p 代表第幾筆測資
      • Pair #p: All you need is love!
      • Pair #p: Love is not all you need!

解法

  • 思路
    • 一直重複用 S - L,其實就是看 S 是不是 L 的倍數,題目有舉例:
    S = 11011 = 27
    L =    11 =  3
    
      bin   dec
    11011 =  27
    11000 =  24
    10101 =  21
    10010 =  18
     1111 =  15
     1100 =  12
     1001 =   9
      110 =   6
       11 =   3
    
    • 所以要檢查有沒有一數字同時對兩字串 S1S2 都合法,代表 L 要同時為兩者的公因數,所以用 GCD 檢查兩者是否互質 (GCD = 1);先把輸入轉成十進位比較好處理
  • 老套路,輸入測資數 N 後,用 while 迴圈重複讀入兩字串存到字元陣列裡
    int N;
    
    scanf("%d", &N);
    
    while(N--){
    
        char S1[31] = {0};
        char S2[31] = {0};
    
        scanf("%s%s", S1, S2);
    
        ...
    }
    
  • 把字串代表的二進位轉成十進位
    int str_to_int(char *a, char *b){
    
        int num1 = 0, num2 = 0;
        int i;
    
        for(i = 0; i < strlen(a); i++){
            num1 = (num1 << 1) + (a[i] - '0');
        }
    
        for(i = 0; i < strlen(b); i++){
            num2 = (num2 << 1) + (b[i] - '0');
        }
    
        return GCD(num1, num2);
    }
    
  • 跟上篇 Day 0x7 UVa11417 GCD 一樣用個邪教遞迴
    int GCD(int a, int b){
        return b == 0 ? a : GCD(b, a % b);
    }
    
  • 判斷回傳是不是互質,再照規則輸出即可
    if(str_to_int(S1, S2) != 1){
        printf("Pair #%d: All you need is love!\n", Case++);
    }
    else{
        printf("Pair #%d: Love is not all you need!\n", Case++);
    }
    
  • C code
    #include<stdio.h>
    #include<string.h>
    
    int GCD(int a, int b){
        return b == 0 ? a : GCD(b, a % b);
    }
    
    int str_to_int(char *a, char *b){
    
        int num1 = 0, num2 = 0;
        int i;
    
        for(i = 0; i < strlen(a); i++){
            num1 = (num1 << 1) + (a[i] - '0');
        }
    
        for(i = 0; i < strlen(b); i++){
            num2 = (num2 << 1) + (b[i] - '0');
        }
    
        return GCD(num1, num2);
    }
    
    int main(){
    
        int N, Case = 1;
    
        scanf("%d", &N);
    
        while(N--){
    
            char S1[31] = {0};
            char S2[31] = {0};
    
            scanf("%s%s", S1, S2);
    
            if(str_to_int(S1, S2) != 1){
                printf("Pair #%d: All you need is love!\n", Case++);
            }
            else{
                printf("Pair #%d: Love is not all you need!\n", Case++);
            }
        }
    
        return 0;
    }
    
  • C++
  • C++ code
    #include <bits/stdc++.h>
    using namespace std;
    
    int GCD(int a, int b){
        return b == 0 ? a : GCD(b, a % b);
    }
    
    int main(){
    
        int N, Case = 1;
    
        cin >> N;
    
        while(N--){
    
            string S1, S2;
    
            cin >> S1 >> S2;
    
            int num1 = stoi(S1, nullptr, 2), num2 = stoi(S2, nullptr, 2);
    
            if(GCD(num1, num2) != 1){
                cout << "Pair #" << Case++ << ": All you need is love!\n";
            }
            else{
                cout << "Pair #" << Case++ << ": Love is not all you need!\n";
            }
        }
    
        return 0;
    }
    

上一篇
Day 0x7 UVa11417 GCD
下一篇
Day 0x9 UVa272 TEX Quotes
系列文
用 C & C++ 帶你手把手解 UVa 一顆星選集30

尚未有邦友留言

立即登入留言