在 C++ 中查詢具有給定位數和數字和的最小數字


在這個問題中,我們得到兩個值:和(表示數字的和)和位數(表示數字的位數)。我們的任務是找到具有給定位數和數字和的最小數字。

讓我們來看一個例子來理解這個問題:

輸入

sum = 15, dgiti = 2

輸出

69

解釋

所有兩位數且數字和為 15 的數字是:69、78、87、96。

解決方案方法

一個簡單的解決方案是考慮所有位數為“位數”的數字,並找到數字和等於“和”的最小數字。

一個高效的解決方案是使用貪婪演算法。我們將透過從最後一位數字(即數字的最低有效位)填充元素來建立數字。我們將考慮最低有效位的最大可能元素,然後轉到下一位。

我們將嘗試使最低有效位儘可能大,而最高有效位儘可能小。

程式說明了我們解決方案的工作原理:

示例

 線上演示

#include <iostream>
using namespace std;
void findSmallestNumWithSum(int digit, int sum) {
   if (sum == 0) {
      if(digit == 1)
         cout<<"Smallest number is 0";
      else
         cout<<"Smallest number with sum cannot be found";
      return ;
   }
   if (sum > 9*digit) {
      cout<<"Smallest number with sum cannot be found";
      return ;
   }
   int number[digit];
   sum -= 1;
   for (int i = digit-1; i>0; i--) {
      if (sum > 9) {
         number[i] = 9;
         sum -= 9;
      } else {
         number[i] = sum;
         sum = 0;
      }
   }
   number[0] = sum + 1;
   cout<<"Smallest number is ";
   for (int i=0; i<digit; i++)
      cout<<number[i];
}
int main() {
   int sum = 15, digit = 3;
   findSmallestNumWithSum(digit, sum);
   return 0;
}

輸出

Smallest number is 159

更新於:2021年3月16日

1K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告