Trong bài toán này, chúng ta được cho hai giá trị là tổng (biểu thị các chữ số sumof) và chữ số (biểu thị số chữ số). Nhiệm vụ của chúng ta là tìm số nhỏ nhất với một số chữ số nhất định và tổng các chữ số.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
sum = 15, dgiti = 2
Đầu ra
69
Giải thích
Tất cả các số có 2 chữ số có tổng 15 là:69, 78, 87, 96.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là xem xét tất cả các số có số tiền là chữ số và tìm số nhỏ nhất có tổng chữ số bằng tổng.
Một giải pháp hiệu quả là sử dụng cách tiếp cận tham lam. Chúng tôi sẽ tạo số sau đó bằng cách điền vào các phần tử từ chữ số cuối cùng, tức là LSB của số. Chúng tôi sẽ xem xét phần tử lớn nhất có thể cho LSB và sau đó chuyển sang vị trí tiếp theo.
Chúng tôi sẽ cố gắng giữ LSB càng lớn càng tốt và MSB càng nhỏ càng tốt.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
Smallest number is 159