تمرین دنباله فیبوناچی برگشتی

تمرین دنباله فیبوناچی برگشتی

در این نوشته تمرین “دنباله فیبوناچی به صورت برگشتی” که در وبسایت کوئرا موجود است را برای شما کاربران عزیز حل کردیم. (پیشنهاد کاربر: aarezo531)

تمرین دنباله فیبوناچی برگشتی

سوال: برنامه‌ای بنویسید که به ازای دریافت جملات Nام و N+1ام از دنباله فیبوناچی (با فرض A_0 = A_1 = 1 ) و ارسال این دو به تابعی با امضای

void ShowFibNth(long int n, long int n+1)

جملات سری فیبوناچی را از جمله Nام تا صفرم را به صورت معکوس چاپ کند. توجه کنید که تابع مذکور در هر بار فراخوانی خود، وظیفه چاپ پارامتر اول و فراخوانی مجدد خود (به صورت بازگشتی) را خواهد داشت. بدیهی است که استفاده از حلقه غیرمجاز است.

پیشنهاد نویسنده‌: الگوریتم فیبوناچی با پایتون

ورودی تمرین دنباله‌ی فیبوناچی

در خط اول جمله n ام و در خط بعد عدد n + 1 ام به شما داده می‌شود. اعداد از 1 تا 1000000 کوچک‌ترند.

خروجی تمرین دنباله‌ی فیبوناچی

جملات فیبوناچی را به ترتیب چاپ کنید.

مثال تمرین دنباله‌ی فیبوناچی

Sample 1:
============================================
input :
5
8
output :
5
3
2
1
1


Sample 2:
============================================
input :
1
1
output :
1

کد تمرین

import java.util.Scanner;

class Main {

    static Scanner sc;

    public static void main(String[]args){
        sc = new Scanner(System.in);
        int N, N1;
        N = sc.nextInt();
        N1 = sc.nextInt();
        ShowFibNth(N, N1);
    }

    public static void ShowFibNth(int N, int N1) {
        if(N==0)
            return;
        System.out.println(N);
        int new_n = N1 - N;
        ShowFibNth(new_n, N);
    }

}

روش حل تمرین دنباله‌ی فیبوناچی

یک تابع با نام ShowFibNth را تعریف می‌کنیم.در این تابع ابتدا بررسی می‌کنیم که مقدار عدد اول ورودی به این تابع صفر نبوده، در صورت صفر بودن تابع پایان می‌یابد. در صورتی که از شرط بالا برنامه رد شود مقدار N که عدد اول ورودی به تابع است چاپ می‌شود. در خط بعدی عدد قبلی دنباله فیبوناچی یافت می‌شود این عدد از کم کردن عدد دوم از عدد اول بدست می‌آید. در آخر هم برای فراخوانی بعدی مقدارها را وارد تابع می‌کنیم و به صورت برگشتی تابع را فراخوانی می‌کنیم. اگر الگوریتم کار دنباله ی فیبوناچی را نمی‌دانید در این لینک آن را بخوانید.

منبع سوال: وبسایت کوئرا

اگر روش حل بهتری دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم. اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در اولویت محتوای سایت بگذاریم.