자바 재귀 피보나치 시퀀스
이 간단한 코드를 설명하십시오 :
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 인 경우 fibonacci (4) + fibonacci (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피보나치 수열이을 반환 한다는 것을 알 수 있습니다 5.
재귀 자습서는 여기를 참조하십시오 .
코드에는 두 가지 문제가 있습니다.
- 결과는 정수 채우기 마이너스 비트 이후 첫 48 피보나치 수만 처리 할 수있는 int에 저장되며 결과는 잘못됩니다.
- 그러나 피보나치 (50)를 실행할 수 없습니다.
코드
fibonacci(n - 1) + fibonacci(n - 2)
가 매우 잘못되었습니다.
문제는 피보나치가 50 번이 아니라 훨씬 더 많다는 것입니다.
처음에는 피보나치 (49) + 피보나치 (48),
다음 피보나치 (48) + 피보나치 (47) 및 피보나치 (47) + 피보나치 (46)
라고합니다. 피보나치 (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 인 경우 다음이 발생합니다.
피보나치 (4) + 피보나치 (3)
이것은 다음과 같이 분류됩니다.
(피보나치 (3) + 피보나치 (2)) + (피보나치 (2) + 피보나치 (1))
이것은 다음과 같이 분류됩니다.
(((피보나치 (2) + 피보나치 (1)) + ((피보나치 (1) + 피보나치 (0))) + ((((피보나치 (1) + 피보나치 (0)) + 1))
이것은 다음과 같이 분류됩니다.
((((피보나치 (1) + 피보나치 (0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))
이것은 다음과 같이 분류됩니다.
((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))
결과 : 5
피보나치 수열이 1 1 2 3 5 8 ... 이면 5 번째 요소는 5입니다. 동일한 방법론을 사용하여 다른 반복을 알아낼 수 있습니다.
재귀는 때때로 파악하기 어려울 수 있습니다. 적은 수의 종이로 그것을 평가하십시오.
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가 실제로 이것을 어떻게 평가하는지 잘 모르겠지만 결과는 같습니다.
다음과 같이 기능을 단순화 할 수도 있습니다.
public int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
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 chapter 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;
}
피보나치 재귀 솔루션의 경우 작은 피보나치 수의 출력을 저장하는 동시에 큰 수의 값을 검색하는 것이 중요합니다. 이것을 "Memoizing"이라고합니다.
여기서 사용하십시오 코드 memoizing 큰 피보나치 수를 검색하는 동안, 작은 피보나치 값. 이 코드는 효율적이며 동일한 기능을 여러 번 요청하지 않습니다.
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;
}
}
}
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]을 산출합니다.
에 피보나치 시퀀스의 처음 두 항목이 0 또는 1이고, 기타 각 항목은 이전의 두 항목의 합이다. 즉 :
0112 3 5 8 ...
5 번째 항목은 4 번째와 3 번째 항목의 합입니다.
피보나치 수열은 1로 시작하는 이전 결과에 추가 될 때 수의 결과를 합한 것입니다.
so.. 1 + 1 = 2
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21
피보나치가 무엇인지 이해하면 코드를 분석하기 시작할 수 있습니다.
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 문은 루프가 발생할 수있는 기본 사례를 확인합니다. 아래의 else if 문은 동일하지만 다시 작성 될 수 있습니다 ...
public int fibonacci(int n) {
if(n < 2)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
이제 기본 사례가 확립되었으므로 호출 스택을 이해해야합니다. "fibonacci"에 대한 첫 번째 호출은 호출 된 순서와 반대 순서로 해결 될 때 스택 (통화 순서)에서 마지막으로 해결됩니다. 마지막으로 호출 된 메소드가 먼저 해결되고 마지막으로 호출되기 전에 마지막으로 호출됩니다.
따라서 모든 결과는 해당 결과로 "계산"되기 전에 먼저 이루어집니다. 입력이 8이면 21이 출력됩니다 (위 표 참조).
피보나치 (n-1)는 기본 사례에 도달 할 때까지 계속 호출되고, 피보나치 (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) 시간에 실행되도록 메모를 사용할 수 있습니다
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];
}
상향식 동적 프로그래밍 경로를 따르면 아래 코드는 피보나치 계산에 충분히 간단합니다.
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 회 재귀 호출
- 루프를 사용하여 질문을 무시합니다
(제외 : 이것들 중 어느 것도 실제로 효율적이지 않습니다; Binet의 공식 을 사용 하여 n 번째 항 을 직접 계산하십시오 )
꼬리 재귀 섬유
다음은 이전 답변과 이전 답변을 모두 전달하여 이중 재귀 호출을 피하는 재귀 적 접근 방식입니다.
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 sequence Tutorial 아래 링크를보십시오.
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);
}
}
}
이론적으로이 재귀 구현이 다중 스레드 환경에서 올바르게 작동 할 수 있도록하는 내부 ConcurrentHashMap을 사용하여 BigInteger와 Recursion을 모두 사용하는 fib 함수를 구현했습니다. 처음 100 개의 fib 수를 계산하는 데 약 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입니다.
fib 95는 31940434634990099905입니다.
96의 fib는 51680708854858323072입니다.
97의 fib는 83621143489848422977입니다.
98의 fib는 135301852344706746049입니다.
99의 fib는 218922995834555169026입니다.
100의 fib는 354224848179261915075입니다.
경과 : 58,0
다음은 한 줄의 페 보나 치 재귀입니다.
public long fib( long n ) {
return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
이 시도
private static int fibonacci(int n){
if(n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
더 많은 정보를 확인하려면 자바 의이 피보나치 시리즈 출력-Mediocre Code
보완하기 위해 더 큰 숫자를 계산하려면 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));
}
}
while 루프 및 기타 루프를 사용할 필요없이 간단하게 작성하십시오.
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]);
}
}
}
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;
}
이 솔루션의 장점은 코드를 읽고 이해하기 쉽기 때문에 코드를 쉽게 읽고 이해할 수 있다는 것입니다.
피보나치 시퀀스는 숫자의 결과를 합한 다음 이전 결과에 추가 한 것입니다. 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);
}
다음은 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.
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;
}
피보나치 시리즈는 다이나믹 프로그래밍의 힘을 보여주는 간단한 코드입니다. 학교 시절부터 배운 것은 반복 또는 최대 재귀 코드를 통해 실행하는 것입니다. 재귀 코드는 20 정도까지 잘 작동합니다. 숫자보다 큰 숫자를 제공하면 계산하는 데 많은 시간이 걸립니다. 동적 프로그래밍에서는 다음과 같이 코딩 할 수 있으며 답을 계산하는 데 몇 초가 걸립니다.
static double fib(int n) {
if (n < 2)
return n;
if (fib[n] != 0)
return fib[n];
fib[n] = fib(n - 1) + fib(n - 2);
return fib[n];
}
배열에 값을 저장하고 배열이 답을 제공 할 수없는 경우에만 새로운 계산을 진행합니다.
간단한 피보나치
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
'development' 카테고리의 다른 글
| pandoc을 사용하여 Markdown에서 PDF로 변환 할 때 여백 크기 설정 (0) | 2020.06.14 |
|---|---|
| 유래 (0) | 2020.06.14 |
| 다른 모듈이 필요한 Node.js 모듈을 단위 테스트하는 방법과 전역 요구 기능을 조롱하는 방법은 무엇입니까? (0) | 2020.06.14 |
| Java 배열은 처음에 요소를 추가하는 방법 (0) | 2020.06.14 |
| “장식 자”란 무엇이며 어떻게 사용됩니까? (0) | 2020.06.14 |