اطبع تسلسل فيبوناتشي باستخدام متغيرين


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون التسليم مجموعة الحقائق فوركايتس رفع MAQ o9 الحلول PayU
البرمجة الديناميكية فيبوناتشي تسلسل

المشكلة بيان

تشير مشكلة "طباعة تسلسل فيبوناتشي باستخدام متغيرين" إلى أنك بحاجة إلى طباعة تسلسل فيبوناتشي ولكن هناك قيود على استخدام متغيرين فقط.

مثال

اطبع تسلسل فيبوناتشي باستخدام متغيرين

n = 5
0 1 1 2 3 5

تفسير

يحتوي تسلسل الإخراج على العناصر الخمسة الأولى من سلسلة فيبوناتشي.

الرسالة

يتم تزويدنا بعنصر واحد كمدخل ، والذي يخبرنا بعدد العناصر التي يجب إنتاجها من تسلسل فيبوناتشي. لذا فإن الطريقة الساذجة لطباعة متوالية فيبوناتشي هي العودية. ثم يمكننا استخدام حلقة تستدعي الدالة العودية لحساب كل رقم فيبوناتشي. لكن هذا النهج يتطلب وقتًا أسيًا ، وبالتالي نحتاج إلى شيء أكثر كفاءة.

يمكننا التفكير في البرمجة الديناميكية/ حفظ المشكلة. هذا النهج سيقلل بالتأكيد من تعقيد الوقت. سيتم تقليل التعقيد الزمني الأسي إلى تعقيد زمني خطي. لكن هذا النهج لا يزال يتطلب منا تعقيدًا خطيًا للفضاء. نحن بحاجة إلى تقليل هذا التعقيد المكاني أكثر. ما يمكننا القيام به هو محاولة تحسين البرمجة الديناميكية النهج.

إذا رأينا الصيغة العودية ، F (n) = F (n-1) + F (n-2). نحن نعتمد فقط على آخر رقمين فيبوناتشي. وبالتالي يمكننا فقط تخزين آخر رقمين فيبوناتشي للعثور على الرقم الحالي وهذا يجعل الخوارزمية تعمل في O (1) الفضاء التعقيد.

رمز

كود C ++ لطباعة تسلسل فيبوناتشي باستخدام متغيرين

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

int main()
{
    int n;cin>>n;
    int last = 1, lastToLast = 0;
    if(n>=0)
        cout<<lastToLast<<" ";
    if(n>=1)
        cout<<last<<" ";
    for(int i=2;i<=n;i++){
        int cur = last + lastToLast;
        cout<<cur<<" ";
        lastToLast = last;
        last = cur;
    }
}
5
0 1 1 2 3 5

كود جافا لطباعة تسلسل فيبوناتشي باستخدام متغيرين

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

تحليل التعقيد

تعقيد الوقت

O (N) لأننا اجتازنا فقط حتى عدد العناصر التي نحتاجها للطباعة. أولاً ، فكرنا في حل المشكلة باستخدام العودية ولكن ذلك كان أسيًا في الوقت المناسب. ثم قللنا من تعقيد وقتنا عندما استخدمناه البرمجة الديناميكية. وبسبب ذلك تمكنا من حل المشكلة في الوقت الخطي.

تعقيد الفضاء

يا (1) ،  لقد حللنا مشكلة التعقيد المكاني الثابت لأننا استخدمنا متغيرين فقط.