ในปัญหาที่กำหนด เราได้จำนวนเต็ม n เราต้องหา Pn กล่าวคือหมายเลขเพลในตำแหน่งนั้น อย่างที่เราทราบกันดีอยู่แล้วว่า pell number เป็นส่วนหนึ่งของอนุกรมที่กำหนดโดยสูตรนี้ −Pn =2*Pn-1 + Pn-2
ด้วยตัวเลขเริ่มต้นสองตัวแรก − P0 =0 และ P1 =1
แนวทางในการหาทางออก
ตอนนี้เราจะแก้ปัญหานี้ด้วยสองวิธี:แบบเรียกซ้ำและแบบวนซ้ำ
แนวทางแบบเรียกซ้ำ
ในสูตรนี้ เราจะใช้สูตร Pell Number ซ้ำๆ และทำซ้ำ n
ตัวอย่าง
#include <iostream>
using namespace std;
int pell(int n) {
if(n <= 2)
return n;
return 2*pell(n-1) + pell(n-2);
}
int main() {
int n = 6; // given n
cout << pell(n) <<"\n"; // Pell number at that position.
return 0;
} ผลลัพธ์
70
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เราใช้การเรียกซ้ำโดยเรียก pell(n-1) &&pell(n-2) จนกระทั่ง n มีค่าน้อยกว่าหรือเท่ากับ 2 เนื่องจากเราทราบดีว่าตัวเลข pell จนถึง 2 จะเหมือนกับตัวเลขที่ระบุ ความซับซ้อนของเวลาโดยรวมของโปรแกรมข้างต้นคือ O(N) โดยที่ N คือตัวเลขที่กำหนด
แนวทางการทำซ้ำ
ในแนวทางนี้ เราจะใช้สูตรเดียวกับด้านบน แต่คำนวณตัวเลขโดยใช้ for loop แทนฟังก์ชันแบบเรียกซ้ำ
ตัวอย่าง
#include <iostream>
using namespace std;
int main() {
int n = 6; // given n.
int p0 = 0; // initial value of pn-2.
int p1 = 1; // initial value of pn-1.
int pn; // our answer.
if(n <= 2) // if n <= 2 we print n.
cout << n <<"\n";
else {
for(int i = 2; i <= n; i++) { // we are going to find from the second number till n.
pn = 2*p1 + p0;
p0 = p1; // pn-1 becomes pn-2 for new i.
p1 = pn; // pn becomes pn-1 for new i.
}
cout << pn << "\n";
}
return 0;
} ผลลัพธ์
70
คำอธิบายของโค้ดด้านบน
ในโปรแกรมที่กำหนด เรากำลังข้ามจาก 2 ถึง n และเพียงอัปเดตค่าสำหรับ pn-2 เป็น pn-1 และ pn-1 เป็น pn จนถึง n
บทสรุป
ในบทความนี้ เราแก้ปัญหาในการค้นหาเลขลำดับที่ N โดยใช้การเรียกซ้ำและการวนซ้ำ นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ
