เราได้รับช่วงจำนวนเต็ม ตัวแปร m ที่ใช้เป็นตัวหาร และตัวแปร d ที่ใช้ตรวจสอบว่าตัวเลข 'd' อยู่ที่ตำแหน่งคู่หรือไม่ และภารกิจคือการคำนวณการนับจำนวนใน ช่วงที่ตัวแปร m หารลงตัวและมีตัวเลข d อยู่ในตำแหน่งคู่
ตัวอย่าง
ป้อนข้อมูล - int start =20, end =50, d =8 และ m =4
ผลลัพธ์ - การนับจำนวนในช่วงที่หารด้วย m ได้และมีหลัก d อยู่ในตำแหน่งคู่คือ:2
คำอธิบาย - ช่วงเริ่มต้นจาก 20 ถึง 50 ดังนั้นตัวเลขที่เป็นไปได้ที่มีหลัก d เช่น 8 คือ 28, 38 และ 48 มี 8 ที่ตำแหน่งคู่เช่น 2 และตัวเลข 24 และ 48 หารด้วย ม. เช่น 4 ลงตัว ดังนั้นการนับคือ 2.
ป้อนข้อมูล - int start =10, end =100, d =6 และ m =2
ผลลัพธ์ - จำนวนตัวเลขในช่วงหารด้วย 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.
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
- สร้างช่วงของตัวเลขจำนวนเต็มตั้งแต่ตัวแปรเริ่มต้นจนถึงสิ้นสุดตัวแปร และประกาศตัวแปร d และ m แล้วป้อนค่า ส่งข้อมูลไปยังฟังก์ชันเพื่อการประมวลผลต่อไป
- สร้างตัวแปรประเภทเวกเตอร์ สมมุติว่า vec
- เริ่มวนรอบในขณะที่ถึงค่าซึ่งเป็นค่าภายในตัวแปรเริ่มต้น ตอนนี้ ภายใน while ดันค่าเป็น val % 10 ไปยังเวกเตอร์ และตั้งค่า val เป็น val / 10
- เรียกใช้ฟังก์ชันย้อนกลับใน STL โดยส่ง vec.begin() และ vec.end() เป็นอาร์กิวเมนต์
- ตั้งค่าในอาร์เรย์เป็น -1 โดยใช้ memset
- คืนค่า set_total(0, 0, 0, vec) ซึ่งเป็นฟังก์ชันที่จะตรวจสอบว่าตัวเลขที่มีตำแหน่งคู่ d และหารด้วย m ลงตัวหรือไม่
- ภายใน set_totalfunction-:
- ตรวจสอบว่าตำแหน่ง IF เท่ากับขนาดของเวกเตอร์ จากนั้นตรวจสอบ IF temp =0 จากนั้นคืนค่า 1 หรือคืนค่า 0
- ตรวจสอบ IF arr[place][temp][val] ไม่เท่ากับ -1 จากนั้นคืนค่าที่ arr[place][temp][val].
- ตรวจสอบ IF place % 2 =1 จากนั้นตรวจสอบ IF val =0 จากนั้นตรวจสอบว่า d มากกว่า vec[place] แล้วคืนค่า 0
- ประกาศตัวแปร temp_2 และตั้งค่าเป็น 0
- ตรวจสอบ IF d น้อยกว่า vec[place] แล้วตั้งค่า temp_2 เป็น 1
- ประกาศตัวแปร temp_3 และทำการเรียกซ้ำไปยัง set_total() และส่งคืน arr[place][temp][val] =temp_3
- ประกาศจำนวนตัวแปรเพื่อเก็บผลลัพธ์
- ประกาศตัวแปร set_limit และตั้งค่าเป็น 9 IF val เท่ากับ 1 ELSE ตั้งค่าด้วย vec[place]
- เริ่มลูป FOR จาก i ถึง 0 จนถึง set_limit และตรวจสอบว่า i เท่ากับ d แล้วดำเนินการต่อ
- ประกาศตัวแปรเป็น temp_2 และตั้งค่าเป็น val
- ตรวจสอบว่า i น้อยกว่า vec[place] แล้วตั้งค่า temp_2 เป็น 1
- ตั้งค่าการนับด้วยการเรียกซ้ำไปยังฟังก์ชัน set_total
- กลับ arr[place][temp][val] =นับ
ตัวอย่าง
#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
