資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在 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+ 次瀏覽
廣告