สิ่งที่โปรแกรมเมอร์ Java ควรรู้เกี่ยวกับตัวเลขฟีโบนักชี

บ่อยครั้งในระหว่างการสัมภาษณ์ โดยเฉพาะในบริษัทต่างประเทศ ผู้คนอาจถูกถามเกี่ยวกับอัลกอริธึม และในสถานการณ์ที่ตึงเครียด การจดจำบางสิ่งอย่างเมามันไม่ใช่เรื่องง่ายเสมอไป ดังนั้นคุณจึงต้องเตรียมตัว ขั้นแรก อย่างน้อยที่สุดก็รีเฟรชหน่วยความจำของอัลกอริธึมพื้นฐาน วันนี้เราจะวิเคราะห์ปรากฏการณ์เช่นตัวเลขฟีโบนัชชีและปัญหารูปแบบต่างๆ ที่พบบ่อยที่สุดที่เกี่ยวข้อง หมายเลขฟีโบนัชชีเป็นลำดับของจำนวนธรรมชาติที่ขึ้นต้นด้วยตัวเลขศูนย์และหนึ่ง และตัวเลขที่ตามมาแต่ละตัวจะเท่ากับผลรวมของสองตัวก่อนหน้า: 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 ตัวแรกใน Java

สมมติว่าเรามีภารกิจในการรับหมายเลข 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];
  }

  สิ่งที่เราจำเป็นต้องเปลี่ยนคือองค์ประกอบแรกของอาร์เรย์ arr[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));

  วิธีการวนซ้ำแบบคงที่ของคลาสStreamส่งคืนสตรีมที่เรียงลำดับไม่สิ้นสุดที่สร้างขึ้นโดยการใช้ฟังก์ชันกับอาร์เรย์เริ่มต้น 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}

  จริงๆ แล้วผลลัพธ์จะเหมือนกับในตัวอย่างก่อนหน้า

ผลรวมของตัวเลขฟีโบนัชชี

จะเป็นอย่างไรหากเราถูกขอให้หาผลรวมของตัวเลขฟีโบนัชชีจนถึงองค์ประกอบที่ n ด้วย? สิ่งนี้ไม่ควรทำให้เราลำบาก ลองใช้วิธีแก้ปัญหาด้วยสตรีมและแทนที่ 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 ดังนั้นคุณจะสามารถคำนวณตัวเลข Fibonacci 46 ตัวแรกเท่านั้น หากเราพยายามหาตัวเลขที่ 47 ถัดไป จะเกิดโอเวอร์โฟลว์และ เราจะได้จำนวนลบ หากเราใช้ชนิดข้อมูลแบบยาวแทน int เราจะสามารถคำนวณตัวเลขฟีโบนักชี 91 ตัวแรกได้อย่างถูกต้อง ในการคำนวณหมายเลขฟีโบนัชชีลำดับต่อมา คุณต้องใช้คลาส BigInteger ซึ่งใช้ตรรกะสำหรับการจัดเก็บและการดำเนินการทางคณิตศาสตร์ของตัวเลขที่ใหญ่มาก