Cho một chuỗi str chứa một số và một tổng số làm đầu vào. Mục tiêu là tìm các số cho đến str có tổng các chữ số bằng tổng.
Hãy cho chúng tôi hiểu với các ví dụ.
Ví dụ
Đầu vào - N =”110” sum =5
Đầu ra - Đếm các số nhỏ hơn hoặc bằng N có tổng các chữ số đã cho là:7
Giải thích - Các số có đến 110 có tổng các chữ số bằng 5 là:-
5, 14, 23, 32, 41, 50 và 104.
Đầu vào - N =”1000” sum =3
Đầu ra - Đếm các số nhỏ hơn hoặc bằng N có tổng các chữ số đã cho là:10
Giải thích - Các số đến 1000 có tổng các chữ số bằng 3 là:-
3, 12, 21, 30, 102, 111, 120, 201, 210 và 300.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng tôi sẽ sử dụng lập trình động để lưu trữ tổng các số và các chữ số của chúng trong mảng arr [18] [2] [162]. Ở đây 18 là số có tối đa 18 chữ số, 2 là giá trị 0 và 1. Và 162 là tổng lớn nhất có thể nếu tất cả 18 chữ số đều là 9 (18 * 9 =162).
Giá trị của phần tử arr [i] [j] [k] đại diện cho số lượng các số có chữ số i đầu tiên được xem xét và j là 0 hoặc 1 dựa trên việc số thứ i được xây dựng hiện tại nhỏ hơn hay nhiều hơn số chữ số i đầu tiên trong N. (nếu N là 123 và i là 2 thì chúng ta sẽ kiểm tra xem các số có 2 chữ số bằng nhau hoặc lớn hơn 12. Nếu bằng 12 thì j sẽ là 1. Còn lại j sẽ là 0 trong arr [i] [j] [k ]). Chỉ số k sẽ là tổng của i chữ số trong arr [i] [j] [k].
Nếu i =các chữ số của N và k =tổng đầu vào thì kết quả sẽ là 1 khác 0.
Để điền chữ số tiếp theo (thứ i + 1), chúng ta sẽ kiểm tra j. Nếu j là 1 thì chữ số i-1 bằng i-1 chữ số của N nên chữ số tiếp theo chỉ có thể có các giá trị từ 0 đến i + chữ số thứ 1 của N để tạo thành <=N.
Nếu j bằng 0 thì số i có 1 chữ số nhỏ hơn số i 1 chữ số ở N. Vì vậy, chúng ta có thể đặt bất kỳ giá trị nào từ 0 đến 9 cho vị trí chữ số tiếp theo (thứ i + 1) và nó vẫn nhỏ hơn N.
Cuối cùng, trả về kết quả dưới dạng tổng số cuối cùng.
- Lấy chuỗi str đại diện cho một số N và tổng là tổng các chữ số.
- Lấy mảng arr [18] [2] [162] và khởi tạo nó bằng -1 bằng memset.
- Hàm count_digits (int i, bool check, int temp, int total, string str, int size) điền đệ quy vào arr [] [] [] và ở cuối trả về số lượng các số nhỏ hơn hoặc bằng N với một tổng chữ số.
- Nếu số chữ số i hiện tại bằng các chữ số của N và tổng nhiệt độ hiện tại bằng tổng tổng đầu vào thì trả về 1 khác trả về 0.
- Lấy count =arr [i] [check] [temp]. Nếu nó không phải là -1 thì kết quả trả về là số lượng.
- Sử dụng các biến tạm thời là check_2 (bool) và temp_2. (int).
- Chuyển ngang các chữ số từ 0 đến 9 bằng vòng lặp for và so sánh nếu kiểm tra là 1 hoặc 0. Nếu 1 thì so sánh chữ số hiện tại ch với str [i]. Nếu nó lớn hơn thì hãy phá vỡ vòng lặp (không làm gì cả).
- Đặt check_2 =check || ch
- Đặt temp_2 =temp + (ch - '0') làm tổng hiện tại.
- Thêm count_digits (i + 1, check_2, temp_2, total, str, size) để đếm để tính toán đệ quy tổng các chữ số.
- Kết quả là số lượt trả lại cuối cùng.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, ing str, int size) {
if (i == size) {
if (temp == total) {
return 1;
} else {
return 0;
}
}
int count = arr[i][check][temp];
if (count != -1) {
return count;
}
count = 0;
bool check_2;
int temp_2;
for (char ch = '0'; ch <= '9'; ch++) {
if (!check) {
if (ch > str[i]) {
break;
}
}
check_2 = check || ch < str[i];
temp_2 = temp + (ch - '0');
count += count_digits(i + 1, check_2, temp_2, total, str, size);
}
return count;
}
int main() {
string str = "1101";
int size = str.size();
int total = 5;
memset(arr, -1, sizeof(arr));
cout << "Count of numbers smaller than or equal to N with given digit sum are: " << count_digits(0, 0, 0, total, str, size);
return 0;
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Đầu ra
Count of numbers smaller than or equal to N with given digit sum are: 26