تبلیغات

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

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

فیبونانچی

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

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

در این دنباله، دو عدد اول را 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 در نظر گرفتیم. ولی شما می‌توانید مقدار اولیه‌ی آنها را از هرجای دنباله که دوست دارید در نظر بگیرید.

پیاده‌سازی

این کد در جاوا و سی‌شارپ پیاده‌سازی شده ست.

bool isFibo(int number) {
  int before = -1;
  int current = 1;
  int next;
  while (true) {
    next = before + current;
    if (next == number) {
      return true;
    }
    else if (next > number) {
      return false;
    }

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

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

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

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

علاقه‌مند به اشتراک‌گذاری اطلاعات در هر زمینه‌ای که امکانش باشه 🙃

پاسخ دهید

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

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

توضیحات پیشنهادی نظرات اشتراک