ما يجب أن يعرفه مبرمج جافا عن أرقام فيبوناتشي

في كثير من الأحيان أثناء المقابلات، خاصة في الشركات الأجنبية، قد يُسأل الأشخاص عن الخوارزميات، وفي المواقف العصيبة، ليس من السهل دائمًا تذكر شيء ما بشكل محموم. لذلك، تحتاج إلى الاستعداد. للبدء، على الأقل قم بتحديث ذاكرتك بالخوارزميات الأساسية. اليوم سنقوم بتحليل ظاهرة مثل أرقام فيبوناتشي والمتغيرات الأكثر شيوعًا للمشاكل المرتبطة بها. أرقام فيبوناتشي هي سلسلة من الأعداد الطبيعية تبدأ بالرقمين صفر وواحد، وكل رقم لاحق يساوي مجموع الرقمين السابقين: F = {0، 1، 1، 2، 3، 5، 8، 13، 21، 34، 55، ...}
F ₀ = 0، F ₁ = 1، F _n = F _{n - 1} + F _{n - 2} ;
ن ≥ 0، ن ∈ 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]);
  }

  تعيين كثافة العمليات ن = 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];
  }

  كل ما نحتاج إلى تغييره هو العنصر الأول في المصفوفة arr[0]: من 0 إلى 1. وبناءً على ذلك، ستكون العناصر العشرة الأولى هي:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

أول أرقام فيبوناتشي ن عبر الدفق

لكننا نريد أن نظهر مستوانا. لذلك دعونا نرى كيف سيبدو هذا الحل باستخدام الدفق .

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

  في الواقع، ستكون النتائج هي نفسها كما في المثال السابق.

مجموع أرقام فيبوناتشي

ماذا لو طُلب منا الحصول على مجموع أرقام فيبوناتشي حتى العنصر التاسع ضمناً؟ وهذا لا ينبغي أن يسبب لنا أي صعوبات. لنأخذ الحل باستخدام المجرى ونستبدل 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}.

الحصول على الرقم 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. بعد ذلك، سيتم إطلاق نفس الطريقة ولكن بأرقام سالبة، وهكذا حتى اللانهاية السالبة. ونتيجة لذلك، سوف نتلقى خطأ StackOverflowError .

ومع ذلك، لا يوصى باستخدام الطريقة العودية لأنه على عكس الطرق السابقة، التي تعمل في زمن O(n) الخطي، يمكن أن تستغرق الطريقة العودية وقتًا أطول بكثير لإكمالها. لماذا؟ يمكن أن تستغرق الطريقة العودية وقتًا طويلاً، لأنه أثناء عملية الحساب سيتم استدعاء الدالة عدة مرات من نفس الوسيطة. على سبيل المثال، عند تقييم getFibonacciValue(7)، ستقوم الدالة بإجراء مكالمات متكررة إلى getFibonacciValue(5) وgetFibonacciValue(6)، وستستدعي كلا الاستدعاءات المتكررة getFibonacciValue(4))، مما سيؤدي إلى استدعاء نفس العمليات عدة مرات. في المقابلة، يمكنك إظهار هذه الطريقة كحل، ولكن في نفس الوقت تحدث عن عيوبها وقدم طريقة أخرى في المقابل. تجدر الإشارة أيضًا إلى أن النوع int في Java يسمح لك بالتخزين من -2147483648 إلى 2147483647، لذلك ستتمكن فقط من حساب أول 46 رقمًا فيبوناتشي: إذا حاولنا الحصول على الرقم 47 التالي، فسيكون هناك تجاوز و سوف نحصل على رقم سلبي. إذا استخدمنا نوع البيانات الطويلة بدلاً من int، فسنكون قادرين على حساب أول 91 رقمًا فيبوناتشي بشكل صحيح. لحساب أرقام فيبوناتشي اللاحقة، تحتاج إلى استخدام فئة BigInteger، التي تنفذ منطق التخزين والعمليات الحسابية للأرقام الكبيرة حقًا.