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

شرح الگوریتم

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

• دو عدد اول 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;
  }
}