Những điều lập trình viên Java nên biết về số Fibonacci

Thông thường trong các cuộc phỏng vấn, đặc biệt là ở các công ty nước ngoài, mọi người có thể được hỏi về các thuật toán, và trong tình huống căng thẳng, việc ghi nhớ một cách điên cuồng điều gì đó không phải lúc nào cũng dễ dàng. Vì vậy, bạn cần phải chuẩn bị. Để bắt đầu, ít nhất hãy làm mới trí nhớ của bạn về các thuật toán cơ bản. Hôm nay chúng ta sẽ phân tích một hiện tượng như số Fibonacci và các biến thể phổ biến nhất của các vấn đề liên quan đến chúng. Số Fibonacci là một dãy số tự nhiên bắt đầu bằng số 0 và số 1, mỗi số tiếp theo bằng tổng của hai số trước đó: 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

Điều đáng chú ý là đôi khi số 0 bị bỏ qua và chuỗi bắt đầu bằng 1 1 2 3... Theo quy định, trong điều kiện của bài toán, người ta chỉ định ngay hai số đầu tiên của chuỗi bắt đầu bằng (0,1 hoặc 1,1), vì vậy chúng tôi sẽ xem xét giải pháp cho cả hai trường hợp.

Lấy n số Fibonacci đầu tiên trong Java

Giả sử chúng ta có nhiệm vụ thu được n số Fibonacci đầu tiên.

• trường hợp 0,1:

  Một số n nhất định đến với chúng ta:

  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];
  }

  Chúng tôi tạo ra một mảng có kích thước n. Hai phần tử đầu tiên sẽ bằng 0 và một, các phần tử còn lại có được bằng cách thực hiện vòng lặp này và sử dụng các số trước đó trong mảng.

  Và chúng tôi hiển thị:

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

  Đặt int n = 10;

  Và chúng tôi nhận được:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• đối với trường hợp 1.1, giải pháp thực sự không khác:

  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];
  }

  Tất cả những gì chúng ta cần thay đổi là phần tử đầu tiên của mảng arr[0]: từ 0 thành 1. Theo đó, 10 phần tử đầu tiên sẽ là:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

n số Fibonacci đầu tiên qua luồng

Nhưng chúng tôi muốn thể hiện đẳng cấp của mình. Vì vậy, hãy xem giải pháp này sẽ như thế nào khi sử dụng luồng .

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

  Phương thức lặp tĩnh của lớp Stream trả về một luồng có thứ tự vô hạn được tạo bằng cách áp dụng hàm cho mảng mảng ban đầu. Trong trường hợp của chúng tôi, chức năng này là đặt quy tắc soạn từng mảng mới, dựa trên mảng trước đó. Kết quả là chúng ta sẽ nhận được một dòng mảng:

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

  Nhưng sẽ có vô số chúng, và do đó, bằng cách sử dụng .limit(n), chúng ta giảm số phần tử xuống n đầu tiên (trong trường hợp của chúng ta là 10).

  Tuy nhiên, chúng ta không cần một luồng mảng, vì vậy, bằng cách sử dụng .map(y -> y[0]), chúng ta chọn phần tử đầu tiên của mỗi mảng và lấy một luồng có các số chúng ta cần và in nó ra bảng điều khiển bằng forEach .

  Trông ngầu hơn phải không?

  với các phần tử đầu tiên là 1,1, mã này cũng sẽ gần giống nhau:

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

  Một lần nữa, sự khác biệt nằm ở phần tử ban đầu: thay vì {0, 1} chúng ta đặt {1, 1}

  Trên thực tế, kết quả sẽ giống như trong ví dụ trước.

Tổng các số Fibonacci

Điều gì sẽ xảy ra nếu chúng ta được yêu cầu tính tổng các số Fibonacci cho đến phần tử thứ n? Điều này sẽ không gây cho chúng ta bất kỳ khó khăn nào. Hãy tìm giải pháp bằng một luồng và thay thế forEach bằng một vài phương pháp khác:

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

  Bằng cách sử dụng .mapToInt(Integer::intValue), chúng ta chuyển đổi luồng của mình thành IntStream dạng số và sử dụng phương thức .sum() của nó để lấy tổng của tất cả các phần tử.

• đối với trường hợp có 1,1 phần tử ban đầu, thay vì {0, 1} chúng ta đặt {1, 1}.

Lấy số thứ n trong dãy Fibonacci

Đôi khi bạn được yêu cầu in không phải một dãy số mà cụ thể là số thứ n trong dãy Fibonacci. Theo quy định, điều này chỉ làm cho công việc trở nên dễ dàng hơn vì bạn có thể dễ dàng điều chỉnh các giải pháp trước đó cho việc này. Vậy còn việc giải quyết vấn đề bằng đệ quy thì sao?

1. cho 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);
     }
   }

   Để chạy thuật toán với 0,1, cần phải xác định rõ rằng khi chúng ta cố lấy phần tử đầu tiên, chúng ta nhận được 0 và phần tử thứ hai - 1. Trên thực tế, chúng ta, như trong các giải pháp trước, cần đặt hai phần tử đầu tiên các phần tử.

2. việc triển khai cho 1.1 sẽ hơi khác một chút:

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

   Trong trường hợp này, chúng ta chỉ cần đặt phần tử đầu tiên là 1, vì phần tử thứ hai sẽ giống nhau và phản hồi của phương thức sẽ giống nhau.

   Đồng thời, chúng ta đặt phản ứng của phương thức thành 0, vì nếu chúng ta không đặt nó, thì khi 2 xuất hiện dưới dạng đối số, phương thức tương tự sẽ được gọi đệ quy, nhưng với đối số 0. Tiếp theo, phương thức tương tự sẽ được khởi chạy , nhưng với số âm, v.v. cho đến âm vô cực. Kết quả là chúng ta sẽ nhận được StackOverflowError .

Tuy nhiên, phương pháp đệ quy không được khuyến khích vì không giống như các phương pháp trước đó, chạy trong thời gian tuyến tính O(n), phương pháp đệ quy có thể mất nhiều thời gian hơn để hoàn thành. Tại sao? Phương pháp đệ quy có thể mất nhiều thời gian vì trong quá trình tính toán, hàm sẽ được gọi nhiều lần từ cùng một đối số. Ví dụ: khi đánh giá getFibonacciValue(7), hàm sẽ thực hiện lệnh gọi đệ quy tới getFibonacciValue(5) và getFibonacciValue(6), cả hai lệnh gọi đệ quy sẽ gọi getFibonacciValue(4)), điều này sẽ dẫn đến việc gọi cùng một thao tác nhiều lần. Tại cuộc phỏng vấn, bạn có thể chỉ ra phương pháp này như một giải pháp, nhưng đồng thời nói về những khuyết điểm của nó và đưa ra một phương pháp khác để đáp lại. Cũng cần lưu ý rằng kiểu int trong Java cho phép bạn lưu trữ từ -2147483648 đến 2147483647, do đó bạn sẽ chỉ có thể tính 46 số Fibonacci đầu tiên: nếu chúng ta cố lấy số thứ 47 tiếp theo, sẽ có tràn và chúng ta sẽ nhận được một số âm. Nếu sử dụng kiểu dữ liệu long thay vì int, chúng ta sẽ có thể tính toán chính xác 91 số Fibonacci đầu tiên. Để tính các số Fibonacci tiếp theo, bạn cần sử dụng lớp BigInteger, lớp này triển khai logic để lưu trữ và thực hiện các phép tính số học của các số thực sự LỚN.