Đề bài
Cho hai số nguyên dương N và X. Nhiệm vụ là biểu diễn N dưới dạng tổng các lũy thừa của X (X0 + X1 +...+ Xn) sao cho số lượng lũy thừa của X là tối thiểu.
In ra số lượng lũy thừa tối thiểu của N dùng để tạo tổng bằng N.
Nếu N = 15 và X = 3 thì chúng ta cần 3 lũy thừa của '3' như sau:
15 = (32 + 31 + 31)
Thuật toán
Sử dụng công thức dưới đây để tính kết quả cuối cùng:
1. Nếu x = 1, thì câu trả lời chỉ là n (n = 1 + 1 +... n lần) 2. Bất kỳ số n nào cũng có thể biểu diễn dưới dạng n = x * a + b với 0 ≤ b ≤ x-1. Vì b nằm giữa 0 và x-1, nên b nên được biểu diễn dưới dạng tổng của x0 b lần
Ví dụ
#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; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum number of powers = 3