فبونیکی نمبر


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایپل DBOI گوگل انفوسس جے پی مورگن میک o9 حل SAP لیبز
ریاضی تسلسل

فبونیکی اعداد وہ نمبر ہیں جو سیریز کو تشکیل دیتے ہیں جسے فبونیکی سیریز کہا جاتا ہے اور ان کی نمائندگی ایف کے طور پر کی جاتی ہےn. پہلے دو فبونیکی اعداد بالترتیب 0 اور 1 ہیں F0= 0 اور ایف1=1. تیسری فبونیکی نمبر سے شروع کرنا ہر ایک فبونیکی نمبر سیریز میں اس کے پچھلے دو نمبروں کا مجموعہ ہے۔

Fn = ایفاین 1 + ایفاین 2

فبونیکی سیریز - 0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ……

ایک عدد دی n. نویں فبونیکی نمبر تلاش کریں۔

مثال کے طور پر

ان پٹ: n = 5

: پیداوار 5

ان پٹ: n=9

: پیداوار 34

تکرار کرنے کا طریقہ

الگورتھم

  1. شروع کریں a متغیر n.
  2. بیس کیس - اگر n 1 کے برابر XNUMX ریٹرن سے کم ہے.
  3. تکرار کرنے والا کیس - ریٹرن fn (n-1) + fn (n-2)۔

وقت کی پیچیدگی: O (1.6180)n     (1.6180 کو سنہری تناسب بھی کہا جاتا ہے)

خلائی پیچیدگی: O (1)

فبونیکی نمبروں کے لئے سی ++ پروگرام

#include<bits/stdc++.h> 
using namespace std; 
  
int fn(int n){ 
    if(n<=1) 
        return n; 
    return fn(n-1) + fn(n-2); 
} 
  
int main (){ 
    int n=6; 
    cout<<fn(n); 
    return 0; 
}
Output :
8

Fibonacci نمبروں کے لئے جاوا پروگرام

class fibNumbers{ 
    static int fn(int n){ 
        if(n<=1) 
           return n; 
        return fn(n-1) + fn(n-2); 
    } 
       
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output : 
8

مذکورہ بالا کوڈ کے لئے درخت کو بار بار لگائیں

فبونیکی نمبر

ہم اوپر والے درخت سے دیکھ سکتے ہیں کہ کچھ افعال کو ایک سے زیادہ دفعہ کہا جاتا ہے۔ 

متحرک پروگرامنگ کا طریقہ

اوپر کی طرح ایک ہی افعال کی دوبارہ گنتی سے ڈی پی کے استعمال سے گریز کیا جاسکتا ہے۔

الگورتھم

  1. فبونیکی اعداد کو ذخیرہ کرنے کے لئے متغیر ن اور ایک سرنی F کا آغاز کریں۔
  2. صف کے پہلے دو عناصر کو بالترتیب 0 اور 1 کے طور پر شروع کریں ..
  3. ایک ایک کرکے 2 سے شروع ہونے تک تمام اقدار کو عبور کریں اور صف میں پچھلے دو عناصر کے جوہر کے بطور سرنی والے اقدار کو اپ ڈیٹ کریں۔
  4. واپسی f [n]

وقت کی پیچیدگی: اے (ن)     

خلائی پیچیدگی: اے (ن)

فبونیکی نمبروں کے لئے سی ++ پروگرام

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

int fn(int n){ 
  int f[n+2];
  
  f[0] = 0; 
  f[1] = 1; 
  
  for(int i=2; i<=n; i++){ 
      f[i] = f[i-1] + f[i-2]; 
  } 
  
  return f[n]; 
} 
  
int main (){ 
  int n = 6; 
  cout<<fn(n);
  return 0; 
}
Output : 
8

Fibonacci نمبروں کے لئے جاوا پروگرام

class fibNumbers{ 
    static int fn(int n){ 
        int[] f = new int[n+2]; 
        
        f[0] = 0; 
        f[1] = 1; 
        
        for(int i=2; i<=n; i++){ 
            f[i] = f[i-1] + f[i-2]; 
        } 
        
        return f[n]; 
    } 
    
  
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output : 
8

مزید جگہ سے بہتر طریقہ

الگورتھم

  1. تین متغیر x = 0 ، y = 1 ، z شروع کریں۔
  2. تمام اقدار کو ن 2 تک ایک ایک کرکے شروع کریں اور z اور x اور y ، x = y ، اور y = z کے جوہر کے طور پر تازہ کاری کریں۔
  3. واپس y

وقت کی پیچیدگی: اے (ن)     

خلائی پیچیدگی: O (1)

فبونیکی نمبروں کے لئے سی ++ پروگرام

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

int fn(int n){ 
    int x=0, y=1, z;
    
    for(int i=2; i<=n; i++){ 
        z = x + y;
        x = y;
        y = z;
    } 
    
    return y; 
} 

int main (){ 
    int n = 6; 
    cout<<fn(n);
    return 0; 
}
Output :
8

Fibonacci نمبروں کے لئے جاوا پروگرام

class fibNumbers{ 
    static int fn(int n){ 
        int x=0, y=1, z; 
        if(n == 0) 
            return x; 
        for(int i=2; i<=n; i++){ 
            z = x + y; 
            x = y; 
            y = z; 
        } 
        return y; 
    } 
  
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output :
8

براہ راست فارمولہ کا استعمال

یہاں ہم نویں فبونیکی نمبر یعنی تلاش کرنے کے لئے براہ راست فارمولہ استعمال کریں گے

Fn = ((((( (5 + 1) / 2) . n) / 5)

وقت کی پیچیدگی: O (1)     

خلائی پیچیدگی: O (1)

سی ++ پروگرام

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

int fn(int n){ 
    double gr = (1 + sqrt(5)) / 2; 
    return round(pow(gr, n) / sqrt(5)); 
} 

int main (){ 
    int n = 6; 
    cout<<fn(n);
    return 0; 
}
Output :
8

جاوا پروگرام

import java.util.*;

class fibNumbers{ 
    static int fn(int n){ 
        double gr = (1 + Math.sqrt(5)) / 2; 
        return (int) Math.round(Math.pow(gr, n) / Math.sqrt(5));
    } 
    
    public static void main (String args[]){ 
        int n = 6; 
        System.out.println(fn(n)); 
    } 
}
Output :
8

حوالہ

انٹرویو سوالات