جاوا پروگرامر کو فبونیکی نمبرز کے بارے میں کیا معلوم ہونا چاہیے۔

اکثر انٹرویوز کے دوران، خاص طور پر غیر ملکی کمپنیوں میں، لوگوں سے الگورتھم کے بارے میں پوچھا جا سکتا ہے، اور ایک دباؤ والی صورتحال میں، کسی چیز کو بے دلی سے یاد رکھنا ہمیشہ آسان نہیں ہوتا ہے۔ لہذا، آپ کو تیار کرنے کی ضرورت ہے. شروع کرنے کے لیے، کم از کم بنیادی الگورتھم کی اپنی یادداشت کو تازہ کریں۔ آج ہم فبونیکی نمبرز اور ان سے متعلق مسائل کی سب سے عام قسموں جیسے رجحان کا تجزیہ کریں گے۔ فبونیکی نمبرز قدرتی اعداد کا ایک سلسلہ ہے جو صفر اور ایک نمبر سے شروع ہوتا ہے، اور اس کے بعد آنے والا ہر نمبر پچھلے دو کے مجموعے کے برابر ہے: 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 فبونیکی نمبرز حاصل کرنے کا کام ہے۔

• کیس 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];
  }

  ہمیں صرف array arr[0] کا پہلا عنصر تبدیل کرنے کی ضرورت تھی: 0 سے 1 تک۔ اس کے مطابق، پہلے 10 عناصر ہوں گے:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

سٹریم کے ذریعے پہلے n فبونیکی نمبرز

لیکن ہم اپنی سطح دکھانا چاہتے ہیں۔ تو آئیے دیکھتے ہیں کہ یہ حل استعمال کرنے سے کیسا نظر آئے گا 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));

  Stream کلاس کا static iterate طریقہ ایک لامحدود ترتیب شدہ سلسلہ واپس کرتا ہے جو فنکشن کو ابتدائی array arr پر لاگو کرکے تخلیق کیا گیا ہے۔ ہمارے معاملے میں، فنکشن یہ ہے کہ ہر نئی صف کو کمپوز کرنے کے لیے اصول مقرر کیا جائے، جو پچھلے ایک کی بنیاد پر ہے۔ نتیجے کے طور پر، ہمیں صفوں کا ایک سلسلہ ملے گا:

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

  دراصل، نتائج وہی ہوں گے جو پچھلی مثال میں تھے۔

فبونیکی نمبروں کا مجموعہ

کیا ہوگا اگر ہم سے کہا جائے کہ فبونیکی نمبرز کا مجموعہ نویں عنصر تک شامل کیا جائے؟ اس سے ہمیں کوئی مشکل نہیں ہونی چاہیے۔ آئیے ایک اسٹریم کے ساتھ حل لیں اور forEach کو کچھ دوسرے طریقوں سے تبدیل کریں:

• 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) وقت میں چلتے ہیں، تکراری طریقہ کو مکمل ہونے میں کافی زیادہ وقت لگ سکتا ہے۔ کیوں؟ تکراری طریقہ میں کافی وقت لگ سکتا ہے، کیونکہ حساب کے عمل کے دوران فنکشن کو ایک ہی دلیل سے کئی بار کال کیا جائے گا۔ مثال کے طور پر، getFibonacciValue(7) کا جائزہ لیتے وقت، فنکشن getFibonacciValue(5) اور getFibonacciValue(6) کو بار بار آنے والی کالیں کرے گا، دونوں تکراری کالیں getFibonacciValue(4) کو کال کریں گی، جس کے نتیجے میں ایک ہی آپریشن کو متعدد بار کال کرنا پڑے گا۔ انٹرویو میں آپ اس طریقے کو حل کے طور پر دکھا سکتے ہیں، لیکن ساتھ ہی اس کی خامیوں کے بارے میں بات کریں اور بدلے میں کوئی اور طریقہ پیش کریں۔ یہ بات بھی قابل غور ہے کہ جاوا میں int قسم آپ کو -2147483648 سے لے کر 2147483647 تک ذخیرہ کرنے کی اجازت دیتی ہے، اس لیے آپ صرف پہلے 46 فبونیکی نمبروں کا حساب لگا سکیں گے: اگر ہم اگلی 47 ویں نمبر کو حاصل کرنے کی کوشش کریں گے، تو ایک اوور فلو ہو جائے گا اور ہمیں ایک منفی نمبر ملے گا۔ اگر ہم int کے بجائے لمبی ڈیٹا ٹائپ استعمال کرتے ہیں، تو ہم پہلے 91 فبونیکی نمبروں کا صحیح حساب لگا سکیں گے۔ بعد میں آنے والے فبونیکی نمبروں کا حساب لگانے کے لیے، آپ کو BigInteger کلاس استعمال کرنے کی ضرورت ہے، جو واقعی BIG نمبروں کو ذخیرہ کرنے اور ریاضی کی کارروائیوں کے لیے منطق کو نافذ کرتی ہے۔