การบวกเลขฐาน n (Adding Base-n Numbers)

บทนำ

ในปัญหานี้ กำหนดตัวเลขสองตัว ฐานของตัวเลขเหล่านั้นคือ n เราต้องหาผลลัพธ์ของการบวกตัวเลขเหล่านั้นในฐาน n เช่นกัน

ขั้นแรก แปลงตัวเลขเป็นเลขฐานสิบ (Decimal) จากค่าทศนิยม สามารถบวกกันได้ง่ายๆ สุดท้าย แปลงผลลัพธ์กลับเป็นเลขฐาน n อีกครั้ง

ตัวเลขฐาน n ถูกให้มาในรูป String เนื่องจากตัวเลขที่มีฐานมากกว่า 9 อาจมีตัวอักษรแทนตัวเลข เช่น เลขฐานสิบหก (Hexadecimal) มีตัวอักษร 6 ตัว (A-F)

อินพุตและเอาต์พุต

Input: ฐานของระบบเลข: 16, ตัวเลขแรก: 2C, ตัวเลขที่สอง: 5F
Output: ผลลัพธ์ของการบวกคือ: 8B

อัลกอริทึม

baseNtoDec(number, base)

Input: สตริงตัวเลขฐาน N, ค่าของฐาน N

Output: ค่าเทียบเท่าทศนิยมของตัวเลขฐาน N

Begin
    len := ความยาวของ number
    power := 1
    num := 0
    for i := len -1 down to 0, do
        if number[i] >= base, then
            return invalid number
        num := num + number[i] * power
        power := power * base
    done
    return num
End

decToBaseN(dec, base)

Input: เลขฐานสิบ, ฐาน N ที่ต้องการแปลง

Output: สตริงตัวเลขฐาน N

Begin
    while dec > 0, do
        res := concatenate (dec mod base) กับ res
        dec := dec / base
    done
    reverse the result
    return res
End

addBaseN(num1, num2, base)

Input: สองตัวเลขในฐาน N, ค่าของฐาน N

Output: ตัวเลขหลังการบวกในฐาน N

Begin
    dec1 := baseNtoDec(num1, base)
    dec2 := baseNtoDec(num2, base)
    sum := decToBaseN(dec1 + dec2, base)
    return sum
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <algorithm>
using namespace std;

int getVal(char c) {
    if (c >= '0' && c <= '9')
        return int(c-'0');  // ค่าทศนิยมของตัวเลขที่กำหนด
    else
        return int(c-'A'+10);  // สำหรับตัวเลข alphanumeric
}

char revVal(int n) {
    if (n >= 0 && n <= 9)
        return char(n+'0');  // ตัวอักษรของตัวเลขที่กำหนด
    else
        return char(n+'A'-10);  // สำหรับ alphanumeric, ได้ตัวอักษรจากทศนิยม
}

int baseNtoDec(string number, int base) {
    int len = number.size();
    int power = 1;
    int num = 0;
    for (int i = len-1; i >= 0; i--) {
        // จากหลักสุดท้ายถึงหลักแรก
        if (getVal(number[i]) >= base)
            return INT_MIN;  // เมื่อหลักหนึ่ง >= base, return -infinity เป็น error
        num += getVal(number[i]) * power;
        power = power * base;
    }
    return num;
}

string decToBaseN(int dec, int base) {
    string res = "";  // สตริงว่าง
    while (dec > 0) {
        res += revVal(dec % base);
        dec /= base;
    }
    reverse(res.begin(), res.end());  // กลับสตริงเพื่อได้คำตอบสุดท้าย
    return res;
}

int main() {
    int base;
    string num1, num2, sum;
    cout << "Enter Base: "; cin >> base;
    cout << "Enter first number in base " << base << ": "; cin >> num1;
    cout << "Enter second number in base " << base << ": "; cin >> num2;
    sum = decToBaseN((baseNtoDec(num1, base) + baseNtoDec(num2, base)), base);
    cout << "The result of addition is: " << sum;
}

ผลลัพธ์

Enter Base: 16
Enter first number in base 16: 2C
Enter second number in base 16: 5F
The result of addition is: 8B