การแทนค่า C++ ของตัวเลขในอำนาจของผู้อื่น

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

Input: x = 4, y = 11
Output: true
Explanation: 4^2 - 4^1 - 4^0 = 11 Hence y can be represented in the power of x.

Input: x = 2, y = 19
Output: true
Explanation: 2^4 + 2^1 + 2^0 =19 Hence y can be represented in the power of x.

Input: x = 3, y = 14
Output: false
Explanation: 14 can be represented as 3^2 + 3^1 + 3^0 + 3^0 but we cannot use one term of power of x twice.

แนวทางในการหาแนวทางแก้ไข

จากการตรวจสอบตัวอย่างว่า 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),

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

สุดท้ายเราต้องตรวจสอบจนถึง y>0 ว่า [(y-1) % x ==0] หรือ [(y) % x ==0] หรือ [(y+1) % x ==0] หรือว่า a ไม่มีวิธีแก้ปัญหา

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int main(){
   int x = 2, y = 19;
   // checking y divisibility till y>0
   while (y>0) {
      // If y-1 is divisible by x.
      if ((y - 1) % x == 0)
         y = (y - 1) / x;
        // If y is divisible by x.
      else if (y % x == 0)
         y = y / x;
         // If y+1 is divisible by x.
      else if ((y + 1) % x == 0)
         y = (y + 1) / x;
         // If no condition satisfies means
         // y cannot be represented in terms of power of 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 เป็นต้น เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์