Java 재귀 피보나치 시퀀스
이 간단한 코드를 설명해 주세요.
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
예를 들어 n = 5이면 피보나치(4) + 피보나치(3)가 호출되는 등 특히 마지막 행과 혼동되지만 이 알고리즘이 이 방법으로 지수 5의 값을 계산하는 방법을 이해할 수 없습니다.자세히 설명해 주세요!
피보나치 시퀀스에서 각 항목은 이전 두 항목의 합계입니다.재귀 알고리즘을 작성하셨군요
그렇게,
fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(2) = fibonacci(1) + fibonacci(0)
알고 있습니다.fibonacci(1)==1 and fibonacci(0) == 0하다
지금이다,
fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5
시퀀스로부터0,1,1,2,3,5,8,13,21.... 보면 알 수 요.5th element는 fibonacci를 합니다.5.
재귀 자습서는 여기를 참조하십시오.
코드에는 다음 2가지 문제가 있습니다.
- 결과는 처음 48개의 피보나치 숫자만 처리할 수 있는int에 저장되며, 이후 정수 채우기 마이너스 비트와 결과가 잘못되었습니다.
- 피보나치(50)
(드)
fibonacci(n - 1) + fibonacci(n - 2)
매우 잘못되었다.
문제는 그것이 피보나찌를 50회 호출하는 것이 아니라 훨씬 더 많이 호출한다는 것입니다.
fibonacci(48)를 호출합니다.
fibonacci46);;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
피보나치(n)가 악화될 때마다 복잡도는 기하급수적으로 증가합니다.
비재귀 코드에 대한 접근법:
double fibbonaci(int n){
double prev=0d, next=1d, result=0d;
for (int i = 0; i < n; i++) {
result=prev+next;
prev=next;
next=result;
}
return result;
}
의사 코드(n = 5)에서는 다음이 발생합니다.
fibonacci(4) + fibonnacci(3)
이것은 다음과 같이 분류됩니다.
(autonacci(3) + fibonnacci(2) + (autonacci(2) + fibonnacci(1))
이것은 다음과 같이 분류됩니다.
(((autonacci (2) + fibonnacci (1) + (autonacci (1) + fibonnacci (0)) + (((autonacci (1) + fibonnacci (0) + 1))))
이것은 다음과 같이 분류됩니다.
((((natonacci(1) + fibonnacci(0) + 1) + (1 + 0) + (1 + 0) + 1))
이것은 다음과 같이 분류됩니다.
((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))
그 결과: 5
fibonnacci 시퀀스가 1 1 2 3 5 8 ...인 경우, 5번째 요소는 5입니다.동일한 방법을 사용하여 다른 반복을 계산할 수 있습니다.
다음과 같이 기능을 단순화할 수도 있습니다.
public int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
재귀는 때때로 이해하기 어려울 수 있습니다.종이 한 장에 적은 숫자에 대해 평가해 보십시오.
fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3
Java가 실제로 어떻게 평가하는지 모르겠지만 결과는 동일합니다.
F(n)
/ \
F(n-1) F(n-2)
/ \ / \
F(n-2) F(n-3) F(n-3) F(n-4)
/ \
F(n-3) F(n-4)
주의할 점은 이 알고리즘은 이전에 계산된 숫자의 결과를 저장하지 않기 때문에 지수적이라는 것입니다.예를 들어 F(n-3)는 3회 호출됩니다.
자세한 내용은 dasgupta 장 0.2의 알고리즘을 참조하십시오.
대부분의 답변은 양호하며 피보나찌의 재귀가 어떻게 작동하는지 설명합니다.
다음은 재귀도 포함하는 세 가지 기술에 대한 분석입니다.
- 루프의 경우
- 재귀
- 메모화
이 세 가지를 모두 테스트하기 위한 코드는 다음과 같습니다.
public class Fibonnaci {
// Output = 0 1 1 2 3 5 8 13
static int fibMemo[];
public static void main(String args[]) {
int num = 20;
System.out.println("By For Loop");
Long startTimeForLoop = System.nanoTime();
// returns the fib series
int fibSeries[] = fib(num);
for (int i = 0; i < fibSeries.length; i++) {
System.out.print(" " + fibSeries[i] + " ");
}
Long stopTimeForLoop = System.nanoTime();
System.out.println("");
System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));
System.out.println("By Using Recursion");
Long startTimeRecursion = System.nanoTime();
// uses recursion
int fibSeriesRec[] = fibByRec(num);
for (int i = 0; i < fibSeriesRec.length; i++) {
System.out.print(" " + fibSeriesRec[i] + " ");
}
Long stopTimeRecursion = System.nanoTime();
System.out.println("");
System.out.println("Recursion Time:" + (stopTimeRecursion -startTimeRecursion));
System.out.println("By Using Memoization Technique");
Long startTimeMemo = System.nanoTime();
// uses memoization
fibMemo = new int[num];
fibByRecMemo(num-1);
for (int i = 0; i < fibMemo.length; i++) {
System.out.print(" " + fibMemo[i] + " ");
}
Long stopTimeMemo = System.nanoTime();
System.out.println("");
System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));
}
//fib by memoization
public static int fibByRecMemo(int num){
if(num == 0){
fibMemo[0] = 0;
return 0;
}
if(num ==1 || num ==2){
fibMemo[num] = 1;
return 1;
}
if(fibMemo[num] == 0){
fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
return fibMemo[num];
}else{
return fibMemo[num];
}
}
public static int[] fibByRec(int num) {
int fib[] = new int[num];
for (int i = 0; i < num; i++) {
fib[i] = fibRec(i);
}
return fib;
}
public static int fibRec(int num) {
if (num == 0) {
return 0;
} else if (num == 1 || num == 2) {
return 1;
} else {
return fibRec(num - 1) + fibRec(num - 2);
}
}
public static int[] fib(int num) {
int fibSum[] = new int[num];
for (int i = 0; i < num; i++) {
if (i == 0) {
fibSum[i] = i;
continue;
}
if (i == 1 || i == 2) {
fibSum[i] = 1;
continue;
}
fibSum[i] = fibSum[i - 1] + fibSum[i - 2];
}
return fibSum;
}
}
결과는 다음과 같습니다.
By For Loop
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
For Loop Time:347688
By Using Recursion
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Recursion Time:767004
By Using Memoization Technique
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Memoization Time:327031
따라서 메모화가 최적의 타이밍이며 루프가 근접하게 일치함을 알 수 있습니다.
그러나 재귀가 가장 오래 걸리고 현실에서는 피해야 할 수도 있습니다.또한 재귀를 사용하는 경우 솔루션을 최적화해야 합니다.
이것은 Java에서의 재귀와 피보나치 시퀀스에 대해 자세히 설명하는 최고의 비디오입니다.
http://www.youtube.com/watch?v=dsmBRUCzS7k
이것은 그의 시퀀스 코드이고 그의 설명은 내가 타이핑하는 것보다 더 훌륭하다.
public static void main(String[] args)
{
int index = 0;
while (true)
{
System.out.println(fibonacci(index));
index++;
}
}
public static long fibonacci (int i)
{
if (i == 0) return 0;
if (i<= 2) return 1;
long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
return fibTerm;
}
fibonacci 재귀 솔루션에서는 작은 fibonacci 숫자의 출력을 저장하고 큰 숫자의 값을 취득하는 것이 중요합니다.이걸 '메모이징'이라고 해요.
다음으로 작은 fibonacci 값을 메모화하고 큰 fibonacci 번호를 취득하는 코드를 나타냅니다.이 코드는 효율적이며 동일한 기능의 여러 요청을 하지 않습니다.
import java.util.HashMap;
public class Fibonacci {
private HashMap<Integer, Integer> map;
public Fibonacci() {
map = new HashMap<>();
}
public int findFibonacciValue(int number) {
if (number == 0 || number == 1) {
return number;
}
else if (map.containsKey(number)) {
return map.get(number);
}
else {
int fibonacciValue = findFibonacciValue(number - 2) + findFibonacciValue(number - 1);
map.put(number, fibonacciValue);
return fibonacciValue;
}
}
}
피보나치 시퀀스에서 처음 두 항목은 0과 1이고, 다른 각 항목은 이전 두 항목의 합계이다.예:
1238 ... 0 1 2 3 5 8 ...
그래서 다섯 번째 항목은 네 번째와 세 번째 항목의 합계입니다.
Michael Goodrich 등은 [fib(n), fib(n-1)]의 배열을 반환함으로써 선형 시간 내에 피보나찌를 재귀적으로 해결하기 위해 Java의 Data Structures and Algorithms에서 매우 현명한 알고리즘을 제공합니다.
public static long[] fibGood(int n) {
if (n < = 1) {
long[] answer = {n,0};
return answer;
} else {
long[] tmp = fibGood(n-1);
long[] answer = {tmp[0] + tmp[1], tmp[0]};
return answer;
}
}
그러면 fib(n) = fibGood(n)[0]가 생성됩니다.
O(1) 솔루션은 다음과 같습니다.
private static long fibonacci(int n) {
double pha = pow(1 + sqrt(5), n);
double phb = pow(1 - sqrt(5), n);
double div = pow(2, n) * sqrt(5);
return (long) ((pha - phb) / div);
}
위의 구현에 사용되는 Binet의 피보나치 수식.대규모 입력의 경우long로 할 수 BigDecimal.
Fibbonacci 시퀀스는 1로 시작하는 이전 결과에 더했을 때 숫자의 결과를 합산하는 시퀀스입니다.
so.. 1 + 1 = 2
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21
Fibbonacci가 무엇인지 알게 되면 암호를 해독할 수 있습니다.
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
첫 번째 if statement는 루프가 발생할 수 있는 베이스 케이스를 체크합니다.그 외의 경우는, 아래의 스테이트먼트가 같은 동작을 하고 있습니다만, 이렇게 고쳐 쓸 수 있습니다.
public int fibonacci(int n) {
if(n < 2)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
이제 기본 사례가 확립되었으므로 콜 스택을 이해할 필요가 있습니다.「fibonacci」에의 첫 번째 콜은, 스택(콜의 시퀀스)으로 해결되는 마지막 콜이 됩니다.이 콜은, 콜의 발신기지와 반대의 순서로 해결됩니다.호출된 마지막 메서드가 먼저 해결되고 그 전에 호출된 마지막 메서드 등이 있습니다.
따라서 모든 콜은 그 결과로 '계산'되기 전에 먼저 이루어집니다.입력이 8일 경우 출력은 21이 될 것으로 예상됩니다(위 표 참조).
fibonacci(n - 1)는 베이스 케이스에 도달할 때까지 계속 호출되며 fibonacci(n - 2)는 베이스 케이스에 도달할 때까지 호출됩니다.스택이 역순으로 결과를 합산하기 시작하면 결과는 다음과 같습니다.
1 + 1 = 1 ---- last call of the stack (hits a base case).
2 + 1 = 3 ---- Next level of the stack (resolving backwards).
2 + 3 = 5 ---- Next level of the stack (continuing to resolve).
스택의 첫 번째 콜에 올바른 합계가 반환되고 그 결과 답변이 나올 때까지 버블링(뒤로 해결)이 계속됩니다.
그러나 이 알고리즘은 코드가 분할된 각 브랜치에 대해 동일한 결과를 계산하기 때문에 매우 비효율적입니다.보다 좋은 방법은 메모화(캐시)나 재귀(딥 콜스택)가 필요 없는 '바텀업' 방식입니다.
이렇게...
static int BottomUpFib(int current)
{
if (current < 2) return current;
int fib = 1;
int last = 1;
for (int i = 2; i < current; i++)
{
int temp = fib;
fib += last;
last = temp;
}
return fib;
}
여기서 제공하는 솔루션의 대부분은 O(2^n)의 복잡성으로 실행됩니다.재귀 트리에서 동일한 노드를 재계산하면 비효율적이며 CPU 사이클이 낭비됩니다.
메모화를 사용하여 O(n) 시간 내에 fibonacci 함수를 실행할 수 있습니다.
public static int fibonacci(int n) {
return fibonacci(n, new int[n + 1]);
}
public static int fibonacci(int i, int[] memo) {
if (i == 0 || i == 1) {
return i;
}
if (memo[i] == 0) {
memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
}
return memo[i];
}
Bottom-Up Dynamic Programming 경로를 따를 경우, 아래 코드는 fibonacci를 계산할 수 있을 만큼 단순합니다.
public static int fibonacci1(int n) {
if (n == 0) {
return n;
} else if (n == 1) {
return n;
}
final int[] memo = new int[n];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i < n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n - 1] + memo[n - 2];
}
이 답변이 다른 이유
다른 모든 답변은 다음과 같습니다.
- 반품 대신 인쇄
- 반복마다 2개의 재귀 호출을 실행
- 루프를 사용하여 질문을 무시합니다.
(게다가, 이들 중 어느 것도 실제로 효율적이지 않다. N항을th 직접 계산하기 위해 Binet의 공식을 사용한다.)
테일 재귀 섬유
여기에서는 이전 응답과 이전 응답을 모두 전달함으로써 이중 재귀 콜을 회피하는 재귀적 접근 방식을 보여 줍니다.
private static final int FIB_0 = 0;
private static final int FIB_1 = 1;
private int calcFibonacci(final int target) {
if (target == 0) { return FIB_0; }
if (target == 1) { return FIB_1; }
return calcFibonacci(target, 1, FIB_1, FIB_0);
}
private int calcFibonacci(final int target, final int previous, final int fibPrevious, final int fibPreviousMinusOne) {
final int current = previous + 1;
final int fibCurrent = fibPrevious + fibPreviousMinusOne;
// If you want, print here / memoize for future calls
if (target == current) { return fibCurrent; }
return calcFibonacci(target, current, fibCurrent, fibPrevious);
}
1 1 2 3 5 8의 출력을 표시하거나 얻는 기본 시퀀스이며, 현재 번호의 합계가 다음에 표시되는 시퀀스입니다.
Java Recursive Fibonacci 시퀀스 아래의 링크를 감시합니다.자습서
public static long getFibonacci(int number){
if(number<=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}
여기를 클릭 스푼 피딩에 대한 Java 재귀 피보나치 시퀀스 튜토리얼 보기
이것은 간단한 방법이라고 생각합니다.
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int number = input.nextInt();
long a = 0;
long b = 1;
for(int i = 1; i<number;i++){
long c = a +b;
a=b;
b=c;
System.out.println(c);
}
}
}
RanRag(승인 완료) 답변은 정상적으로 동작하지만 Anil 답변에서 설명한 바와 같이 외우지 않으면 솔루션이 최적화되지 않습니다.
아래 재귀적 접근법의 경우 메서드 호출:TestFibonacci최소값
public class TestFibonacci {
public static void main(String[] args) {
int n = 10;
if (n == 1) {
System.out.println(1);
} else if (n == 2) {
System.out.println(1);
System.out.println(1);
} else {
System.out.println(1);
System.out.println(1);
int currentNo = 3;
calFibRec(n, 1, 1, currentNo);
}
}
public static void calFibRec(int n, int secondLast, int last,
int currentNo) {
if (currentNo <= n) {
int sum = secondLast + last;
System.out.println(sum);
calFibRec(n, last, sum, ++currentNo);
}
}
}
public class febo
{
public static void main(String...a)
{
int x[]=new int[15];
x[0]=0;
x[1]=1;
for(int i=2;i<x.length;i++)
{
x[i]=x[i-1]+x[i-2];
}
for(int i=0;i<x.length;i++)
{
System.out.println(x[i]);
}
}
}
이론적으로 이 재귀 구현이 멀티스레드 환경에서 올바르게 동작할 수 있도록 내부 ConcurrentHashMap을 사용함으로써 BigInteger와 재귀 모두를 사용하는 fib 함수를 구현했습니다.처음 100개의 파이버 번호를 계산하는 데 약 53ms가 소요됩니다.
private final Map<BigInteger,BigInteger> cacheBig
= new ConcurrentHashMap<>();
public BigInteger fibRecursiveBigCache(BigInteger n) {
BigInteger a = cacheBig.computeIfAbsent(n, this::fibBigCache);
return a;
}
public BigInteger fibBigCache(BigInteger n) {
if ( n.compareTo(BigInteger.ONE ) <= 0 ){
return n;
} else if (cacheBig.containsKey(n)){
return cacheBig.get(n);
} else {
return
fibBigCache(n.subtract(BigInteger.ONE))
.add(fibBigCache(n.subtract(TWO)));
}
}
테스트 코드는 다음과 같습니다.
@Test
public void testFibRecursiveBigIntegerCache() {
long start = System.currentTimeMillis();
FibonacciSeries fib = new FibonacciSeries();
IntStream.rangeClosed(0,100).forEach(p -&R {
BigInteger n = BigInteger.valueOf(p);
n = fib.fibRecursiveBigCache(n);
System.out.println(String.format("fib of %d is %d", p,n));
});
long end = System.currentTimeMillis();
System.out.println("elapsed:" +
(end - start) + "," +
((end - start)/1000));
}
테스트 출력은 다음과 같습니다......93의 fib는 12200160415121876738입니다.94의 fib는 19740274219868223167입니다.95의 fib는 31940434634990099905입니다.96의 fib는 51680708854858323072 입니다.97의 fib는 83621143489848422977입니다.fib of 98 은 135301852344706746049 입니다.99 의 fib 는 218922995834555169026 입니다.fib of 100 은 3542248179261915075 입니다.경과: 58,0
다음은 한 줄의 febonacci 재귀입니다.
public long fib( long n ) {
return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
더 큰 숫자를 계산하려면 BigInteger를 사용해야 합니다.
반복적인 예.
import java.math.BigInteger;
class Fibonacci{
public static void main(String args[]){
int n=10000;
BigInteger[] vec = new BigInteger[n];
vec[0]=BigInteger.ZERO;
vec[1]=BigInteger.ONE;
// calculating
for(int i = 2 ; i<n ; i++){
vec[i]=vec[i-1].add(vec[i-2]);
}
// printing
for(int i = vec.length-1 ; i>=0 ; i--){
System.out.println(vec[i]);
System.out.println("");
}
}
}
자세한 것은, http://en.wikipedia.org/wiki/Fibonacci_number 를 참조해 주세요.
public class Fibonacci {
public static long fib(int n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
for (int i = 1; i <= N; i++)
System.out.println(i + ": " + fib(i));
}
}
루프 및 기타 루프를 사용하지 않아도 되는 심플함을 최대한 실현합니다.
public class FibonacciSeries {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
for (int i = 0; i <= N; i++) {
int result = fibonacciSeries(i);
System.out.println(result);
}
scanner.close();
}
private static int fibonacciSeries(int n) {
if (n < 0) {
return 1;
} else if (n > 0) {
return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
}
return 0;
}
}
사용하다while:
public int fib(int index) {
int tmp = 0, step1 = 0, step2 = 1, fibNumber = 0;
while (tmp < index - 1) {
fibNumber = step1 + step2;
step1 = step2;
step2 = fibNumber;
tmp += 1;
};
return fibNumber;
}
이 솔루션의 장점은 코드를 쉽게 읽고 이해할 수 있다는 것입니다.
Fibbonacci 시퀀스는 숫자의 결과를 합산한 수열입니다.앞의 결과에 더하면 1부터 시작해야 합니다.알고리즘에 근거해 솔루션을 찾으려고 하고 있었기 때문에, 재귀 코드를 작성하고, 이전 번호를 유지하고 있는 것을 눈치채고, 위치를 변경했습니다.1부터 15까지 피보나치 수열을 찾고 있어요
public static void main(String args[]) {
numbers(1,1,15);
}
public static int numbers(int a, int temp, int target)
{
if(target <= a)
{
return a;
}
System.out.print(a + " ");
a = temp + a;
return numbers(temp,a,target);
}
이거 드셔보세요
private static int fibonacci(int n){
if(n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
나는 3진 연산자가 있는 단순한 라이너를 찾을 수 없었다.예를 들어 다음과 같습니다.
public int fibonacci(int n) {
return (n < 2) ? n : fibonacci(n - 2) + fibonacci(n - 1);
}
public static long fib(int n) {
long population = 0;
if ((n == 0) || (n == 1)) // base cases
{
return n;
} else // recursion step
{
population+=fib(n - 1) + fib(n - 2);
}
return population;
}
심플 피보나치
public static void main(String[]args){
int i = 0;
int u = 1;
while(i<100){
System.out.println(i);
i = u+i;
System.out.println(u);
u = u+i;
}
}
}
언급URL : https://stackoverflow.com/questions/8965006/java-recursive-fibonacci-sequence
'source' 카테고리의 다른 글
| 모바일 장치에서 네비게이션 바를 mini로 전환 (0) | 2022.08.19 |
|---|---|
| C를 위한 스마트 포인터/안전한 메모리 관리 (0) | 2022.08.19 |
| Vue.js 및 jQuery? (0) | 2022.08.19 |
| Signal R을 Vue.js 및 Vuex와 통합 (0) | 2022.08.19 |
| Vue 앱이 VM을 사용할 때 이벤트 청취자에게 추가 매개 변수를 전달할 수 있는 방법은 무엇입니까?$once()? (0) | 2022.08.18 |