เราได้รับช่วงจำนวนเต็ม ตัวแปร m ใช้เป็นตัวหาร และตัวแปร d ใช้ตรวจสอบว่าเลข 'd' อยู่ที่ตำแหน่งคู่หรือไม่ และภารกิจคือคำนวณจำนวนตัวเลขในช่วงที่หารด้วย m ลงตัวและมีเลข d อยู่ตำแหน่งคู่
ตัวอย่าง
Input - int start = 20, end = 50, d = 8 และ m = 4
Output - จำนวนตัวเลขในช่วงที่หารด้วย m ลงตัวและมีเลข d อยู่ตำแหน่งคู่คือ: 2
คำอธิบาย - ช่วงคือ 20 ถึง 50 ดังนั้น ตัวเลขที่เป็นไปได้ที่มีหลัก d คือ 8 คือ 28, 38 และ 48 มี 8 อยู่ตำแหน่งคู่คือ 2 และตัวเลข 24 และ 48 หารด้วย m คือ 4 ลงตัว ดังนั้นจำนวนนับคือ 2
Input - int start = 10, end = 100, d = 6 และ m = 2
Output - จำนวนตัวเลขในช่วงที่หารด้วย m ลงตัวและมีเลข d อยู่ตำแหน่งคู่คือ: 8
คำอธิบาย - ช่วงคือ 10 ถึง 100 ดังนั้น ตัวเลขที่เป็นไปได้ที่มีหลัก d คือ 6, 16, 26, 36, 46, 56, 66, 76, 86 และ 96 มี 6 อยู่ตำแหน่งคู่ยกเว้น 6 และ 66 ที่อยู่ตำแหน่งคี่ เราจะไม่นำเข้า และตอนนี้เราจะตรวจสอบตัวเลขจากรายการที่หารด้วย 2 ลงตัว ดังนั้นตัวเลขทั้งหมด 16, 26, 36, 46, 56, 76, 86 และ 96 หารด้วย 2 ลงตัว ดังนั้นจำนวนนับคือ 8
แนวทางที่ใช้ในโปรแกรมด้านล่าง
- สร้างช่วงจำนวนเต็มเริ่มจาก start ถึง end ประกาศตัวแปร d และ m และรับค่า ส่งข้อมูลให้ฟังก์ชันเพื่อประมวลผลต่อ
- สร้างตัวแปรประเภท vector คือ vec
- เริ่มลูป while จนกว่าค่าจะเป็นค่าภายในตัวแปร start ภายใน while ให้ push ค่า val % 10 เข้า vec และตั้ง val = val / 10
- เรียกฟังก์ชัน reverse ใน STL ส่ง vec.begin() และ vec.end()
- ตั้งค่าในอาร์เรย์เป็น -1 ด้วย memset
- คืนค่า set_total(0, 0, 0, vec) ซึ่งเป็นฟังก์ชันที่จะตรวจสอบว่าตัวเลขที่มีตำแหน่งคู่เป็น d และหารด้วย m ลงตัว
- ภายในฟังก์ชัน set_total:
- ตรวจสอบ IF place == vec.size() แล้วตรวจสอบ IF temp == 0 คืนค่า 1 มิฉะนั้น 0
- ตรวจสอบ IF arr[place][temp][val] != -1 คืนค่าที่ arr[place][temp][val]
- ตรวจสอบ IF place % 2 == 1 แล้วตรวจสอบ IF val == 0 แล้วตรวจสอบ IF d > vec[place] คืนค่า 0
- ประกาศตัวแปร temp_2 ตั้งเป็น 0
- ตรวจสอบ IF d < vec[place] แล้ว temp_2 = 1
- ประกาศตัวแปร temp_3 เรียก set_total() แบบเรียกซ้ำ และคืนค่า arr[place][temp][val] = temp_3
- ประกาศตัวแปร count เก็บผลลัพธ์
- ประกาศตัวแปร set_limit ตั้งเป็น 9 ถ้า val == 1 มิฉะนั้น vec[place]
- เริ่มลูป FOR จาก i = 0 ถึง set_limit ตรวจสอบ IF i == d แล้ว continue
- ประกาศตัวแปร temp_2 ตั้งเป็น val
- ตรวจสอบ IF i < vec[place] แล้ว temp_2 = 1
- ตั้ง count ด้วยการเรียกฟังก์ชัน set_total แบบเรียกซ้ำ
- คืนค่า arr[place][temp][val] = count
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int arr[20][20][2];
int d, m;
int set_total(int place, int temp, int val, vector < int > vec) {
if (place == vec.size()) {
if (temp == 0) {
return 1;
}
return 0;
}
if (arr[place][temp][val] != -1) {
return arr[place][temp][val];
}
if (place % 2) {
if (val == 0) {
if (d > vec[place]) {
return 0;
}
}
int temp_2 = val;
if (d < vec[place]) {
temp_2 = 1;
}
int temp_3 = set_total(place + 1, (10 * temp + d) % m, temp_2, vec);
return arr[place][temp][val] = temp_3;
}
int count = 0;
int set_limit = (val ? 9 : vec[place]);
for (int i = 0; i <= set_limit; i++) {
if (i == d) {
continue;
}
int temp_2 = val;
if (i < vec[place]) {
temp_2 = 1;
}
count += set_total(place + 1, (10 * temp + i) % m, temp_2, vec);
}
return arr[place][temp][val] = count;
}
int divisible(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 set_total(0, 0, 0, vec);
}
int main() {
int start = 20, end = 50;
d = 8, m = 4;
int count = divisible(end) - divisible(start);
cout << "Count of Numbers in a Range divisible by m and having digit d in even positions are: " << count;
return 0;
}
หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้
ผลลัพธ์
Count of Numbers in a Range divisible by m and having digit d in even positions are: 2
