การหาเลข Pell ด้วย C++

ในปัญหาที่กำหนด เราได้รับจำนวนเต็ม n เราต้องหา P_n คือ เลข Pell ในตำแหน่ั้นั้น ตอนนี้ เรารู้ว่าเลข Pell เป็นส่วนหนึ่งของอนุกรมที่กำหนดโดยสูตรนี้:

P_n = 2×P_n-1 + P_n-2

ด้วยตัวเลขเริ่มต้นสองตัว:

P₀ = 0 และ P₁ = 1

วิธีการแก้ปัญหา

ตอนนี้เราจะแก้ปัญหานี้ด้วยสองวิธี: แบบ Recursive (เรียกซ้ำ) และ Iterative (วนซ้ำ)

วิธี Recursive (เรียกซ้ำ)

ในสูตรนี้ เราจะนำสูตรของเลข Pell ไปใช้แบบเรียกซ้ำ และทำ 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; // n ที่กำหนด
    cout << pell(n) << "\n"; // เลข Pell ในตำแหน่ั้นั้น
    return 0;
}

ผลลัพธ์

70

คำอธิบายโค้ด

ในวิธีนี้ เราใช้การเรียกซ้ำโดยเรียก pell(n-1) && pell(n-2) จนกว่า n จะน้อยกว่าหรือเท่ากับ 2 เนื่องจากเรารู้ว่าเลข Pell จนถึง 2 เท่ากับตัวเลขที่กำหนด ความซับซ้อนด้านเวลาทั้งหมดของโปรแกรมข้างต้นคือ O(N) โดยที่ N คือตัวเลขที่กำหนด

วิธี Iterative (วนซ้ำ)

ในวิธีนี้ เราจะใช้สูตรเดียวกับข้างต้น แต่คำนวณตัวเลขโดยใช้ for loop แทนฟังก์ชันเรียกซ้ำ

ตัวอย่าง

#include <iostream>
using namespace std;

int main() {
    int n = 6; // n ที่กำหนด
    int p0 = 0; // ค่าเริ่มต้นของ pn-2
    int p1 = 1; // ค่าเริ่มต้นของ pn-1
    int pn; // คำตอบของเรา
    
    if(n <= 2) // ถ้า n <= 2 เราพิมพ์ n
        cout << n << "\n";
    else {
        for(int i = 2; i <= n; i++) { // เราจะหาตั้งแต่ตัวที่สองจนถึง n
            pn = 2*p1 + p0;
            p0 = p1; // pn-1 กลายเป็น pn-2 สำหรับ i ใหม่
            p1 = pn; // pn กลายเป็น pn-1 สำหรับ i ใหม่
        }
        cout << pn << "\n";
    }
    return 0;
}

ผลลัพธ์

70

คำอธิบายโค้ด

ในโปรแกรมที่กำหนด เรากำลังเดินทางจาก 2 ถึง n และเพียงแค่อัปเดตค่าสำหรับ pn-2 เป็น pn-1 และ pn-1 เป็น pn จนกว่าจะถึง n

สรุป

ในบทความนี้ เราแก้ปัญหาการหาเลข Pell ตัวที่ N โดยใช้การเรียกซ้ำและการวนซ้ำ เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ธรรมดาและมีประสิทธิภาพ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้