آنچه یک برنامه نویس جاوا باید در مورد اعداد فیبوناچی بداند

اغلب در طول مصاحبه ها، به خصوص در شرکت های خارجی، ممکن است از مردم در مورد الگوریتم ها سؤال شود، و در یک موقعیت استرس زا، یادآوری دیوانه وار چیزی همیشه آسان نیست. بنابراین، شما باید آماده شوید. برای شروع، حداقل حافظه خود را از الگوریتم های اساسی تازه کنید. امروز ما پدیده ای مانند اعداد فیبوناچی و رایج ترین انواع مسائل مربوط به آنها را تجزیه و تحلیل خواهیم کرد. اعداد فیبوناچی دنباله ای از اعداد طبیعی هستند که با اعداد صفر و یک شروع می شوند و هر عدد بعدی برابر است با مجموع دو عدد قبلی: F = {0، 1، 1، 2، 3، 5، 8، 13، 21، 34، 55، ...}
F ₀ = 0، F ₁ = 1، F _n = F _{n - 1} + F _{n - 2} ;
n ≥ 0، n ∈ Z

شایان ذکر است که گاهی اوقات 0 حذف می شود و سری با 1 1 2 3 شروع می شود ... قاعدتاً در شرایط مسئله بلافاصله مشخص می شود که سری با کدام دو عدد اول شروع می شود (0.1 یا 1.1). بنابراین در ادامه راه حل هایی را برای هر دو مورد در نظر خواهیم گرفت.

دریافت اولین n عدد فیبوناچی در جاوا

فرض کنید ما وظیفه داریم اولین n عدد فیبوناچی را بدست آوریم.

• مورد 0.1:

  یک عدد مشخص n به ما می رسد:

  int[] arr = new int[n];
  arr[0] = 0;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  آرایه ای به اندازه n ایجاد می کنیم. دو عنصر اول برابر با صفر و یک خواهند بود و عناصر باقیمانده با عبور از این حلقه و استفاده از اعداد قبلی آرایه به دست می آیند.

  و ما نمایش می دهیم:

  for (int i = 0; i < arr.length; ++i) {
    System.out.println(arr[i]);
  }

  int n = 10 را تنظیم کنید.

  و دریافت می کنیم:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• برای مورد 1.1 راه حل در واقع تفاوتی ندارد:

  int[] arr = new int[n];
  arr[0] = 1;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  تنها چیزی که ما نیاز به تغییر داشتیم اولین عنصر آرایه [0] بود: از 0 به 1. بر این اساس، 10 عنصر اول خواهد بود:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

اولین n عدد فیبوناچی از طریق جریان

اما ما می خواهیم سطح خود را نشان دهیم. بنابراین بیایید ببینیم این راه حل با استفاده از جریان چگونه به نظر می رسد .

• برای 0.1:

  Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(y -> y[0])
     .forEach(x -> System.out.println(x));

  متد تکرار ثابت کلاس Stream یک جریان مرتب شده بی نهایت ایجاد شده با اعمال تابع به آرایه اولیه را برمی گرداند. در مورد ما، تابع تنظیم قانون برای ترکیب هر آرایه جدید، بر اساس آرایه قبلی است. در نتیجه، جریانی از آرایه ها را دریافت خواهیم کرد:

  {0,1}
  {1,1}
  {1, 2}
  {2, 3}
  {3, 5}
  {5, 8}
  {8, 13}
  {13, 21}
  {21, 34}
  {34, 55}
  …..

  اما تعداد آنها بی نهایت خواهد بود و بنابراین با استفاده از .limit(n) تعداد عناصر را به n اول کاهش می دهیم (در مورد ما به 10).

  با این حال، ما به جریانی از آرایه ها نیاز نداریم، بنابراین با استفاده از .map(y -> y[0]) اولین عنصر هر آرایه را انتخاب می کنیم و یک جریان با اعداد مورد نیاز خود دریافت می کنیم و با استفاده از forEach آن را در کنسول چاپ می کنیم. .

  خنک تر به نظر می رسد، اینطور نیست؟

  با اولین عناصر 1،1 این کد نیز تقریباً یکسان خواهد بود:

  Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(y -> y[0])
       .forEach(x -> System.out.println(x));

  دوباره، تفاوت ها در عنصر اولیه است: به جای {0، 1}، ما {1، 1} را تنظیم می کنیم.

  در واقع، نتایج مشابه مثال قبلی خواهد بود.

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

اگر از ما خواسته شود که مجموع اعداد فیبوناچی را تا عنصر n که شامل می شود به دست آوریم چطور؟ این نباید برای ما مشکلی ایجاد کند. بیایید یک راه حل با یک جریان در نظر بگیریم و برای هر کدام چند روش دیگر جایگزین کنیم:

• برای 0.1:

  int n = 10;
  int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(t -> t[0])
       .mapToInt(Integer::intValue)
       .sum();
  System.out.println(result);

  با استفاده از .mapToInt(Integer::intValue) جریان خود را به یک IntStream عددی تبدیل می کنیم و از روش .sum() آن برای بدست آوردن مجموع همه عناصر استفاده می کنیم.

• برای مورد با 1،1 عنصر اولیه، به جای {0، 1}، {1، 1} را تنظیم می کنیم.

بدست آوردن عدد n در سری فیبوناچی

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

1. برای 0.1:

   public int getFibonacciValue(int n) {
     if (n <= 1) {
        return 0;
     } else if (n == 2) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   برای اجرای الگوریتم با 0،1، لازم است مشخص کنیم که وقتی می خواهیم عنصر اول را بدست آوریم، 0 و دومی - 1 می گیریم. در واقع، مانند راه حل های قبلی، باید دو عنصر اول را تنظیم کنیم. عناصر.

2. اجرای 1.1 کمی متفاوت خواهد بود:

   public int getFibonacciValue(int n) {
     if (n == 0) {
        return 0;
     } else if (n == 1) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   در این حالت فقط باید عنصر اول را 1 تنظیم کنیم، زیرا عنصر دوم یکسان خواهد بود و پاسخ متد نیز یکسان خواهد بود.

   در همان زمان، واکنش متد را روی 0 قرار می دهیم، زیرا اگر آن را تنظیم نکنیم، وقتی 2 به عنوان آرگومان می آید، همان متد به صورت بازگشتی فراخوانی می شود، اما با آرگومان 0. بعد، همان متد راه اندازی می شود. ، اما با اعداد منفی و غیره تا بی نهایت منفی. در نتیجه، یک خطای StackOverflow دریافت خواهیم کرد .

با این حال، روش بازگشتی توصیه نمی‌شود، زیرا برخلاف روش‌های قبلی که در زمان O(n) خطی اجرا می‌شوند، تکمیل روش بازگشتی می‌تواند به طور قابل توجهی بیشتر طول بکشد. چرا؟ روش بازگشتی می تواند زمان زیادی طول بکشد، زیرا در طول فرآیند محاسبه، تابع بارها از همان آرگومان فراخوانی می شود. به عنوان مثال، هنگام ارزیابی getFibonacciValue(7)، این تابع با getFibonacciValue(5) و getFibonacciValue(6) بازگشتی فراخوانی می کند، هر دو فراخوانی بازگشتی getFibonacciValue(4) را فراخوانی می کنند، که منجر به فراخوانی چندین عملیات مشابه می شود. در مصاحبه می توانید این روش را به عنوان یک راه حل نشان دهید، اما در عین حال از کاستی های آن صحبت کنید و در ازای آن روش دیگری ارائه دهید. همچنین شایان ذکر است که نوع int در جاوا به شما امکان ذخیره سازی از 2147483648- تا 2147483647 را می دهد، بنابراین شما فقط می توانید 46 عدد فیبوناچی اول را محاسبه کنید: اگر سعی کنیم عدد 47 بعدی را بدست آوریم، یک سرریز وجود خواهد داشت و یک عدد منفی دریافت خواهیم کرد. اگر به جای int از نوع داده long استفاده کنیم، می توانیم 91 عدد فیبوناچی اول را به درستی محاسبه کنیم. برای محاسبه اعداد فیبوناچی بعدی، باید از کلاس BigInteger استفاده کنید که منطق ذخیره سازی و عملیات حسابی اعداد واقعا بزرگ را پیاده سازی می کند.