دنباله پادوان در سی پلاس پلاس (Padovan Sequence)

در این جلسه تیم کدگیت را با آموزش دنباله پادوان در سی پلاس پلاس همراهی کنید. دنباله پادوان یکی از دنباله‌های مشابه با سری فیبوناچی می‌باشد اما شروط پایه این دو متفاوت است. این آموزش به توضیح دنباله پادوان پرداخته سپس این دنباله را در سی پلاس پلاس پیاده سازی می‌کنیم. پیش‌نیازهای این آموزش به صورت زیر می‌باشد:

1. توابع در سی پلاس پلاس
2. حلقه for در سی پلاس پلاس
3. Static در سی پلاس پلاس

دنباله پادوان

قبل از پیاده سازی دنباله پادوان توضیح مختصری در مورد این دنباله می‌دهیم. دنباله پادوان بسیار شبیه به سری فیبوناچی است و در شرط پایه با یکدیگر متفاوت هستند. فرمول این دنباله به صورت زیر است:

P(n) = P(n-2) + P(n-3)

P(0) = P(1) = P(2) = 1

حال فرض کنید n=3 باشد پس فرمول بالا به صورت زیر تغییر می‌کند.

P(3) = P(1) + P(0) = 2

برای n = 4 به همین ترتیب محاسبه می‌کنیم:

P(4) = P(2) + P(1) = 2

به طور کلی اعداد دنباله پادوان به صورت زیر می‌باشد:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37,…

دنباله پادوان در سی پلاس پلاس

برای پیاده‌سازی دنباله پادوان ما از یک تابع استفاده کردیم. در این تابع سه عدد قبل دنباله را درون سه متغیر (pPrevPrev، pPrev، pCurr) ذخیره می‌کنیم. با استفاده از این سه متغیر عدد بعدی دنباله را پیدا می‌کنیم. ورودی تابع ما همان n در فرمول بالا است(عددی که میخواهیم دنباله آن را پیدا کنیم). کد این تابع به صورت زیر است:

int pad(int n)
{
    int pPrevPrev = 1, pPrev = 1, pCurr = 1, pNext = 1;

    for (int i=3; i<=n; i++)
    {
        pNext = pPrevPrev + pPrev;
        pPrevPrev = pPrev;
        pPrev = pCurr;
        pCurr = pNext;
    }

    return pNext;
}

برای استفاده از کد بالا باید یک Main به صورت زیر بنویسیم:

int main() {
    int n = 12;
    cout << pad(n);
	return 0;
}

خروجی کد بالا عدد 21 است.