กำหนดสตริงสตริงที่มีตัวเลขและผลรวมเป็นอินพุต เป้าหมายคือการหาตัวเลขที่ไม่เกิน str ที่มีผลรวมของหลักเท่ากับยอดทั้งหมด
ให้เราเข้าใจด้วยตัวอย่าง
ตัวอย่าง
ป้อนข้อมูล - N=”110” ผลรวม=5
ผลลัพธ์ - จำนวนตัวเลขที่น้อยกว่าหรือเท่ากับ N โดยมีผลรวมหลักคือ 7
คำอธิบาย - ตัวเลขไม่เกิน 110 ที่มีผลรวมของหลักเท่ากับ 5 ได้แก่ :-
5, 14, 23, 32, 41, 50 และ 104.
ป้อนข้อมูล - N=”1000” ผลรวม=3
ผลลัพธ์ - จำนวนตัวเลขที่น้อยกว่าหรือเท่ากับ N โดยมีผลรวมหลักคือ 10
คำอธิบาย - ตัวเลขไม่เกิน 1,000 ซึ่งมีผลรวมของหลักเท่ากับ 3 ได้แก่ :-
3, 12, 21, 30, 102, 111, 120, 201, 210 และ 300
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
ในแนวทางนี้ เราจะใช้โปรแกรมไดนามิกเพื่อเก็บผลรวมของตัวเลขและตัวเลขในอาร์เรย์ arr[18][2][162] ในที่นี้ 18 สำหรับตัวเลขสูงสุด 18 หลัก 2 สำหรับค่า 0 และ 1 และ 162 สำหรับผลรวมสูงสุดที่เป็นไปได้หากทั้งหมด 18 หลักเป็น 9 ( 18*9=162 )
ค่าขององค์ประกอบ arr[i][j][k] หมายถึงการนับจำนวนที่มีการพิจารณา i หลักแรกและ j คือ 0 หรือ 1 ขึ้นอยู่กับว่าตัวเลขที่สร้างในปัจจุบันของ i หลักน้อยกว่าหรือมากกว่าตัวเลข i หลักแรกใน N. ( ถ้า N คือ 123 และ i เป็น 2 เราจะตรวจสอบว่าตัวเลข 2 หลักเท่ากับหรือมากกว่า 12 ถ้าเท่ากับ 12 แล้ว j จะเป็น 1 มิฉะนั้น j จะเป็น 0 ใน arr[i][j][k ] ). ดัชนี k จะเป็นผลรวมของตัวเลข i ใน arr[i][j][k].
ถ้า i=digits ของ N และ k=input sum ผลลัพธ์จะเป็น 1 อื่น 0
สำหรับการกรอกหลักถัดไป ( i+1th ) เราจะตรวจสอบ j ถ้า j เป็น 1 แล้ว i-1 หลักจะเท่ากับ i-1 หลักของ N ดังนั้นตัวเลขถัดไปจะมีค่าระหว่าง 0 ถึง i+1 หลักที่ N เท่านั้นที่จะทำให้เป็น <=N.
ถ้า j เป็น 0 ดังนั้นตัวเลข i-1 หลักจะน้อยกว่าตัวเลข i-1 หลักใน N ดังนั้นเราสามารถใส่ค่าใดๆ ระหว่าง 0 ถึง 9 สำหรับตำแหน่งหลักถัดไป ( i+1 th ) และจะยังคงน้อยกว่า N.
ในตอนท้ายส่งคืนผลลัพธ์เป็นการนับครั้งสุดท้าย
- ใช้สตริง str แทนตัวเลข N และผลรวมเป็นผลรวมของหลัก
- นำอาร์เรย์ arr[18][2][162] และเริ่มต้นด้วย -1 โดยใช้ memset
- Function count_digits(int i, bool check, int temp, int total, string str, int size) เรียกซ้ำเติม arr[][][] และในตอนท้ายจะคืนค่าจำนวนตัวเลขที่น้อยกว่าหรือเท่ากับ N ด้วยค่าที่กำหนด ผลรวมหลัก
- หากจำนวนหลักปัจจุบัน i เท่ากับตัวเลขของ N และอุณหภูมิรวมปัจจุบันเท่ากับผลรวมที่ป้อนเข้า ให้คืนค่า 1 มิฉะนั้นจะคืนค่า 0
- นับ =arr[i][check][temp]. หากไม่ใช่ -1 ให้นับกลับเป็นผลลัพธ์
- ตรวจสอบตัวแปรชั่วคราว check_2 ( bool ) และ temp_2. (int )
- ข้ามหลัก 0 ถึง 9 โดยใช้ for loop และเปรียบเทียบว่าเช็คคือ 1 หรือ 0 ถ้า 1 ให้เปรียบเทียบตัวเลขปัจจุบัน ch กับ str[i] ถ้ามันมากกว่าก็ให้ทำลายลูป ( ไม่ทำอะไรเลย )
- ตั้งค่า check_2 =ตรวจสอบ || ch
- ตั้งค่า temp_2 =temp + (ch - '0') เป็นผลรวมปัจจุบัน
- เพิ่ม count_digits(i + 1, check_2, temp_2, total, str, size) เพื่อนับสำหรับการคำนวณผลรวมของตัวเลขแบบเรียกซ้ำ
- เมื่อสิ้นสุดการส่งคืน นับเป็นผลลัพธ์
ตัวอย่าง
#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;
} หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Count of numbers smaller than or equal to N with given digit sum are: 26
