سری فیبوناچی بازگشتی
01. خطوط فیبوناچی (Fibonacci) چه هستند و چه کاربردی دارند؟
لئوناردو فیبوناچی ریاضیدان قرن 12 میلادی در ایتالیا متولد شد و بزرگترین اثر وی کشف اعدادی طلایی از روی حل مساله ازدیاد تعداد خرگوش ها بود. اعداد طلایی کشف شده توسط این دانشمند را به احترامش اعداد فیبوناچی می نامند. دنباله فیبوناچی با صفر و یک شروع می شود و هر عدد مجموع دو عدد قبلی می باشد …377-233-144-89-55-34-21-13-8-5-3-2-1-1
تا به حال هماهنگی های زیادی بین روابط این اعداد و قوانین طبیعت دیده شده است. نسبت های فیبوناچی در همه جا دیده می شوند، از فاصله حرکت سیاره ها به دور ستارگان تا فاصله حرکت الکترون ها به دور هسته اتم. این اعداد نسبت هایی با یکدیگر دارند که در علم اقتصاد نیز کاربرد دارد.
سری فیبوناچی چیست؟
سری فیبوناچی دنباله ای از اعداد است که هر عدد از مجموع دو عدد قبلی خود بدست می آید این دنباله بصورت زیر است.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …
شاید در نگاه اول این سری چیز خاصی نداشته باشد! اما آنچه دنباله فیبوناچی را مشهور کرده است نسبت هایی است که اعداد این دنباله با یکدیگر دارند که مهمترین آن، نسبت هر عدد از این دنباله به عدد قبلی خود است و هر چه این عمل را برای جملات جلوتر این سری انجام دهیم این نسبت به یک عدد ثابت همگرا میشود. برای مثال در سری فیبوناچی، اعداد 20، 21 و 22 اُم به ترتیب عبارت است از: 6765، 10946، 17711 حال اگر هر عدد را به عدد قبلی خود تقسیم کنیم به جواب زیر میرسیم و همانطور که مشاهده میکنید تا رقم هفتم اعشار آن یکی است!
عدد 1.618 را نسبت طلایی یا همان Golden Ratio می گویند.
نسبت های مهم فیبوناچی
423.8% : از تقسیم هر عدد سری به سومین عدد قبل از خود بدست می آید.
261.8% : از تقسیم هر عدد سری به دومین عدد قبل از خود بدست می آید.
161.8% : از تقسیم هر عدد سری به عدد قبلی خود بدست می آید.
78.6% : جذر عدد 61.8 است!
61.8% : از تقسیم هر عدد سری به عدد بعدی خود بدست می آید.
38.2% : از تقسیم هر عدد سری به دومین عدد بعد از خود بدست می آید.
23.6% : از تقسیم هر عدد سری به سومین عدد بعد از خود بدست می آید.
تذکر: نسبت های 50% و 100% و 200% جزء نسبت های فیبوناچی نیستند اما هنگام تحلیل مورد استفاده قرار میگیرند!
ابزارهای مهم فیبوناچی در تحلیل تکنیکال
با استفاده از ابزارهای فیبوناچی میتوان یک خط، منحنی و یا زمان خاص برای بازگشت یا ادامه دار بودن یک روند را ترسیم کرد که هیچ اجباری به حمایت و مقاومت بودن آنها نیست و صرفا بحث روانی دارد و استفاده از آنها بایستی به عنوان ابزار کمکی تحلیل تکنیکال و همراه با سایر ابزارها باشد و همپوشانی سطوح فیبوناچی با الگوهای قیمتی، خطوط حمایت و مقاومت، خط روند و… باعث افزایش اعتبار آنها خواهد شد و میتوان واکنش جدی تر بازار را انتظار داشت.
جزئیات خبر
در مطلب « ابزارهای فیبوناچی و کاربرد آنها در تحلیل تکنیکال » نحوه استفاده تعدادی از ابزارهای پرکاربرد را تشریح کردیم. به‌غیراز مواردی که پیش‌تر درباره آنها توضیح دادیم، ابزارهای دیگری هم در فیبوناچی وجود دارد که در ادامه با آنها آشنا می‌شوید.
۱- کمان فیبوناچی(Fibonacci Arcs)
استفاده از این ابزار همانند حالت فیبوناچی اصلاحی RET است، در واقع برای یک‌روند که می‌تواند صعودی یا نزولی باشد، می‌توانیم نقاط حمایت یا مقاومت را به دست بیاوریم.
۲- بادبزن فیبوناچی(Fibonacci Fan)
این ابزار نیز همانند کمان فیبوناچی برای تعیین محدوده حمایت یا مقاومت استفاده میشود و تنها فرق آن این است که در حالت قبلی به‌صورت کمان نمایش داده میشود و در این حالت به‌صورت خط است. به تصویر زیر توجه کنید.
۳- فیبوناچی زمانی(Fibonacci Time Extension)
این ابزار برای به دست آوردن نقاطی است که احتمالا از لحاظ زمانی جز نقاط عطف(کلیدی) به‌شمار بیایند، بنابراین یکی از کارهایی که انجام می‌دهد، به شما این امکان را می‌دهد که زمان را نیز پیش‌بینی کنید. زمانی که در آن تغییر جهت رخ می‌دهد. برای رسم این ابزار کافی است که نقطه حداکثر و حداقل یک کندل را به هم وصل کنید؛ که در این‌بین یک سقف و یک کف همانند حالت‌های پیشین داریم. یادآوری میشود که فاصله زمانی بین ستون‌ها مبین اعداد سری فیبوناچی است.
ناحیه پر پتانسیل بازگشتی The potential reversal zone confirmation (PRZ)
هنگامی‌که فیبوناچی‌های از هر نوع در یک نقطه ظاهر می‌شوند، سری فیبوناچی بازگشتی یک ناحیه‌ی پر پتانسیل بازگشتی را نشان می‌دهد که نشانگر بازگشت قیمت‌ها است، در واقع با توجه به‌رسم ابزار فیبوناچی هنگامی‌که چند سطح در کنال سایر عوامل همگرا می‌شوند، یک ناحیه معتبر را تشکیل می‌دهند، در این روش باید از تایم‌های کوچک‌تر نیز استفاده کرد.(min30/60/15) تا بر اعتبار ناحیه برگشتی بیفزاید.(تایم‌های کوچک‌تر سریع‌تر شکسته می‌شوند) همچنین می‌توانیم به دنبال شکاف قیمتی باشیم. توجه داشته باشید حجم معامله در PRZ بسیار حائز اهمیت است. استفاده ویژه این ناحیه در الگوهای هارمونیک است که هنگامی‌که این الگوها تشخیص داده شوند، با وجود منطقه‌یPRZ میتوان اعتبار الگو افزایش می‌یابد.
نکات مهم در ترازهای فیبو
۱ سقف‌ها و کف‌هایی که وجود دارد را با رسم فیبو های مختلف استفاده کرده و نقاط prz را شناسایی کنیم.
۲ وجود الگوهای شمعی بر روی تراز مهم است و بررسی کنید که سطح با کندل شکسته شده است؟
۳ نقاط پایانی نباید از تراز عبور کنند یا حداکثر کمی نفوذ داشته باشیم و درصورتی‌که نفوذ جدی باشد، باید منتظر کندل بعدی بود و از روی آن تصمیم گرفت.
آموزش توابع بازگشتی در جاوا اسکریپت
آموزش توابع بازگشتی در جاوا اسکریپت recursion function با چند مثال کاربردی
در این مقاله میخوام در مورد توابع بازگشتی در جاوا اسکریپت صحبت کنم توابع بازگشتی توابعی هستند که میتونن خودشون رو فراخوانی کنند که چنین فرایندی به طور کلی «بازگشت» (recursion) نامیده میشود توابع بازگشتی ( recursion function ) در زبان های برنامه نویسی کاربرد های زیادی دارن و میتونن به ما کمک کنن تا از تکرار کد جلوگیری کنیم مثلا در بخش های از برنامه ما اگه نیاز باشه که روی یک فرایند یک کار تکراری انجام بدیم که این کار از یک الگوی مشترک پیروی میکنه میتونیم از توابع بازگشتی استفاده کنیم مثال معروف شو هم فک کنم همه بدونن و معمولا توی دانشگاه ها این تابع رو با این چند مثال توضیح میدن که میشه از اون برای حل سری فیبوناچی یا محاسبه فاکتوریل و … استفاده کرد.
تابع بازگشتی یا recursion function چیست ؟
اگر بخوام در یک تعریف ساده این اصطلاح رو بهتون توضیح بدم میشه گفت که اگر در تعریف بدنۀ یک فانکشن ، اون فانکشن بتونه خودش رو در داخل بدنه خودش فراخوانی کنه ، به همین سادگی ما یک فانکشن بازگشتی یا recursion نوشتیم
فقط دقت داشته باشین که در نوشتن یک تابع بازگشتی باید حتما یک شرط اتمام حلقه فراخوانی براش بزارین که بعد از درست بودن شرط یک مقداری رو برگردونه چون در این صورت ما در یک حلقه بی نهایت می افتیم و برنامه خطا میده
یک مثال ساده از توابع بازگشتی
در این مثال قبل از نوشتن تابع بازگشتی من یک تابع ساده برای نمایش اعداد n تا ۰ می نویسم که در ابتدا با روش غیر بازگشتی حلش کردم بعدش اون رو تبدیل میکنم به یک تابع بازگشتی تا بتونید از این طریق مفهوم این نوع توابع رو کامل درک کنید.
خب در ابتدا من عدد ۵ رو به تابع countDown دادم که از طریق حلقه for عدد دریافتی رو از n تا ۰ نمایش بدیم فقط توجه کنید که منظور من ازn تا ۰ اینکه اگه یک عدد رو به این تابع بدیم مثلا ۵ این تابع در هر مرحله یکی از اون کم میکنه و نمایش میده تا اینکه به صفر برسه و اون عدد رو برای ما در کنسول لاگ چاپ میکنه به کد های زیر دقت کنید:
حالا مثال بالا رو با یک تابع بازگشتی انجام میدم براتون
اگر بخوام مثال بالا رو براتون توضیح بدم من تابع رو در بار اول فقط یک بار فراخوانی کردیم و عدد ۵ رو به اون پاس دادم و در دفعات بعد این تابع رو در داخل خودش فراخوانی کردم و هر دفعه از پارامتر ورودی اون یک مقداری رو کم کردم و از یک شرط اتمام فرآیند فراخوانی تابع استفاده کردم یعنی نکته مهم در توابع بازگشتی همین شرط اتمام فرایند فراخوانی است که باید به اون خیلی دقت کنید چون اگر این شرط نباشه تابع در یک حلقه بی نهایت می افته و برنامه با خطا مواجه می شه
یک مثال کمی پیجیده تر و البته کاربردی در صفحات وب از توابع بازگشتی
اگر بخوام این مثال رو توضیح بدم و بگم ما در شرکت مون یک مگامنو داشتیم که هر دفعه داده هاشو از یک api دریافت میکردیم در یک قسمت نیاز بود که ما با استفاده از category id در هر سطحی که باشیم بیایم و parent category های این دسته بندی رو بدست بیارم پس اینجا بود که متوجه شدم باید حتما از یک تابع بازگشتی استفاده کنم چون بدون تابع بازگشتی نمیشه این مسئله رو حل کرد.
در این مثال یک آرایه داریم که داخل این آرایه تعداد object وجود داره که شامل مجموعه ای از دسته بندی هاست و در سه سطح می باشد اگه بخواهم بیشتر توضیح بدم ما میخوایم یک تابع بازگشتی بنویسیم که وقتی category id سطح سوم این لیست را به آن بدیم این تابع بازگشتی بیاد و متن این لیست و متن دو سطح بالای اون را هم پیدا کند و به ما بده.
فرض کنید که ما یک آرایه از دسته بندی منو های سایت مون داریم که میخوایم از طریق این آرایه منو ها و زیر منو های هر دسته بندی رو پیاده سازی کنیم من برای اینکه کاربرد توابع بازگشتی رو سری فیبوناچی بازگشتی متوجه بشین میام و اول اون رو بدون اینکه از تابع بازگشتی استفاده کنم پیاده سازی میکنم و بعدش از طریق توابع بازگشتی همین مثال رو حل میکنم تا شما با مزایای توابع بازگشتی آشنا بشین و ببینید که چقدر از تکرار کد ها جلوگیری میکنه
فرض کنید که این ارایه همون دسته بندی های ماست که از طریق یک api دریافت کردیم و میخوایم اون رو نمایش بدیم و یا عملیات خاصی روش پیاده سازی کنیم
درس ۱۴: تابع سری فیبوناچی بازگشتی در پایتون: تابع بازگشتی (Recursive) و Memoization¶
این درس بخش پایانی از بررسی تابع در پایتون می‌باشد و به شرح تابع بازگشتی (Recursive) و مفهوم Memoization در زبان برنامه‌نویسی پایتون خواهد پرداخت.
تابع بازگشتی¶
از درس نهم با دستورات کنترلی for و while آشنا شده‌ایم، این دستورات تنها ابزار ما برای تکرار قسمتی از کد بودند. اکنون با پیاده‌سازی شیوه‌ای جدید در تکرار آشنا می‌شویم.
به بیانی ساده، تابع بازگشتی (Recursive function) به تابعی گفته میشود که خود را از داخل بدنه خود فراخوانی می‌کند. پیاده‌سازی تابع به صورت بازگشتی شیوه‌ای است که از آن برای حل برخی مسائل بهره گرفته میشود و باید بدانیم که توابع بازگشتی، یک سینتکس یا دستور خاص در زبان پایتون نیست بلکه یک شیوه حل مسئله می‌باشد که با استفاده از تابع در زبان برنامه‌نویسی پایتون (همچون بسیاری از زبان‌های دیگر) قابل پیاده‌سازی است.
برای مثال در نمونه کد پایین مقدار فاکتوریل (Factorial) عدد پنج را به شیوه بازگشتی محاسبه می‌کنیم:
عموما میتوان مسئله‌هایی که از توالی انجام یک کار یکسان قابل حل هستند را به صورت بازگشتی پیاده‌سازی کرد. مراحل اجرای نمونه کد بالا به صورت زیر است:
توضیح: هنگامی factorial(5) فراخوانی میشود ( n == 5 )، شرط 1 => n رد و بخش else اجرا میشود. در این مرحله نمونه دیگری از تابع با آرگومان 4 فراخوانی میشود و اجرای factorial(5) منتظر پایان اجرای factorial(4) و دریافت نتیجه آن می‌ماند. به همین ترتیب چندین نمونه از یک تابع اجرا می‌شوند که منتظر دریافت نتیجه از نمونه بعد از خود هستند. در نهایت شرط 1 => n برقرار میشود و نمونه factorial(1) نتیجه خود را به factorial(2) برمی‌گرداند. به همین ترتیب نتایج بازگشت داده می‌شوند تا به نمونه نخست اجرا شده یعنی factorial(5) برسد و اجرای مورد نظر کاربر به پایان برسد.
مدیریت توالی تابع (شیوه بازگشتی) در حافظه با استفاده از ساختمان داده پشته (Stack) [ویکی‌پدیا] انجام میشود.
هر تابع بازگشتی شامل دو بخش مهم است:
- یک عبارت حاوی فراخوانی خود تابع
- یک شرط برای انتخاب بین فراخوانی مجدد و پایان
پیاده‌سازی شیوه بازگشتی شاید به نظر هیجان‌انگیز باشد اما نباید فراموش کرد که میزان حافظه (Memory) زیادی مصرف می‌کند، اجرای آن زمان‌بر خواهد بود، درک جریان اجرای آن اغلب سخت است و اشکال‌زدایی (debug) آن ساده نخواهد بود!
استفاده از decorator¶
هنگام استفاده از decorator بر روی توابع بازگشتی باید به این نکته توجه داشته باشید که این decorator بر روی تمامی نمونههای فراخوانی شده از تابع اعمال خواهد شد و اینکه تنها یک نمونه از decorator ایجاد میشود و تمام نمونههای تابع به همان یک نمونه ارسال می‌شوند:
به خروجی نمونه کد بالا حتما توجه نمایید!.
تنظیم عمق بازگشتی¶
در زبان برنامه‌نویسی پایتون در عمق پیاده‌سازی توابع بازگشتی (تعداد نمونههای فراخوانی شده از تابع و موجود در پشته) یک محدودیت قابل تنظیم وجود دارد. تابع ()getrecursionlimit از ماژول sys این مقدار را برمی‌گرداند [اسناد پایتون]. این مقدار به صورت پیش‌فرض برابر با 1000 می‌باشد که با استفاده از تابع (limit)setrecursionlimit از ماژول sys میتوان آن را تغییر داد [اسناد پایتون]:
با رد شدن از محدودیت عمق توابع بازگشتی یک استثنا RecursionError گزارش خواهد شد:
علاوه بر این محدودیت، یک محدودیت جدی‌تر دیگری نیز وجود دارد و آن هم میزان فضایی است که توسط سیستم عامل برای پشته در نظر گرفته شده است. با رد شدن از این مقدار فضا، سری فیبوناچی بازگشتی برنامه با خطای زمان اجرا مواجه می‌گردد ( RuntimeError ).
تابع Generator بازگشتی¶
در پیاده‌سازی توابع Generator و Coroutine نیز میتوان شیوه بازگشتی را در نظر گرفت، در این صورت ممکن است نتایج کمی برخلاف انتظار شما باشد. نمونه کد زیر یک شی لیست تو در تو را دریافت و تک تک اعضای درون هر لیست را چاپ می‌کند:
اکنون برای تبدیل تابع flatten به یک Generator کافی است به جای print از yield استفاده کنیم:
اتفاقی نیفتاد! و خروجی یک لیست خالی است. از درس پیش به خاطر داریم، فراخوانی تابع genflatten (که در واقع یک تابع Generator است) تنها باعث ایجاد یک شی Generator میشود و می‌بایست در نقطه‌ای که تابع خودش را فراخوانی می‌کند نیز مقدمات پردازش خروجی یک شی Generator را فراهم کنیم. اکنون با اصلاح کد بالا:
Memoization¶
Memoization یا یادآوری، یک تکنیک برای نگهداری از نتایج به دست آمده به منظور جلوگیری از تکرار محاسبات است [ویکی‌پدیا]. این تکنیک را میتوان در زبان برنامه‌نویسی پایتون با استفاده از decorator پیاده‌سازی کرد.
برای توضیح این بخش اجازه دهید یک مثال بازگشتی دیگر را بررسی کنیم. محاسبه مقدار فیبوناچی [ویکی‌پدیا] یک عدد مشخص:
در این مثال ما از عدد 9 جلوتر نرفتیم چرا که محاسبه برای اعداد بزرگتری به مانند 50 واقعا زمان‌بر خواهد بود و این فرصتی است تا ما کارایی تکنیک Memoization را محک بزنیم. اکنون تابع بازگشتی فیبوناچی خود را با استفاده از تکنیک Memoization و یک Decorator بهینه‌سازی می‌کنیم:سری فیبوناچی بازگشتی
حالا مقدار 50 که هیچ، مقدار فیبوناچی برای عدد 500 را محاسبه کنید ( (500)fibonacci ). تفاوت در زمان اجرا را خودتان متوجه خواهید شد!
به کمک Decorator در این مثال ( memoize_fibonacci ) نتایج حاصل از فراخوانی هر نمونه تابع در جایی ذخیره میشود (شی دیکشنری memory ) و پیش از فراخوانی مجدد یک نمونه جدید از تابع بررسی میشود که آیا قبلا این مقدار محاسبه شده است یا خیر. در صورت وجود جواب از تکرار فراخوانی تابع صرف نظر و سری فیبوناچی بازگشتی مقدار از پیش موجود به عنوان نتیجه برگردانده میشود. بنابراین بدیهی است که با جلوگیری از ایجاد نمونه توابع جدید و محاسبات تکراری، سرعت اجرا افزایش یابد.
Function Attributes¶
از دروس پیش مشاهده کردیم که اشیا در پایتون بر حسب نوع خود شامل یک سری صفات یا ویژگی‌های (Attributes) پیش‌فرض هستند؛ برای مثال صفت __name__ که دربردارنده نام تابع است [اسناد پایتون].
علاوه بر این؛ توابع در پایتون می‌توانند صفات دلخواه کاربر را نیز دریافت کنند که به این صورت میتوان یک سری اطلاعات اضافی را به توابع پیوست کرد [PEP 232]. به نمونه کد پایین توجه نمایید:
همانطور که قابل مشاهده است با استفاده از سینتکس زیر میتوان یک Attribute به تابع اضافه کرد:
همچنین برای این منظور میتوان از تابع آماده (setattr(object, name, value استفاده کرد [اسناد پایتون]. این تابع سه آرگومان دریافت می‌کند؛ شی‌ای که می‌خواهید یک Attribute به آن اضافه کنید (در اینجا تابع)، نام (از نوع رشته - string) و مقدار Attribute مورد نظر:
این صفات در قالب یک شی دیکشنری ذخیره می‌شوند که با استفاده از صفت __dict__ در دسترس هستند [اسناد پایتون]:
برای دریافت مقدار یک Attribute مشخص می‌توانید از تابع آماده ([getattr(object, name[, default نیز استفاده کرد [اسناد پایتون]. این تابع دو پارامتر اجباری ( object و name ) و یک پارامتر اختیاری ( default ) دارد. در صورتی که شی مورد نظر (در اینجا تابع) فاقد صفت مورد نظر باشد مقدار default (در صورت ارسال) برگردانده خواهد شد:
در صورت تلاش برای دریافت صفتی که برای تابع مورد نظر تعریف نشده باشد یک استثنای AttributeError گزارش خواهد شد. البته همانطور که بیان شد در صورت استفاده از تابع getattr و تنظیم پارامتر default این اتفاق رخ نخواهد داد. همچنین برای جلوگیری از بروز این استثنا میتوان پیش از استفاده از صفت، وجود آن را با استفاده از تابع آماده (hasattr(object, name بررسی کرد [اسناد پایتون]:
برای حذف یک Attribute نیز میتوان از تابع آماده (delattr(object, name استفاده کرد [اسناد پایتون]:
و یا از دستور del
در انتهای این بخش باید خاطر نشان کرد که در صورت تعریف Attribute برای توابع خود و استفاده از decorator، همانطور که در درس پیش نیز توضیح داده شد استفاده از [email protected] فراموش نشود [درس سیزدهم].
Built-in Functions¶
مفسر پایتون تعدادی تابع کاربردی را بدون نیاز به import کردن ماژول خاصی در اختیار برنامه‌نویسان قرار می‌دهد. از این توابع با عنوان Built-in Functions (توابع آماده یا توابع داخلی) یاد میشود. فهرست کامل این توابع به همراه توضیح در اسناد پایتون موجود است. در طی دروس پیشین و حتی همین درس با برخی از آنها آشنا شده‌اید، در این بخش نیز به بررسی چند مورد دیگر می‌پردازیم.
این تابع یک (و تنها یک) عبارت پایتونی را در قالب شی رشته دریافت، اجرا و نتیجه را برمی‌گرداند [اسناد پایتون].
بر اساس تعریف موجود در اسناد پایتون ([[eval(object[, globals[, locals ، این تابع شامل دو پارامتر globals و locals نیز میشود که ارسال آرگومان به آنها اختیاری است. هر دو از نوع دیکشنری (dict) هستند که Scope یا حوزه‌های global و local کدی که باید اجرا شود (پارامتر یکم تابع) را ارايه می‌دهند:
این تابع همانند eval است ولی با این تفاوت که می‌تواند چندین عبارت یا دستور پایتونی را در قالب یک شی رشته دریافت و اجرا کند. خروجی exec همیشه برابر با None است [اسناد پایتون].
exec در پایتون نسخه 2x به صورت تابع تعریف نشده است و به صورت یک دستور به کار می‌رود [اسناد پایتون]:
این تابع همانند eval شامل دو پارامتر globals و locals نیز میشود:
که البته در نسخه‌های 2x از سینتکس [[exec code[ in globals[,locals پیروی میشود:
compile¶
هر بار که یک شی رشته حاوی کد پایتون به توابع eval و exec ارسال میشود، مفسر پایتون ابتدا این کد را به بایت‌کد کامپایل و سپس اجرا می‌کند که تکرار این کار باعث تحمیل سربار به سیستم میشود. میتوان با یک بار کامپیال و استفاده مجدد از اعمال این سربار اجتناب کرد.
تابع compile برای همین منظور است [اسناد پایتون]. تعریف این تابع به صورت زیر است:
سری فیبوناچی بازگشتی
چنان‌كه در ويكي‌پديا آمده، فيبوناچي نام رياضيدان ايتاليايي است که در مسابقات سال 1225 براي حل مساله مطرح شده راه‌حلي ارائه داد که جواب آن سري فيبوناچي شد و به احترام او اين سري اعداد را سري فيبوناچي نامگذاري کردند. اين سري به دنباله‌اي از اعداد گفته مي‌شود که به ازاي هر x عضو اعداد صحيح مثبت بزرگ‌تر از ? داشته باشيم:
و به ازاي x=0,1 داريم: F(x)=x.
جمله عمومي سري فيبوناچي به‌صورت زير است:
حال ما قصد داريم همين اعداد را با برنامه‌نويسي محاسبه کنيم. اولين سوال ما به‌دست آوردن يک عنصر مشخص از اعداد فيبوناچي است، مثلا عنصر xام از اين سري از اعداد را به‌دست بياوريد.
براي اين کار بايد در يک حلقه اعداد را با دو عدد قبلي جمع کنيم، مثلا اگر عنصر 10 ام سري فيبوناچي را از ما خواستند در يک حلقه از 1 تا 10 اعداد را با دو عدد پيشين جمع مي‌کنيم.
فقط دقت داشته باشيد که دو عدد اول 0 و 1 هستند. فرض مي‌کنيم عدد اول a و عدد دوم b باشد و fib عدد مورد نظر ما باشد. در هر بار اجرا شدن حلقه فوق داريم:
اين‌طوري مي‌دانيم که در هر مرحله عدد فيبوناچي مورد نظر ما چيست. پس کد را به‌صورت زير مي‌نويسيم:
long Fibonacci(int no)
for (int i = 1; i « no; i++)
بسيار خب اين روش ترتيبي براي به‌دست آوردن اعداد فيبوناچي است، مي‌توانيم به‌صورت بازگشتي نيز اعداد فيبوناچي را محاسبه کنيم.
در روش سری فیبوناچی بازگشتی بازگشتي در هر مرحله تابع به دو بخش تقسيم مي‌شود و براي هر دو بخش دوباره تابع فراخواني مي‌شود. در مرحله اول تابع به ازاي ( Fibonacci (no–1 و ( Fibonacci (no–2 دوبار اجرا مي‌شود و همين‌طور در مرحله بعدي اين دو تابع از حل 4 تابع ديگر به‌دست مي‌آيد و همين‌طور اگر حساب کنيم مي‌بينيم که در محاسبه عدد nام سري فيبوناچي بايد 2 به توان n + 1 بار تابع اجرا شود. از آنجا که در توابع بازگشتي از Stack پشته استفاده مي‌شود و فضاي پشته محدود است با زياد شدن no دچار خطايStack Overflow خواهيم شد!
پس در محاسبه اعداد بزرگ بهتر است از روش بازگشتي استفاده نکنيم.
کد روش بازگشتي به‌صورت زير است:
long FibonacciRecursive(int no)
if ((no == 1) || (no == 2))
return FibonacciRecursive(no - 1) + FibonacciRecursive(no - 2);
در هر دو روش ممکن است عدد فيبوناچي حاصل بقدري بزرگ باشد که در متغير‌هاي معمول زبان‌هاي برنامه‌نويسي جاي نگيرد، آن وقت تکليف چيست؟
براي حل اين مشکل بايد عدد حاصل را يک آرايه تعريف کرده و فرض کنيد هر رقم از آرايه يک رقم از عدد است. براي اطلاعات بيشتر در مورد پياده‌سازي جمع براي اعداد بزرگ به مقاله‌هاي قبلي که پيرامون اين موضوع هستند مراجعه کنيد.
آيا راه‌حل ديگري براي به‌دست آوردن عدد فيبوناچي وجود دارد؟ بله! با استفاده از عدد طلايي Phi.
براي محاسبه عدد فيبوناچي با استفاده از عدد طلايي کافيست جاي n در سری فیبوناچی بازگشتی فرمول زير شماره عدد فيبوناچي مورد نظر را قرار دهيد.
fn = math.pow(Phi, n) / math.sqrt( 5)
عدد في برابر است با: (25/1+ 1) / 2 = 1.6180339
double Phi = (Math.Sqrt(5) + 1) / 2;
double fibonachi = Math.Pow(Phi, 40) / Math.Sqrt(5);
بسيار خب ما توانستيم براي محاسبه عدد فيبوناچي از سه روش استفاده کنيم، هر کدام از روش‌هاي ذکر شده ويژ‌گي‌هاي خود را دارند.
مزيت روش آخر نسبت به روش‌هاي ديگر اين است كه ديگر حلقه‌اي اجرا نمي‌شود و بيشتر از توابع کتابخانه‌اي هر زبان استفاده شده است (توابع Math.Pow تابع توان و Math.Sqrt تابع جذر).
يکي ديگر از مسائلي که در مورد اعداد فيبوناچي مطرح مي‌شود اين است که عکس مراحل بالا را انجام دهيم، يعني يک عدد به ما بدهند و تشخيص بدهيم که آيا اين عدد جزئي از سري فيبوناچي است يا نه؟ يا به اصطلاح اين عدد فيبوناچي است يا خير؟
حل اين مساله بر عهده خواننده گذاشته شده است.
| صفحه نخست پست الکترونیک آرشیو عناوین مطالب وبلاگ |
| درباره وبلاگ |
|
ساخت مصلی اعظم لار ستاد بازسازی عتبات عالیات حسینیه اعظم مقالات مرتبط |
