Tư duy toán và lập trình: Bài toán về viết số tự nhiên thỏa mãn điều kiện tổng các chữ số

Trong bài viết tìm tòi học toán này, thầy Hiếu giới thiệu các em học sinh một bài toán về viết số thỏa mãn điều kiện tổng các chữ số bằng 1 số cho trước. Bài tập này thuộc chương trình toán lớp 4, 5 của tiểu học.

Ví dụ 1: Viết số tự nhiên nhỏ nhất có tổng các chữ số bằng 11 và các chữ số khác nhau.

Ta có để có số nhỏ nhất thì số chữ số là ít nhất, để có ít chữ số nhất mà tổng các chữ số không đổi, ta sử dụng các chữ số lớn nhất có thể

Ta có: 11 = 9 +  2 --> sắp xếp được số 29.

Ví dụ 2:  Viết số tự nhiên nhỏ nhất có tổng các chữ số bằng 20 và các chữ số khác nhau.

Ta có: 

20 = 9 + 8 + 3 --> sắp xếp được số 389

Bây giờ, chúng ta tìm hiểu bài toán lập trình sau đây:

Với bài lập trình này, ý tưởng về thuật toán như sau:

Ta tách số n thành tổng các chữ số lớn nhất có thể (các chữ số khác nhau);

Ví dụ: n = 30

Ta có n = 9 + 21

sau đó cập nhật n là 21, chữ số lớn nhất có thể là 8:

21 = 8 + 13

cập nhật n là 13; chữ số lớn nhất có thể là 8 - 1 = 7

13 = 7 + 6

...

Các em học sinh tham khảo code của thầy Hiếu bằng ngôn ngữ C++ như dưới đây:

#include
#include
using namespace std;

int main()
{
     long long int n;
     cin >> n;
     int cs_max = 9;
     long long int cs[10] = {};
     long long int dem = 9;
     while (n != 0)
     {
            if(n > cs_max)
            {
                     n = n - cs_max;
                     cs[dem] = cs_max;
                     dem --;
                     cs_max --;
            }else{
                    cs[dem] = n;
                    n = 0;
            }
            
     }
     
     // In ra so tim đc
     for(int i = 0; i < 10; i ++)
     {
          if(cs[i] != 0) cout << cs[i];
     }
}