biểu Java 8 Lambda để giải quyết fibonacci (cách không đệ quy)

Question

Tôi là một người mới bắt đầu trong việc sử dụng tính năng biểu Lambda trong Java 8. biểu thức Lambda là khá tốt hữu ích trong việc giải quyết các chương trình như kiểm tra số Prime, thừa, vv

Tuy nhiên chúng có thể được sử dụng hiệu quả trong việc giải quyết các vấn đề như Fibonacci, nơi giá trị hiện tại phụ thuộc vào tổng của hai giá trị trước đó. Tôi đã giải quyết tốt vấn đề kiểm tra số nguyên tố một cách hiệu quả bằng cách sử dụng các biểu thức Lambda. Mã cho cùng được đưa ra dưới đây.

boolean checkPrime=n>1 && LongStream.range(2, (long) Math.sqrt(n)).parallel().noneMatch(e->(n)%e==0); 

Trong đoạn mã trên trong noneMatch phương pháp chúng tôi đang đánh giá với giá trị hiện tại (e) trong phạm vi. Nhưng đối với vấn đề Fibonacci, chúng tôi yêu cầu hai giá trị trước đó.

Làm cách nào để chúng tôi có thể thực hiện điều đó?

Answer 1

Giải pháp đơn giản nhất là sử dụng một dòng Pair s:

Stream.iterate(new long[]{ 1, 1 }, p->new long[]{ p[1], p[0]+p[1] }) 
     .limit(92).forEach(p->System.out.println(p[0])); 

Do thiếu một loại cặp tiêu chuẩn, nó sử dụng một mảng hai yếu tố. Hơn nữa, tôi sử dụng .limit(92) vì chúng tôi không thể đánh giá nhiều yếu tố hơn bằng cách sử dụng các giá trị long. Nhưng thật dễ dàng để thích ứng với BigInteger:

Stream.iterate(new BigInteger[]{ BigInteger.ONE, BigInteger.ONE }, 
       p->new BigInteger[]{ p[1], p[0].add(p[1]) }) 
     .forEach(p->System.out.println(p[0])); 

Điều đó sẽ chạy cho đến khi bạn chưa đủ bộ nhớ để đại diện cho giá trị tiếp theo.

BTW, để có được những yếu tố thứ n từ dòng:

Stream.iterate(new long[]{1, 1}, p -> new long[]{p[1], p[0] + p[1]}) 
    .limit(91).skip(90).findFirst().get()[1]; 

Answer 2

giải quyết fibonacci (cách không đệ quy)

này sẽ không xảy ra với cách tiếp cận của bạn

Thế hệ các số Fibonacci dựa trên hai con số trước đó được dựa trên trước hai số, tức là nó là một thuật toán đệ quy, ngay cả khi bạn thực hiện nó mà không đệ quy nhưng trong một vòng lặp. Có những cách khác dựa trên hàm mũ ma trận để bạn có thể tính số thứ tự số n'th mà không tính số n-1 trước đó, nhưng đối với vấn đề của bạn (tính toán chuỗi), điều này không có ý nghĩa.

Vì vậy, để trả lời câu hỏi của bạn cuối cùng, cụ thể là làm cách nào tôi có thể sử dụng biểu thức Lambda trên hai phần tử trước?: có danh sách các bộ dữ liệu, mỗi bộ chứa hai số liên tiếp và lặp lại số đó, thêm một bộ mới mỗi bước.

Answer 3

Nếu bạn muốn có một thực hiện không đệ quy để tìm số thứ n của dãy Fibonacci bạn có thể sử dụng công thức:

Un = ((1+sqrt(5))^n - (1-sqrt(5))^n)/(2^n * sqrt(5)) 

long fibonacci(int n) { 
    return (long) ((Math.pow(1 + Math.sqrt(5), n) - Math.pow(1 - Math.sqrt(5), n))/
     (Math.pow(2, n) * Math.sqrt(5))); 
} 

Answer 4

Để có được yếu tố fibonacci thứ N (sử dụng giảm):

Stream.iterate(new long[] {1, 1}, f -> new long[] {f[1], f[0] + f[1]}) 
    .limit(n) 
    .reduce((a, b) -> b) 
    .get()[0];