C++ การแสดงตัวเลขในรูปกำลังของอีกตัวหนึ่ง

อภิปรายปัญหาการแสดงตัวเลขในกำลังของอีกตัวเลขหนึ่ง เราได้รับตัวเลขสองตัว คือ x และ y เราต้องบอกว่า y สามารถแสดงในรูปกำลังของ x ได้หรือไม่ โดยแต่ละกำลังของ x สามารถใช้ได้เพียงครั้งเดียว ตัวอย่างเช่น:

Input: x = 4, y = 11
Output: true
คำอธิบาย: 4^2 - 4^1 - 4^0 = 11 ดังนั้น y สามารถแสดงในรูปกำลังของ x ได้

Input: x = 2, y = 19
Output: true
คำอธิบาย: 2^4 + 2^1 + 2^0 = 19 ดังนั้น y สามารถแสดงในรูปกำลังของ x ได้

Input: x = 3, y = 14
Output: false
คำอธิบาย: 14 สามารถแสดงเป็น 3^2 + 3^1 + 3^0 + 3^0 แต่เราไม่สามารถใช้พจน์กำลังของ x ซ้ำได้

วิธีการหาคำตอบ

จากการตรวจสอบตัวอย่างว่าวิธีที่ 19 แสดงในรูปกำลังของ 2 เราสามารถสร้างสมการได้:

c0(x^0) + c1(x^1) + c2(x^2) + c3(x^3) + ... = y ...(1),

โดยที่ c0, c1, c2 สามารถเป็น -1, 0, +1 เพื่อแสดงว่า (-1)พจน์ถูกลบ, (+1)พจน์ถูกบวก, (0)พจน์ไม่รวม

c1(x^1) + c2(x^2) + c3(x^3) + ... = y - c0,

นำ x ออกมาร่วม:

c1(x^0) + c2(x^1) + c3(x^2) + ... = (y - c0)/x ...(2),

จากสมการ (1) และ (2) เราสามารถแสดงตัวเลขในรูปแบบเดียวกันอีกครั้ง และสำหรับคำตอบที่จะมีอยู่ (y - Ci) ต้องหาร x ลงตัว และ Ci สามารถมีได้แค่ -1, 0 และ +1

ดังนั้นสุดท้ายเราต้องตรวจสอบจนกว่า y > 0 ว่า [(y-1) % x == 0] หรือ [(y) % x == 0] หรือ [(y+1) % x == 0] หรือว่าไม่มีคำตอบ

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int main(){
    int x = 2, y = 19;
    // ตรวจสอบการหาร y ลงตัวจนกว่า y > 0
    while (y > 0) {
        // ถ้า y-1 หาร x ลงตัว
        if ((y - 1) % x == 0)
            y = (y - 1) / x;
        // ถ้า y หาร x ลงตัว
        else if (y % x == 0)
            y = y / x;
        // ถ้า y+1 หาร x ลงตัว
        else if ((y + 1) % x == 0)
            y = (y + 1) / x;
        // ถ้าไม่มีเงื่อนไขไหนตรง
        // y ไม่สามารถแสดงในรูปกำลังของ x ได้
        else
            break;
    }
    if(y == 0)
        cout << "y can be represented in terms of the power of x.";
    else
        cout << "y cannot be represented in terms of the power of x.";
    return 0;
}

ผลลัพธ์

y can be represented in terms of the power of x.

สรุป

ในบทช่วยสอนนี้ เราอภิปรายวิธีตรวจสอบว่าการแสดงตัวเลขในรูปกำลังของอีกตัวเลขเป็นไปได้หรือไม่ เราอภิปรายวิธีง่ายๆ ในการแก้ปัญหานี้โดยการตรวจสอบการหารลงตัวของตัวเลขปัจจุบัน ก่อนหน้า และถัดไป กับ y

เรายังอภิปรายโปรแกรม C++ สำหรับปัญหานี้ซึ่งเราสามารถทำได้กับภาษาโปรแกรมมิ่งอย่าง C, Java, Python ฯลฯ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์