在 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
廣告