הדפיסו את מספרי פיבונאצ'י בסדר הפוך


רמת קושי קַל
נשאל לעתים קרובות אקסנצ'ר מאק פתרונות o9 UHG אופטום
תכנות דינמי רצף

הצהרת בעיה

בהתחשב במספר n, הדפס את מספרי פיבונאציים בסדר הפוך.

דוגמה

n = 5
3 2 1 1 0

הסבר: מספרי פיבונאצ'י הם 0, 1, 1, 2, 3 לפי הזמנתם. אבל מכיוון שהיינו צריכים להדפיס בסדר הפוך.

n = 7
8 5 3 2 1 1 0

הדפיסו את מספרי פיבונאצ'י בסדר הפוך

האיור מציין כיצד מספרי פיבונאצ'י תלויים בתוצאה של 2 המספרים האחרונים של פיבונאצ'י.

אַלגוֹרִיתְם

  1. קח קלט, מספר האלמנטים שיש להדפיס.
  2. הכריז על מערך בגודל ככניסה של הקלט הנתון.
  3. אתחל את אינדקס המערך 0 ו -1 עם 0 ו -1.
  4. אנו מתחילים להריץ לולאה מ- i = 2, עד שהערך של i קטן מ- n תוך הגדלת הערך של i אחד אחד.
    1. המשך לשמור את התוספת של אלמנט האינדקס האחרון ואלמנט האינדקס האחרון.
  5. כעת הדפיסו מערך זה בסדר הפוך.

גישה

גישה נאיבית להדפסת מספרי פיבונאצ'י הייתה תמיד רקורסיה. ובכל פעם שמספרים לנו על רקורסיה, הדבר הראשון שבדרך כלל מספרים לנו עליו הם מספרים של פיבונאצ'י. לכן, באמצעות רקורסיה אנו יכולים למצוא את מספרי פיבונאצ'י. ואז פשוט הדפיסו בסדר הפוך. אך לשם כך נדרש חישוב כבד, ולכן במקום לעשות זאת עלינו לחשוב על גישה חלופית.

הגישה האלטרנטיבית היא תכנות דינמי, שם אנו מאחסנים את הנתונים הנדרשים לעיתים קרובות יותר בפתרון הבעיה. דנו גם במציאת מספרים פיבונאציים באמצעות תכנות דינמי בקודם פוסט.

קופונים

קוד C ++ להדפסת מספרים פיבונאליים בסדר הפוך

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

int main()
{
    int n;cin>>n;
    int fib[n];
    if(n>=1)
    fib[0] = 0;
    if(n>=2)
    fib[1] = 1;
    for(int i=2;i<n;i++)
        fib[i] = fib[i-1] + fib[i-2];
    for(int i=n-1;i>=0;i--)
        cout<<fib[i]<<" ";
}
4
2 1 1 0

קוד Java להדפסת מספרי פיבונאציים בסדר הפוך

import java.util.*;
class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    	int fib[] = new int[n];
    	if(n>=0)
    		fib[0] = 0;
    	if(n>=1)
    		fib[1] = 1;
    	for(int i=2;i<n;i++)
    		fib[i] = fib[i-1] + fib[i-2];
    	for(int i=n-1;i>=0;i--)
    		System.out.print(fib[i]+" ");
  	}
}
4
2 1 1 0

ניתוח מורכבות

מורכבות זמן

O (N), זמן זה נדרש לחישוב מספרי פיבונאצי. מכיוון שאנחנו פשוט מפעילים לולאה אחת כדי למצוא את רצף פיבונאצי. מורכבות הזמן היא לינארית.

מורכבות בחלל

O (N), מכיוון שהשתמשנו במערך לאחסון ערכי מספרים פיבונאציים, מורכבות החלל היא ליניארית.