حل LeetCode عدد فیبوناچی

سطح دشواری ساده
اغلب در خشت آمازون سیب بلومبرگ ای بی فیس بوک گلدمن ساکس گوگل Infosys در جی پی مورگان کارهای ریاضی مایکروسافت کارت گرافیک Nvidia وحی SAP حال بارگذاری آموزش VMware Zillow
بزرگنمایینمایش ها 215

بیان مسأله

حل LeetCode شماره فیبوناچی - "شماره فیبوناچی" بیان می کند که The اعداد فیبوناچی، معمولاً نشان داده می شود F(n) دنباله ای به نام the دنباله فیبوناچی، به طوری که هر عدد از مجموع دو عدد قبل شروع می شود 0 و 1. به این معنا که،

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

داده n، محاسبه F(n).

حل LeetCode عدد فیبوناچی

به عنوان مثال 1:

ورودی:

 n = 2

خروجی:

 1

شرح:

 F(2) = F(1) + F(0) = 1 + 0 = 1.

به عنوان مثال 2:

ورودی:

 n = 3

خروجی:

 2

شرح:

 F(3) = F(2) + F(1) = 1 + 1 = 2.

به عنوان مثال 3:

ورودی:

 n = 4

خروجی:

 3

شرح:

 F(4) = F(3) + F(2) = 2 + 1 = 3.

روش

ایده:

مشاهدات اصلی این است که هر F(i) به مجموع F(i-1) و F(i-2) بستگی دارد. بنابراین می‌توانیم دو متغیر بگیریم که مقدار اولیه را ذخیره می‌کنند، سپس تا N تکرار می‌کنیم تا به نتیجه برسیم.

توضیح

  • N==0: برگرداندن 0
  • N==1: برگرداندن 1
  • پیش فرض: بازگشت fib(N-1) + fib(N-2)

بیایید در مورد صحبت کنیم رویکرد دوم:

با در نظر گرفتن دنباله [34,55,89،XNUMX،XNUMX] می توانیم a را ببینیم الگو یعنی اگر هر دو عبارت متوالی را تقسیم کنیم بخش منجر به یک عدد یکسان نزدیک به 1.618 به نام نسبت طلایی. در واقع ما فرمول انجام این کار را داریم! تماس گرفت فرمول بینه.

باشه؟ چگونه می توانیم از این چیز طلایی استفاده کنیم! 34 هست 9th اصطلاح، اگر ما پیدا کنیم pow(golden,Nth term)/sqrt(5) محصور با a دور تابع، مقدار ترم N را در آن دریافت می کنیم O(1) زمان و مکان!

رمز

کد C++ شماره فیبوناچی

class Solution {
public:
    int fib(int n) {
        if(n==0)
            return 0;
        if (n==1)
            return 1;
        int a=0,b=1,c;
        for(int i=1;i<n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
        
    }
};

برنامه جاوا شماره فیبوناچی

class Solution {
    public int fib(int n) {
        if(n==0)
            return 0;
        if (n==1)
            return 1;
        int a=0,b=1,c=0;
        
        for(int i=1;i<n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
        
    }
}

تجزیه و تحلیل پیچیدگی برای حل LeetCode عدد فیبوناچی

پیچیدگی زمان

بر)

پیچیدگی فضا

O (1)

Translate »