ในปัญหานี้ เราได้รับค่าสองค่าที่เป็นผลรวม (แสดงถึงผลรวมของหลัก) และหลัก (แสดงถึงจำนวนหลัก) งานของเราคือการหาจำนวนที่น้อยที่สุดด้วยจำนวนหลักและผลรวมของหลักที่กำหนด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
sum = 15, dgiti = 2
ผลลัพธ์
69
คำอธิบาย
ตัวเลข 2 หลักที่มีผลรวม 15 ได้แก่ 69, 78, 87, 96
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือ พิจารณาตัวเลขทั้งหมดที่มีหลักหน่วยเป็นตัวเลข แล้วหาจำนวนที่น้อยที่สุดที่ผลรวมของหลักเท่ากับผลรวม
วิธีแก้ปัญหาที่มีประสิทธิภาพคือการใช้วิธีโลภ เราจะสร้างตัวเลขโดยเติมองค์ประกอบจากหลักสุดท้าย เช่น LSB ของตัวเลข เราจะพิจารณาองค์ประกอบที่ใหญ่ที่สุดที่เป็นไปได้สำหรับ LSB แล้วจึงไปที่ตำแหน่งถัดไป
เราจะพยายามรักษา LSB ให้ใหญ่ที่สุดและ MSB ให้เล็กที่สุดเท่าที่จะทำได้
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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
