จำนวนมอทซ์คิน (Motzkin number) ใน C++

โจทย์

ลำดับจำนวนมอทซ์คินเริ่มต้นด้วย 1, 1, 4, 9 เป็นต้น เราสามารถหาพจน์ทั่วไปลำดับที่ n ได้จากลำดับนี้ ลำดับจำนวนมอทซ์คินมีดังนี้

a₀ = 1

a₁ = 1

a₂ = 4

a₃ = 9

a_n = ((2 * n + 1)/ n + 2) * M_(n-1) +((3 * n - 3)/ n + 2) * M_{(n - 2)}

อัลกอริธึม

กำหนดตัวเลข n
วนลูปจนถึง n
- อัปเดตตัวเลขก่อนหน้าสองตัว
คืนค่าตัวเลขสุดท้าย

ตัวอย่าง

การนำไปใช้งาน

ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน C++

#include <bits/stdc++.h> 
using namespace std; 

int getNthTerm(int n) { 
    if(n == 0 || n == 1) { 
        return 1; 
    } 
    int a = 1, b = 1; 
    for(int i = 2; i <= n; ++i) { 
        int c = ((2 * i + 1) * b + (3 * i - 3) * a) / (i + 2); 
        a = b; 
        b = c; 
    } 
    return b; 
} 

int main() { 
    int n = 5; 
    cout << getNthTerm(n) << endl; 
    return 0; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้