جاوا پروگرامر کي فبونيڪي نمبرن بابت ڇا ڄاڻڻ گهرجي

گهڻو ڪري انٽرويو دوران، خاص طور تي پرڏيهي ڪمپنين ۾، ماڻهن کان پڇيو وڃي ٿو الگورتھم بابت، ۽ هڪ دٻاء واري صورتحال ۾، ڪنهن شيء کي ياد رکڻ هميشه آسان ناهي. تنهن ڪري، توهان کي تيار ڪرڻ جي ضرورت آهي. شروع ڪرڻ سان، گهٽ ۾ گهٽ توهان جي ياداشت جي بنيادي الگورتھم کي تازو ڪريو. اڄ اسان فبونيڪي انگن ۽ انهن سان لاڳاپيل مسئلن جي سڀ کان عام قسم جي طور تي اهڙي رجحان جو تجزيو ڪنداسين. فبونيڪي نمبر قدرتي انگن جو هڪ سلسلو آهي جيڪو صفر ۽ هڪ نمبرن سان شروع ٿئي ٿو، ۽ هر ايندڙ نمبر پوئين ٻن جي رقم جي برابر آهي: 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 Fibonacci نمبر حاصل ڪرڻ جو ڪم آهي.

• ڪيس 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 Fibonacci نمبر وهڪرو ذريعي

پر اسان پنهنجي سطح کي ڏيکارڻ چاهيون ٿا. سو اچو ته ڏسون ته هي حل stream استعمال ڪرڻ جهڙو نظر ايندو .

• 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));

  اسٽريم ڪلاس جو جامد ورجائي طريقو هڪ لامحدود آرڊر ٿيل وهڪرو واپس ڪري ٿو جيڪو فنڪشن کي لاڳو ڪندي ابتدائي صف آرر تي لاڳو ڪري ٿو. اسان جي حالت ۾، فنڪشن هر نئين صف کي ترتيب ڏيڻ لاء قاعدو مقرر ڪرڻ آهي، پوئين هڪ جي بنياد تي. نتيجي طور، اسان صفن جو سلسلو حاصل ڪنداسين:

  {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}

  دراصل، نتيجا ساڳيا ئي هوندا جيئن اڳئين مثال ۾.

Fibonacci انگن جو مجموعو

ڇا جيڪڏهن اسان کي فبونيڪي نمبرن جو مجموعو حاصل ڪرڻ لاءِ چيو ويو ته nth عنصر تائين شامل آهي؟ اهو اسان کي ڪنهن به مشڪلات جو سبب نه هجڻ گهرجي. اچو ته هڪ وهڪرو سان هڪ حل وٺو ۽ هر هڪ کي ٻين طريقن سان تبديل ڪريو:

• 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}.

فبونيڪي سيريز ۾ نمبر نمبر حاصل ڪرڻ

ڪڏهن ڪڏهن توهان کي پرنٽ ڪرڻ لاءِ چيو ويندو آهي انگن جو سلسلو نه، پر خاص طور تي فبونيڪي سيريز ۾ نمبر نمبر. ضابطي جي طور تي، اهو صرف ڪم کي آسان بڻائي ٿو، ڇاڪاڻ ته توهان آساني سان هن لاء اڳوڻي حل کي ترتيب ڏئي سگهو ٿا. خير، ٻيهر ورجائي ذريعي مسئلو حل ڪرڻ بابت ڇا؟

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 سان. اڳتي هلي، ساڳيو طريقو شروع ڪيو ويندو. ، پر منفي انگن سان، ۽ ائين ئي منفي لامحدوديت تائين. نتيجي طور، اسان حاصل ڪنداسين StackOverflowError .

بهرحال، ٻيهر ورجائڻ وارو طريقو سفارش نه ڪيو ويو آهي ڇاڪاڻ ته اڳئين طريقن جي برعڪس، جيڪي لڪير O(n) وقت ۾ هلن ٿا، ٻيهر ورجائيندڙ طريقو مڪمل ٿيڻ ۾ گهڻو وقت وٺي سگھي ٿو. ڇو؟ recursive طريقو هڪ ڊگهو وقت وٺي سگھي ٿو، ڇاڪاڻ ته حساب جي عمل دوران، فنڪشن کي ساڳئي دليل کان ڪيترائي ڀيرا سڏيو ويندو. مثال طور، جڏهن getFibonacciValue(7) جو جائزو وٺندي، فنڪشن getFibonacciValue(5) ۽ getFibonacciValue(6) کي بار بار ڪالون ڪندو، ٻئي ريٽرسي ڪالون getFibonacciValue(4) کي ڪال ڪنديون، جنهن جي نتيجي ۾ ساڳئي آپريشن کي ڪيترائي ڀيرا ڪال ڪيو ويندو. انٽرويو ۾، توهان هن طريقي کي حل طور ڏيکاري سگهو ٿا، پر ساڳئي وقت ان جي گهٽتائي بابت ڳالهايو ۽ موٽ ۾ ٻيو طريقو پيش ڪيو. اهو پڻ قابل ذڪر آهي ته جاوا ۾ int قسم توهان کي -2147483648 کان 2147483647 تائين ذخيرو ڪرڻ جي اجازت ڏئي ٿو، تنهنڪري توهان صرف پهرين 46 فبونيڪي نمبرن کي ڳڻڻ جي قابل هوندا: جيڪڏهن اسان ايندڙ 47 نمبر حاصل ڪرڻ جي ڪوشش ڪندا، اتي هڪ اوور فلو ٿيندو ۽ اسان هڪ منفي نمبر حاصل ڪنداسين. جيڪڏهن اسان int جي بدران ڊگھي ڊيٽا جو قسم استعمال ڪريون ٿا، ته اسان پهرين 91 Fibonacci انگن جو صحيح حساب ڪري سگهنداسين. ايندڙ Fibonacci انگن کي ڳڻڻ لاءِ، توھان کي استعمال ڪرڻ جي ضرورت آھي BigInteger ڪلاس، جيڪو واقعي BIG نمبرن جي اسٽوريج ۽ رياضي واري عمل لاءِ منطق لاڳو ڪري ٿو.