ข้อความโจทย์
กำหนดจำนวนเต็มบวกสองจำนวน N และ X งานคือการแสดง N เป็นผลรวมของกำลังของ X (X0 + X1 + ... + Xn) โดยที่จำนวนกำลังของ X ควรน้อยที่สุด
พิมพ์จำนวนกำลังของ N ที่น้อยที่สุดที่ใช้ทำให้ผลรวมเท่ากับ N
ถ้า N = 15 และ X = 3 แล้วเราต้องการ 3 กำลังของ '3' ดังนี้ -
15 = (32 + 31 + 31)
อัลกอริทึม
ใช้สูตรด้านล่างเพื่อคำนวณผลลัพธ์สุดท้าย -
1. ถ้า x = 1 คำตอบจะเป็น n เท่านั้น (n = 1 + 1 + ... n ครั้ง) 2. จำนวน n ใดๆ สามารถแสดงได้เป็น n = x * a + b โดยที่ 0 ≤ b ≤ x-1 ตอนนี้ b อยู่ระหว่าง 0 ถึง x-1 ดังนั้น b ควรแสดงเป็นผลรวมของ x0 จำนวน b ครั้ง
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
int minNumOfPower(int n, int x) {
if (x == 1) {
return n;
}
int result = 0;
while (n > 0) {
result = result + (n % x);
n = n / x;
}
return result;
}
int main() {
int n = 15;
int x = 3;
cout << "Minimum number of powers = " << minNumOfPower(15, 3) << endl;
return 0;
}
ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -
Minimum number of powers = 3
