使用 C++ 最小化冪的和為 n 的冪的項數。

問題表述

給定兩個正整數 N 和 X。任務是用 X 的冪表達 N（X0 + X1 +…..+ Xn），使得 X 的冪的個數最少。

列印用於使和等於 N 的 N 的最小冪數。

如果 N = 15 且 X = 3，那麼我們需要 3 個“3”的冪，如下所示 −

15 = (3² + 3¹ + 3¹)

演算法

使用以下公式計算最終結果 −

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

示例

#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

Narendra Kumar

更新時間：2019 年 10 月 31 日

234 次瀏覽

開啟你的 事業

完成課程並獲得認證

開始