سکانس فیبوناچی سوال مصاحبه JavaScript. راه حل های تکراری و بازگشتی.

"نوشتن یک تابع برای بازگشت یک عنصر N در دنباله فیبوناچی" یکی از متداول ترین سؤالاتی است که می توانید در قسمت مصاحبه چالش برنامه نویسی بشنوید. در این وبلاگ من قصد دارم دو راه حل معمولی برای این مشکل را طی کنم و همچنین یک موضوع وحشتناک (برای اکثر توسعه دهندگان تازه کار) از پیچیدگی زمان را پوشش دهم.

بنابراین دنباله فیبوناچی چیست؟طبق ویکی پدیا:

"در ریاضیات ، اعداد فیبوناچی اعداد موجود در توالی عدد صحیح زیر است که دنباله فیبوناچی نامیده می شود و با این واقعیت مشخص می شود که هر عدد بعد از دو اول مجموع دو مورد قبلی است."

بسته به نقطه شروع انتخاب شده دنباله (0 یا 1) دنباله به این شکل است:

1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89 ، 144 ،…

0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89 ، 144 ،…

واقعیت جالب: دنباله فیبوناچی ، که به عنوان نسبت طلایی نیز شناخته می شود ، از نظر طبیعت زیادی به نظر می رسد. الگوهای مانند مارپیچ پوسته ها ، منحنی امواج ، سر بذر ، پینکون ها و شاخه های درختان همه با استفاده از این دنباله ریاضی قابل توصیف هستند. این واقعیت که چیزهایی به اندازه مارپیچ های کهکشان ها و به اندازه مولکولهای DNA کوچک از قانون نسبت طلایی پیروی می کنند ، نشان می دهد که توالی فیبوناچی یکی از اساسی ترین ویژگی های جهان است.

خوب ، اکنون به زمین و چالش برنامه نویسی توالی فیبوناچی ما بازگشت. بیایید به سرعت یک مورد آزمایشی را برای عملکرد FIB () ما شرح دهیم. اگر بخواهیم یک دنباله فیبوناچی کوتاه داشته باشیم: [0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21] و FIB (4) ، نتیجه آن برابر با 3 خواهد بود ، بنابراین اساساً ما باید برگردیمعنصر با فهرست 4 از آرایه توالی فیبوناچی ما.

یکی از ممکن و احتمالاً ساده ترین راه حل که در اینجا به ذهن متبادر می شود ، تکرار است. بیایید ببینیم که چگونه به نظر می رسد:

بنابراین توجه کنید که دو شماره اول واقعاً نمی توانند توسط یک حلقه برای یک حلقه ایجاد شوند ، زیرا حلقه ما شامل اضافه کردن دو عدد به هم خواهد بود ، بنابراین به جای ایجاد یک آرایه خالی ، متغیر ARR خود را به [0 ، 1] اختصاص می دهیم که ما می دانیمواقعیت همیشه در آنجا خواهد بود. پس از آن حلقه ای ایجاد می کنیم که از I = 2 شروع می شود و اعداد را به آرایه اضافه می کند تا طول آرایه برابر با N + 1 باشد. سرانجام ، شماره را در فهرست N آرایه باز می گردانیم.

عالی ، به نظر می رسد که این کار می کند. حال اگر مصاحبه کننده شما فکر کند این کافی نیست و از شما می خواهد یک راه حل بازگشتی اجرا کنید ، چه می شود؟

اگرچه راه حل بازگشتی بسیار ساده به نظر می رسد ، اگر قبلاً هرگز با آن روبرو نشده اید ، رسیدن به آن بسیار دشوار است:

بنابراین ، پرونده پایه ما در اینجا در حال بازگشت است اگر ارزش آن کمتر باشد. FIB عملکرد با آرگومان 5 خوانده می شود:

اساساً عملکرد FIB ما همچنان به صورت بازگشتی به خود می آید و بیشتر و بیشتر شاخه های درخت را ایجاد می کند تا زمانی که به مورد پایه برخورد کند ، از این طریق شروع به جمع بندی مقادیر بازگشت هر شاخه در پایین به بالا خواهد کرد ، تا اینکه در نهایت آنها را خلاصه کرد و یک عدد صحیح را برمی گرداندبرابر با 5. ممکن است لحظه ای غرق شود ، بنابراین مدتی را به درخت نگاه کنید و خواهید فهمید که در آنجا چه اتفاقی می افتد.

برای دنباله فیبوناچی ، یادگیری جاوا اسکریپت بسیار توصیه می شود. اکنون که ما این دو راه حل مشترک را برای این مشکل پوشش دادیم ، بیایید در مورد پیچیدگی زمان صحبت کنیم.

به عنوان مثال برخی از محیط های آزمایش ، مانند شوخی ، نشان می دهد که مدت زمان زیادی برای سرگرمی عملکرد شما در میلی ثانیه طول کشید. با فرض اینکه ما برای این چالش تست هایی از قبل نوشته شده بودیم ، این همان چیزی است که نتایج به دنبال آن خواهد بود:

راه حل تکراری:

راه حل بازگشتی:

اکنون به پرونده ای نگاه کنید که ما با n = 15 تماس می گیریم. راه حل تکراری 4ms طول کشید ، اما برای انجام همان عمل ، راه حل بازگشتی 1328ms طول کشید. چرا این است؟

یک الگوریتم در راه حل تکراری ما برای تکمیل کار زمان خطی می گیرد. در اصل ما از طریق حلقه n-2 تکرار می کنیم ، بنابراین بزرگ O (نماد مورد استفاده برای توصیف بدترین سناریوی ما) در این مورد به سادگی با N برابر خواهد بود.

در صورت بازگشت ، راه حل زمان نمایی را می گیرد ، می توان با این واقعیت توضیح داد که اندازه درخت با افزایش N به صورت نمایی رشد می کند. بنابراین برای هر عنصر اضافی در دنباله فیبوناچی ، ما در تماس های عملکردی افزایش می یابیم. در این حالت Big O برابر با 2^n است.

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