C++ มีรายการฟังก์ชันมหาศาลสำหรับแก้ปัญหาทางคณิตศาสตร์ ฟังก์ชันทางคณิตศาสตร์หนึ่งคือการหาตัวเลขลำดับที่ N ที่ประกอบด้วยหลักเลขคี่ (Odd Digits) เท่านั้น บทความนี้จะอธิบายวิธีการครบถ้วนในการหาตัวเลขคี่ลำดับที่ N และเข้าใจว่าตัวเลขคี่คืออะไร และตัวเลขที่ประกอบด้วยหลักเลขคี่คืออะไร
การหาตัวเลขลำดับที่ N ที่ประกอบด้วยหลักเลขคี่เท่านั้น
ตัวเลขคี่ให้เศษเมื่อหารด้วย 2 ดังนั้น ตัวเลขคี่แรกๆ คือ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19...
เพื่อหาตัวเลขที่ต้องการ เรามีสองวิธี:
วิธีที่ 1 - ตรวจสอบทุกจำนวนธรรมชาติ ว่ามันเป็นตัวเลขคี่หรือไม่ และนับทุกตัวเลขคี่จนกว่าจำนวนนับจะเท่ากับ n และไม่นับถ้าตัวเลขที่พบเป็นเลขคู่ กล่าวคือ ข้ามเลขคู่และนับเลขคี่แล้วให้ตัวเลขลำดับที่ N ที่พบ
วิธีนี้อาจดูง่าย เพราะเราแค่ตรวจสอบทุกตัวเลขและนับเลขคี่ แต่ในแง่ของการเขียนโปรแกรม วิธีนี้ใช้เวลานานมากในการทำภารกิจนี้
วิธีที่ 2 - ทุกตัวเลขที่ประกอบด้วยหลักเลขคี่ สามารถมี 1, 3, 5, 7, 9 เป็นหลักสุดท้ายได้ ดังนั้นพวกมันคือตัวเลขคี่ เราตรวจสอบก่อนว่าตัวเลขลำดับที่ N เป็น 1, 3, 5, 7, 9 หรือไม่ หากใช่ เราได้คำตอบแล้ว มิฉะนั้น เราไปยังตัวเลขที่เป็นไปได้อื่นๆ ซึ่งคือ 11, 13, 15, 17, 19 และต่อมาคือ 21, 23, 25, 27, 29 นี่สร้างรูปแบบ (Pattern) คือ 1 × 10 + {หลักสุดท้ายที่เป็นไปได้}
ตัวอย่าง
หลักสุดท้ายที่เป็นไปได้คือ 1, 3, 5, 7, 9 ตัวเลขที่เป็นไปได้ต่อไปหาได้จาก 1 × 10 + 1 = 11 1 × 10 + 3 = 13 1 × 10 + 5 = 15 1 × 10 + 7 = 17 1 × 10 + 9 = 19 เช่น 11, 13, 15, 17, 19
โค้ดตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int main() {
queue<int> q;
int cnt = 0, ans = 0;
int n;
cin >> n;
int a[5] = {1, 3, 5, 7, 9};
for(int i = 0; i < 5; i++) {
cnt++;
if(cnt == n)
ans = a[i];
q.push(a[i]);
}
if(ans)
cout << ans << "\n";
else {
while(true) {
int x = q.front();
q.pop();
for(int j = 0; j < 5; j++) {
int temp = x * 10 + a[j];
q.push(temp);
cnt++;
if(cnt == n)
ans = temp;
}
if(ans)
break;
}
cout << ans << "\n";
}
return 0;
}
ผลลัพธ์
9
(เมื่อเราใส่ 5 เป็นอินพุต เราจะได้ 9 เป็นเอาต์พุต)
โค้ดข้างต้นคือโค้ด C++ สำหรับหาตัวเลขลำดับที่ N ที่ประกอบด้วยหลักเลขคี่เท่านั้น เพื่อเข้าใจโค้ดนี้ มาแยกโค้ดและเข้าใจแต่ละส่วนเพื่อเข้าใจโค้ดทั้งหมด
คำอธิบายโค้ด
ขั้นตอนที่ 1 - รับ n จากผู้ใช้และเริ่มต้นตัวแปรที่จำเป็น
int main() {
queue<int> q;
int cnt = 0, ans = 0;
int n;
cin >> n;
int a[5] = {1, 3, 5, 7, 9};
ที่นี่เราสร้างคิว (queue) และเริ่มต้นตัวแปร cnt เพื่อนับ และ ans เพื่อเก็บคำตอบ นอกจากนี้ เรารับอินพุตจากผู้ใช้ด้วย cin และเริ่มต้นอาร์เรย์ด้วยตัวเลขที่เป็นไปได้ก่อนหน้า
ขั้นตอนที่ 2 - ตรวจสอบว่าตัวเลขลำดับที่ N พบในตัวเลขที่เป็นไปได้เริ่มต้นหรือไม่ และเก็บตัวเลขเหล่านั้นในคิว
for(int i = 0; i < 5; i++) {
cnt++;
if(cnt == n)
ans = a[i];
q.push(a[i]);
}
if(ans)
cout << ans << "\n";
ในโค้ดข้างต้น เราตรวจสอบว่าตัวเลขลำดับที่ N พร้อมใช้งานในตัวเลขที่เป็นไปได้เริ่มต้น ซึ่งเก็บอยู่ในอาร์เรย์ และผลักดัน (push) คิวด้วยตัวเลขที่อยู่ในอาร์เรย์ และให้เอาต์พุทหากพบตัวเลขลำดับที่ N ในตัวเลขที่เป็นไปได้เริ่มต้น
ขั้นตอนที่ 3 - หาตัวเลขลำดับที่ N ในตัวเลขที่เป็นไปได้ถัดไป และเปลี่ยนตัวเลขในคิว หากไม่พบตัวเลขลำดับที่ N
while(true) {
int x = q.front();
q.pop();
for(int j = 0; j < 5; j++) {
int temp = x * 10 + a[j];
q.push(temp);
cnt++;
if(cnt == n)
ans = temp;
}
if(ans)
break;
}
cout << ans << "\n";
สุดท้าย เรานำตัวเลขทุกตัวออกจากคิว (pop) และสร้างตัวเลขที่เป็นไปได้ถัดไปจากนั้นโดยใช้สูตร { x × 10 + หลักเลขคี่สุดท้าย } และตรวจสอบว่าค่าของ cnt กลายเป็นเท่ากับ n หรือไม่
สรุป
ในบทความนี้ เรามีปัญหา: วิธีหาตัวเลขคี่ลำดับที่ N ที่ประกอบด้วยหลักเลขคี่เท่านั้น และเราพบสองวิธีในการทำเช่นนั้น วิธีแรกเข้าใจง่าย เพราะมันแค่ตรวจสอบตัวเลขแต่ละตัวและข้ามเลขคู่ แต่ใช้เวลาในการคำนวณ
วิธีที่สองใช้คิว (queue) และเก็บตัวเลขคี่ไว้ในนั้น และหาตัวเลขที่เป็นไปได้ถัดไปด้วยสูตรที่เราเห็นข้างต้น ความซับซ้อนของวิธีนี้คือ O(n)
เราทำโปรแกรมใน C++ เพื่อหาตัวเลขลำดับที่ N ที่ประกอบด้วยหลักเลขคี่เท่านั้น เราสามารถทำโปรแกรมนี้ในภาษาอื่นๆ เช่น C, Python, Java หรือภาษาโปรแกรมมิ่งอื่นๆ ได้เช่นกัน หวังว่าคุณจะพบว่าบทความนี้เป็นประโยชน์ เพราะมันให้ความรู้ครบถ้วนของวิธีการแก้ปัญหา
