تبلیغات

الگوریتم تشخیص عدد فیبونانچی

الگوریتم تشخیص عدد فیبونانچی

فیبونانچی

دنباله‌‌ی اعداد فیبونانچی به صورت زیر می‌باشد:

۰٬ ۱٬ ۱٬ ۲٬ ۳٬ ۵٬ ۸٬ ۱۳٬ ۲۱٬ ۳۴٬ ۵۵٬ ۸۹٬ ۱۴۴٬ ۲۳۳٬ ۳۷۷٬ ۶۱۰٬ ۹۸۷٬ ۱۵۹۷٬ ۲۵۸۴٬ ۴۱۸۱٬ ۶۷۶۵٬ ۱۰۹۴۶٬ ۱۷۷۱۱

در این دنباله، دو عدد اول را 0 و 1 در نظر گرفته و سپس اعداد بعدی، از جمع دو عدد قبلی خود ساخته می‌شوند.

شرح الگوریتم

این را می‌دانیم که:

  • دو عدد اول 0 و 1 هستند.
  • اعداد سوم به بعد، از جمع دو عدد قبلی خود ساخته می‌شوند.
  • می‌توان فرض کرد که عدد اول فیبونانجی، برای مثال از جمع دو عدد 1 و -1 ساخته می‌شود. یا حتی از جمع عدد 0 و 0! این تنها یک فرض است که در نظر می‌گیریم!

با این اوصاف، برای فهمیدن فیبونانچی بودن یک عدد در برنامه‌نویسی:

اگر بخواهیم تشخیص دهیم که x عدد اول است یا نه:

  1. سه متغیر نیاز داریم:
    • a: متغیری که عدد قبلی را در خود نگهدارد و مقدارا ولیه‌ی آن -1 خواهد بود.
    • b: متغیری که عدد فعلی را در خود نگهدارد و مقدارا ولیه‌ی آن 1 خواهد بود.
    • c: متغیری که عدد بعدی را در خود نگهدارد و مقدار آن در ابتدای کار مهم نیست.
  2. عدد قبلی و فعلی را باهم جمع کرده و درون متغیر c قرار می‌دهیم. (c=a+b)
  3. مقدار a را برابر b و مقدار b را برابر a در نظر می‌گیریم. (برای محاسبه‌ی بعدی در صورت نیاز)
  4. اگر c برابر x باشد، پس فیبونانچی است. ولی اگر نباشد، طبیعتا از آن بزرگتر یا کوچکتر خواهد بود.
    حالا اگر بزرگتر از آن باشد، دیگر از مرز رد شده و x هرگز نمی‌تواند یک عدد فیبونانچی باشد. ولی اگر کوچکتر از آن باشد، به مرحله‌ی 2 برگشته و هنوز امیدی برای فیبونانچی بودن عدد وجود دارد. (تکرار)

نکته خیلی مهم: ما مقدار اولیه‌ی a را -1 و b را هم 1 در نظر گرفتیم. ولی شما می‌توانید مقدار اولیه‌ی آنها را از هرجای دنباله که دوست دارید در نظر بگیرید.

پیاده سازی در جاوا/سی‌شارپ/…

نکته
اگر به کد بالا دقت کنید، خواهید دید که مرحله‌ی سوم الگوریتم را در انتهای تابع پیاده‌سازی کرده‌ایم! چراکه طبیعتا بهتر است در ابتدا بررسی کنیم تا اگر نیاز نبود، یک پردازش اضافه صورت نگیرد! (البته نیازی نیست که تا این حد به مبحث بهینه‌سازی الگوریتم خود حساس بوده و وسواس داشته باشید. :D)

تبلیغات
0
کانال تلگرام فول کده
تبلیغات

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

هادی اکبرزاده

[ مدیر فول کده ]

علاقه‌مند به اشتراک گذاری اطلاعات در هر زمینه‌ای / برنامه‌نویس / مدیر فول کده

پاسخ دهید

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

نظرات ثبت شده بدون دیدگاه