فارکس چیست

فیبوناچی بازگشتی

توصیه می‌شود که سطوح صفر و یک فیبوناچی‌ بر روی آخرین روند قیمتی قرار فیبوناچی بازگشتی بگیرد؛ به این صورت که سطح یک یا صد درصد فیبوناچی‌ را در ابتدای روند و سطح صفر یا صفر درصد فیبوناچی‌ را در انتهای روند قرار دهیم. تصویر زیر نحوه استفاده از ابزار اصلاحی Fibonacci را نشان می‌دهد.

اعداد فیبوناچی

در ریاضیات، اعداد فیبوناچی که اغلب با $F_n$ نمایش داده می‌شود، دنباله‌ای نامتناهی از اعداد حسابی‌ است که در آن هر عنصر حاصل جمع دو عنصر پیشین خود است.

صورت ریاضی

$$ F_n = \begin 0 & \mbox n = 0; \\ 1 & \mbox n = 1; \\ F_ + F_ & \mbox n> 1. \\ \end $$ بدین معنی که: عنصر صفرم یعنی $F_0$ برابر با صفر، عنصر اول یعنی $F_1$ برابر با یک،‌ و عنصر $n$ ام یعنی $F_n$ که $n > 1$ برابر است با مجموع عنصر $n-1$ ام و عنصر $n-2$ ام.

عناصر اولیه‌ی این دنباله عبارتند از: $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . $$

محاسبه

راه حل‌ها و الگوریتم‌های زیادی برای محاسبه $n$ امین عنصر این دنباله وجود دارند. مهم‌ترین آن‌ها عبارتند از:

حل‌ با توابع بازگشتی

تحلیل پیچیدگی زمانی

با استقرای ریاضی می‌توان نشان داد که: $T(n) = O(2^n)$

حل‌ با استفاده از دو متغیر اضافی

تحلیل پیچیدگی زمانی

این الگوریتم یک حلقه از $2$ تا $n$ دارد،‌بنابراین پیچیدگی زمانی آن $O(n)$ است.

حل‌ با استفاده از ماتریس ها

اگر ماتریس $A$ و $M$ برابر باشند با: $$A = \beginF_ \\ F \end$$ و $$M = \begin0 & 1 \\ 1 & 1 \end$$

با استفاده از تعریف ریاضی اعداد فیبوناچی می‌توان نشان داد که: $$M \times A = \beginF_ \\ F \end$$

بدین ترتیب برای $0 \leq n$ داریم: $$M^n \times A = \beginF_ \\ F \end$$

پس برای به‌دست آوردن $F_n$ کافی‌ است $M^n$ را محاسبه کرده، آن را در ماتریس $A$ ضرب کنیم و عنصر فیبوناچی بازگشتی واقع در ستون اول سطر اول ماتریس حاصل را بگیریم.

حل‌ با استفاده از فرمول صریح

با استفاده از توابع مولد می‌توان نشان داد: $$F_n = \frac>((\frac>)^n - (\frac>)^n)$$

یک مثال

مثال: کلاسی $12$ دانش‌آموز دارد که در صبحگاه در یک صف به ترتیب پشت سر هم می‌ایستند. مدرسه میخواهد تعدادی از این دانش‌آموزان (فیبوناچی بازگشتی حداقل یک نفر)‌ را برای گروه سرود انتخاب کند که در آن هیچ دو دانش‌آموزی که در صف پشت سر هم هستند نباشند. مدرسه چند راه برای انتخاب این گروه دارد؟

سوال را برای $n$ دانش آموز حل می‌کنیم. فرض فیبوناچی بازگشتی می‌کنیم جواب مساله برای $n$ دانش‌آموز برابر $s_n$ باشد. برای $n = 1$، تنها ۱ راه وجود دارد، پس $s_1 = 1$. برای $n = 2$، تنها‌ یکی از دانش‌آموزان می‌تواند در گروه سرود باشد، پس ۲ راه وجود دارد، پس $s_2 = 2$. برای $n$ های بزرگ‌تر از $2$: اگر دانش‌آموز آخر (شماره‌ی $n$)، در گروه سرود باشد، دانش آموز $n-1$ ام نمی‌تواند باشد، پس $s_$ راه وجود دارد، و اگر نباشد، $s_$ راه. بنابر‌این: $s_n = s_ + s_$. می‌توان دید که $s_n = f_$. پس جواب مساله برابر است با $f_$ یعنی $233$.

الگوریتم فیبوناچی با پایتون + بازگشتی و غیربازگشتی

الگوریتم فیبوناچی با پایتون

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

مشاهده ی نوشته های زیر به شما توصیه می شود:

الگوریتم فیبوناچی با پایتون

الگوریتم فیبوناچی درپایتون غیر بازگشتی

کد دنباله ی فیبوناچی به صورت غیر بازگشتی با زبان برنامه نویسی پایتون به شکل زیر است:

الگوریتم فیبوناچی در پایتون بازگشتی

کد فیبوناچی بازگشتی دنباله ی فیبوناچی به صورت بازگشتی با پایتون به شکل زیر است:

اگر کدهای بهتری برای حل دنباله ی فیبوناچی در دسترس دارید برای ما ارسال کنید.

2 دیدگاه

اخه ارور می ده که

فرورفتگی ها یا indentهارو خودتون اصلاح کنید برای دستورات for و if و …
درست میشه

دیدگاهتان را بنویسید لغو پاسخ

پیشنهاد می شود این نوشته ها را نیز بخوانید

روش افزودن ckeditor به nextjs

دانلود یک لیست از تصاویر با کمک فایل متنی در پایتون

مشکل CORS policy فیبوناچی بازگشتی با apiها در جنگو

مشکل نخواندن اطلاعات تابع file_get_contents بعد از استفاده از CDN

دیگر مطالب برنامه نویسی را از دست نمی دهید

با وارد کردن ایمیل خود از مقالات، آموزش ها و مطالب ما با خبر شوید. ایمیل شما برای هیچ منظور دیگری استفاده نخواهد شد زیرا ما خود از اسپم بیزاریم.

وبسایت آموزشی camelCase، یک وبسایت آموزش برنامه نویسی به زبان فارسی می باشد که به انتشار مقاله ی آموزشی، کتاب مرجع، آموزش ویدیویی، دوره های حضوری و وبینار آنلاین، سورس کد و حل تمرین می‌پردازد. سالهای سال است که نویسندگان این مجموعه با ارائه ی اندوخته ها و تجربیات خود در حوزه های برنامه نویسی، طراحی وب و هوش مصنوعی که دانش آموخته و فعال این حوزه هستند در کنار شما می‌باشند.

مقالات مرتبط

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

برو به دکمه بالا