اگر می خواهید کدنویسی را یاد بگیرید، باید الگوریتم ها را یاد بگیرید. الگوریتم های یادگیری با آشکار کردن الگوهای طراحی در برنامه نویسی، مهارت های حل مسئله شما را بهبود می بخشد. در این آموزش شما یاد خواهید گرفت که چگونه دنباله فیبوناچی بازگشتی را در جاوا اسکریپت کدنویسی کنید و پایتون.
این مقاله در ابتدا در jarednielsen.com منتشر شده است
نحوه کدگذاری الگوریتم فیبوناچی بازگشتی
برنامه نویسی حل مسئله است. برای حل هر مشکل برنامه نویسی باید چهار مرحله را طی کنیم:
-
مشکل را درک کنید
-
ایجاد یک طرح
-
طرح را اجرا کنید
-
طرح را ارزیابی کنید
مشکل را درک کنید
برای درک مشکل خود ابتدا باید آن را تعریف کنیم. بیایید دوباره مشکل را به عنوان معیار پذیرش در نظر بگیریم:
GIVEN a number, _n_
WHEN I call a recursive Fibonacci function
THEN I am returned the _nth_ member of the Fibonaccis sequence
این طرح کلی ماست. ما شرایط ورودی خود را می دانیم، یک عدد صحیح nو الزامات خروجی ما، نهمین عضوی از دنباله فیبوناچی است و هدف ما محاسبه بازگشتی آن است.
بیایید برنامه ریزی کنیم!
ایجاد یک طرح
بیایید اکتشافات تفکر محاسباتی خود را مجدداً مرور کنیم زیرا آنها در ساختن یک برنامه کمک می کنند و راهنمایی می کنند. آن ها هستند:
-
تجزیه
-
الگو شناسی
-
انتزاع – مفهوم – برداشت
-
طراحی الگوریتم
اولین گام تجزیه، یا تجزیه مشکل ما به مشکلات کوچکتر است. کوچکترین مشکلی که می توانیم حل کنیم چیست؟
0
اگر n برابر 0 است، عدد فیبوناچی معادل چیست؟
0
بیایید 10 عدد اول را ترسیم کنیم تا هدف را روشن کنیم.
| n | نهمین |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
بیایید شبه/هاردکد 0 کنیم:
FUNCTION fibonacci
INPUT n
IF n IS EQUAL TO 0
RETURN n
کوچکترین مشکل بعدی چیست؟
1
اگر به جدول بالا مراجعه کنیم، می بینیم که نتیجه n = 1 بر خواهد گشت 1. ما به سادگی می توانیم این را به شرطی خود اضافه کنیم:
FUNCTION fibonacci
INPUT n
IF n IS EQUAL TO 0 OR n IS EQUAL TO 1
RETURN n
سلام! به آن نگاه کنید. ما فقط پرونده پایه خود را ایجاد کردیم. حال باید حالت بازگشتی خود را تعریف کنیم.
بیایید به کوچکترین مشکل بعدی نگاه کنیم، 2.
اگر ورودی ما باشد 2، انتظار داریم مقدار بازگشتی چقدر باشد؟
1
چگونه به آن برسیم 1 در دنباله فیبوناچی؟ این مجموع دو عدد قبلی 0 و 1 است.
اگر ورودی ما باشد 3، انتظار داریم مقدار بازگشتی چقدر باشد؟
2
چگونه در دنباله فیبوناچی به عدد 2 برسیم؟ این مجموع دو عدد قبلی 1 و 1 است.
اگر ورودی ما 4 باشد، انتظار داریم مقدار بازگشتی چقدر باشد؟
3
به منظور برگرداندن مقدار 3 when n برابر 4 است، می دانیم که باید 1 و 2 را جمع کنیم، اعدادی که در دنباله فیبوناچی قبل از 3 هستند.
آیا الگو را می بینید؟
ممکن است وسوسه شوید که بگویید این ساده است n - 1، اما اگر ورودی ما 5 باشد چه؟ انتظار داریم ارزش بازگشتی چقدر باشد؟
نه 4.
5 است!
به منظور برگرداندن مقدار 5 when n برابر با 5 است، می دانیم که باید 2 و 3 را جمع کنیم، اعدادی که در دنباله فیبوناچی قبل از 5 هستند.
اگر تابع فیبوناچی خود را فراخوانی کنیم f() به طور خلاصه می دانیم که:
f(5) = 3 + 2
و…
f(4) = 2 + 1
و…
f(3) = 1 + 1
و…
f(2) = 1 + 0
و f(1) مورد پایه ما است زیرا دو عدد قبلی برای رسیدن به این مقدار وجود ندارد.
آیا الگو را می بینید؟
f(5) = f(4) + f(3)
و…
f(4) = f(3) + f(2)
و…
f(3) = f(2) + f(1)
به عبارت دیگر…
f(5) = (f(3) + f(2)) + (f(2) + f(1))
و غیره…
اکنون می‌توانیم به انتزاع جهش کنیم: فیبوناچی بازگشتی یا f() از n را می توان به صورت بیان کرد f(n – 1) + f (n – 2). ما می توانیم این را به شبه کد ترجمه کنیم:
FUNCTION fibonacci
INPUT n
IF n IS EQUAL TO 0 OR n IS EQUAL TO 1
RETURN n
RETURN fibonacci(n - 1) + fibonacci(n - 2)
طرح را اجرا کنید
اکنون فقط موضوع ترجمه شبه کد ما به نحو زبان برنامه نویسی ما است.
نحوه کدگذاری الگوریتم فیبوناچی بازگشتی در جاوا اسکریپت
بیایید با جاوا اسکریپت شروع کنیم…
const fibonaive = n => {
if (n == 0 || n == 1) {
return n;
}
return fibonaive(n - 1) + fibonaive(n - 2);
};
نحوه کدگذاری الگوریتم فیبوناچی بازگشتی در پایتون
حالا بیایید آن را در پایتون ببینیم …
def fibonaive(n):
if (n ==0) or (n == 1):
return n
return fibonaive(n - 1) + fibonaive(n - 2)
طرح را ارزیابی کنید
آیا می توانیم بهتر عمل کنیم؟
ما مطمئنا می توانیم!
راه حل ما در بالا به عنوان یک پیاده سازی ساده از فیبوناچی نامیده می شود.
چرا ساده لوح است؟ چون زمان اجرا واقعا بد است.
O بزرگ دنباله فیبوناچی بازگشتی چیست؟
O(2^n) است.
(در واقع، O(1.6^n) است، اما چه کسی در حال شمارش است؟)
اگر می‌خواهید نحوه محاسبه پیچیدگی زمان و مکان را بیاموزید، یک نسخه از کتاب کوچک بیگ O را بردارید
به این نمودار شاخه های تماس بازگشتی ما نگاهی بیندازید.
چرا این الگوریتم ناکارآمد است؟
همپوشانی مشکلات فرعی! ما همان مشکلات را به طور مکرر در شعب خود حل می کنیم.
چند بار f(0) را حل می کنیم؟
f(1) را چند بار حل می کنیم؟
f(2) را چند بار حل می کنیم؟
چند بار f(3) را حل می کنیم؟
پاسخ به همه موارد بالا این است: خیلی زیاد!
راه حل چیست؟
برنامه نویسی پویا!
اگر می خواهید بیشتر بدانید، مقاله من را بررسی کنید برنامه نویسی پویا چیست؟ حفظ کردن و جدول بندی
A برای الگوریتم ها است
به خود یک A بدهید. کپی خود را از A برای الگوریتم ها بگیرید
