Số hạng tối thiểu lũy thừa có tổng bằng n bằng cách sử dụng C ++.

Tuyên bố vấn đề

Cho hai số nguyên dương N và X. Nhiệm vụ là biểu thị N thành tổng các lũy thừa của X (X0 + X1 +… .. + Xn) sao cho số lũy thừa của X là nhỏ nhất.

In ra số lũy thừa nhỏ nhất của N đã dùng để 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 =(3 ² + 3 ¹ + 3 ¹ )

Thuật toán

Sử dụng công thức dưới đây để tính toán kết quả cuối cùng -

1. If x = 1, then answer will be n only (n = 1 + 1 +…. n times)s
2. Any number n can be expressed as, n = x * a + b where 0 −= b −= x-1. Now since b is between 0 to x – 1, then b should be expressed as sum of x0 b times

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;
}

Đầu ra

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