เราได้รับช่วงจำนวนเต็มเริ่มต้นจากตัวแปร สมมติว่าเริ่มต้นจนถึงสิ้นสุดตัวแปรและตัวแปร k และภารกิจคือการคำนวณการนับตัวเลขในช่วงเพื่อให้ตัวเลขไม่เกิน 'k' ที่ไม่ใช่ศูนย์ ตัวเลข
ตัวอย่าง
ป้อนข้อมูล - int start =50, end =100 และ K =2;
ผลลัพธ์ - จำนวนตัวเลขในช่วงที่ตัวเลขมีตัวเลขไม่เกิน K ที่ไม่ใช่ศูนย์คือ 50
คำอธิบาย - ช่วงเริ่มต้นจาก 50 ถึง 100 และเราได้รับ k เป็น 2 ดังที่เราเห็นตัวเลขทั้งหมดระหว่าง 50 ถึง 100 มีตัวเลข 2 หลักซึ่งทำให้ไม่สามารถมีตัวเลขศูนย์มากกว่า 2 หลักได้ยกเว้นตัวเลข 100 ซึ่งเป็น ตัวเลข 3 หลักแต่จะมี 2 ศูนย์ไม่เกินนั้นจึงนับเป็น 50
ป้อนข้อมูล - int start =50, end =100 และ K =1;
ผลลัพธ์ - การนับจำนวนในช่วงที่ตัวเลขมีจำนวนไม่เกิน K ไม่ใช่ศูนย์
ตัวเลขคือ:5
คำอธิบาย - ช่วงเริ่มต้นจาก 50 ถึง 100 และเราได้รับ k เป็น 1 ดังที่เราเห็น ตัวเลขทั้งหมดระหว่าง 50 ถึง 100 มีตัวเลข 2 หลัก ดังนั้นตัวเลขที่มีไม่เกิน 1 หรือ k เป็นตัวเลขที่ไม่ใช่ศูนย์คือ 50 , 60, 70, 80 และ 90 จึงนับเป็น 5
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
- สร้างช่วงของตัวเลขจำนวนเต็มตั้งแต่ตัวแปรเริ่มต้นจนถึงสิ้นสุดตัวแปร และประกาศ k และป้อนค่า ส่งข้อมูลไปยังฟังก์ชันเพื่อการประมวลผลต่อไป
- สร้างตัวแปรประเภทเวกเตอร์ สมมุติว่า vec
- เริ่มวนรอบในขณะที่ถึงค่าซึ่งเป็นค่าภายในตัวแปรเริ่มต้น ตอนนี้ ภายใน while ดันค่าเป็น val % 10 ไปยังเวกเตอร์ และตั้งค่า val เป็น val / 10
- เรียกใช้ฟังก์ชันย้อนกลับใน STL โดยส่ง vec.begin() และ vec.end() เป็นอาร์กิวเมนต์
- ตั้งค่าในอาร์เรย์เป็น -1 โดยใช้ memset
- คืนค่า check_val(0, 0, 0, vec) ซึ่งเป็นฟังก์ชันที่จะตรวจสอบว่าตัวเลขนั้นไม่ใช่ศูนย์หรือไม่
- ภายในฟังก์ชัน check_val-:
- ตรวจสอบ IF place เท่ากับขนาดของเวกเตอร์ จากนั้นตรวจสอบ IF temp <=k แล้วคืนค่า 1 หรือคืนค่า 0
- ตรวจสอบว่า arr[place][temp][set_val] ไม่เท่ากับ -1 แล้วคืนค่าที่ arr[place][temp][set_val].
- ประกาศตัวแปรเพื่อเก็บผลลัพธ์และตั้งค่าเป็น 0
- ประกาศตัวแปร val และตั้งค่าเป็น 9 IF set_val เท่ากับ 1 ELSE ตั้งค่าเป็น i++
- เริ่มลูป FOR จาก 0 จนถึงค่า val
- ภายในลูปตั้งค่า temp_2 เป็น temp และตรวจสอบว่า IF 1 ไม่เท่ากับ 0 จากนั้นเพิ่มค่าของ temp_2 เป็น 1 และตั้งค่า temp_3 เป็น set_val และตรวจสอบว่า i น้อยกว่า vec[place] จากนั้นตั้งค่า temp_3 เป็น 1
- ตั้งค่าของการนับเป็นการเรียกซ้ำไปยังฟังก์ชัน check_val(place + 1, temp_2, temp_3, vec)
- ส่งคืน arr[place][temp][set_val] เท่ากับนับ
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int arr[20][20][2];
int K;
int check_val(int place, int temp, int set_val, vector < int > vec) {
if (place == vec.size()) {
if (temp <= K) {
return 1;
}
return 0;
}
if (arr[place][temp][set_val] != -1) {
return arr[place][temp][set_val];
}
int count = 0;
int val = (set_val ? 9 : vec[place]);
for (int i = 0; i <= val; i++) {
int temp_2 = temp;
if (i != 0) {
temp_2++;
}
int temp_3 = set_val;
if (i < vec[place]) {
temp_3 = 1;
}
count += check_val(place + 1, temp_2, temp_3, vec);
}
return arr[place][temp][set_val] = count;
}
int Not_more_k(int val) {
vector < int > vec;
while (val) {
vec.push_back(val % 10);
val = val / 10;
}
reverse(vec.begin(), vec.end());
memset(arr, -1, sizeof(arr));
return check_val(0, 0, 0, vec);
}
int main() {
int start = 50, end = 100;
K = 2;
int count = Not_more_k(end) - Not_more_k(start);
cout << "Count of Numbers in Range where the number does not contain more than K non zero digits are: " << count;
return 0;
} หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Count of Numbers in Range where the number does not contain more than K non zero digits are: 50
