피보나치 스택 프로그램 (Java). 무한 루프

Question

Java에서 재귀를 사용하지 않는 피보나치 숫자 계산기를 만들려고합니다. 그러나 프로그램을 실행하면 무한 루프가 생성됩니다. 시도하고 디버깅하는 많은 인쇄 문을 넣었지만 솔직히 스택이 어떻게 작동하는지 잘 모르겠습니다. 다음은 두 클래스입니다.

package fibNumbers.fibStack; 

import java.math.BigInteger; 
import java.util.HashMap; 
import java.util.Map; 
import java.util.Stack; 

/** 
* A utility class containing methods to compute Fibonacci numbers. 
* 
* @author EECS2030 Fall 2016-17 
* 
*/ 
public class Fibonacci { 

private Fibonacci() { 
    // empty by design 
} 

private static Map<Integer, BigInteger> cache = new HashMap<Integer, BigInteger>(); 

/** 
* Memoized recursive implementation for computing Fibonacci numbers. 
* This method will fail for modest values of n because of limits 
* on the size of the call stack memory. 
* 
* @param n which Fibonacci number to compute 
* @return the value of F(n) 
*/ 
public static BigInteger fib(int n) { 
BigInteger sum = null; 
if (n == 0) { 
    sum = BigInteger.ZERO; 
} 
else if (n == 1) { 
    sum = BigInteger.ONE; 
} 
else if (cache.containsKey(n)) { 
    sum = cache.get(n); 
} 
else { 
    BigInteger fMinus1 = Fibonacci.fib(n - 1); 
    BigInteger fMinus2 = Fibonacci.fib(n - 2); 
    sum = fMinus1.add(fMinus2); 
    cache.put(n, sum); 
} 
return sum; 
} 


/** 
* Memoized iterative implementation for computing Fibonacci numbers 
* using an explicit call stack and simulated stack frames. 
* 
* @param n which Fibonacci number to compute 
* @return the value of F(n) 
*/ 
public static BigInteger fib2(int n) { 
Stack<FibonacciStackFrame> callStack = new Stack<FibonacciStackFrame>(); 

FibonacciStackFrame f = new FibonacciStackFrame(n, null); 
callStack.push(f); 
while (!callStack.isEmpty()) { 
    f = callStack.peek(); 
    f.execute(callStack); 
    System.out.println("Finished execution, starting loop again."); 
} 
return f.getReturnValue(); 
} 

public static void main(String[] args) { 
    System.out.println("F(10000) = " + Fibonacci.fib2(10000)); 
} 

} 

내 스택 프레임 클래스. 그렇지 않으면 결코 멈추지 않을 것이기 때문에 나는 반복을 30 번 실행 한 후에 예외를 두었다.

package fibNumbers.fibStack; 

import java.math.BigInteger; 
import java.util.HashMap; 
import java.util.Map; 
import java.util.Stack; 

/** 
* A stack frame for computing Fibonacci numbers. 
* 
* @author EECS2030 Fall 2016-17 
* 
*/ 
public class FibonacciStackFrame { 

private static Map<Integer, BigInteger> cache = new HashMap<Integer, BigInteger>(); 
private int n; 
private FibonacciStackFrame caller; 
private boolean fMinus1Computed; 
private boolean fMinus2Computed; 
private BigInteger fMinus1; 
private BigInteger fMinus2; 
private BigInteger sum; 
public static int timesExecuted = 0; 

/** 
* Creates a stack frame to compute F(n). <code>caller</code> is a reference 
* to the <code>FibonacciStackFrame</code> that created this stack frame. If 
* this stack frame is not being created by another 
* <code>FibonacciStackFrame</code> instance, then <code>caller</code> is 
* expected to be equal to <code>null</code>. 
* 
* 
* @param n 
*   the Fibonccci number to compute 
* @param caller 
*   the <code>FibonacciStackFrame</code> that created this stack 
*   frame 
* @throws IllegalArgumentException 
*    if n is less than 0 
*/ 
public FibonacciStackFrame(int n, FibonacciStackFrame caller) { 
    if (n < 0) { 
     throw new IllegalArgumentException("n must != ZERO"); 
    } 

    this.n = n; 
    this.caller = caller; 
    this.fMinus1 = BigInteger.ZERO; 
    this.fMinus1Computed = false; 
    this.fMinus2 = BigInteger.ZERO; 
    this.fMinus2Computed = false; 
    this.sum = BigInteger.ZERO; 
} 

/** 
* Receive a return value from another <code>FibonacciStackFrame</code> 
* instance. 
* 
* <p> 
* This method is used to simulate Lines 16 and 17 of the fib(int) method 
* described in the lab web page. This method needs to figure out if it is 
* simulating Line 16 or Line 17; continue reading for details. 
* </p> 
* 
* <p> 
* If this.fMinus1Computed is false, then this method should set 
* this.fMinus1 to <code>retVal</code> (simulating Line 16), and set 
* this.fMinus1Computed to true. 
* </p> 
* 
* <p> 
* If this.fMinus1Computed is true, and this.fMinus2Computed is false, then 
* this method should set this.fMinus2 to <code>retVal</code> (simulating 
* Line 17), and set this.fMinus2Computed to true.. 
* </p> 
* 
* <p> 
* If both this.fMinus1Computed and this.fMinus2Computed are true then you 
* have done something wrong elsewhere in the class, and you should throw an 
* IllegalStateException. 
* </p> 
* 
* @param retVal 
*   the value of F(n - 1) or F(n - 2) returned from another 
*   <code>FibonacciStackFrame</code> instance 
* @throws IllegalStateException 
*    if this stack frame has already received values for both F(n 
*    - 1) and F(n - 2) 
*/ 
public void receiveReturnValue(BigInteger retVal) { 
    System.out.println("...Now at top of this.recieveReturnValue"); 
    if (this.fMinus1Computed == false) { 
     System.out.println("...Computing fMinus1, setting to true"); 
     this.fMinus1 = retVal; 
     this.fMinus1Computed = true; 
    } else if ((this.fMinus1Computed == true) && (this.fMinus2Computed == false)) { 
     this.fMinus2 = retVal; 
     this.fMinus2Computed = true; 
    } else if ((this.fMinus1Computed == true) && (this.fMinus2Computed == true)) { 
     throw new IllegalStateException("BOTH both F(n - 1) and F(n - 2), stack frames have recieved values"); 
    } 
} 

/** 
* Returns the value of F(this.n) back to the caller. This simulates Line 21 
* of the fib(int) method described in the lab web page. 
* 
* <p> 
* If the caller is equal to null, then you should simply pop the call 
* stack. Otherwise, you should have the caller invoke 
* <code>receiveReturnValue</code> to accept the value of F(n), which can be 
* obtained from the method <code>getReturnValue</code>, and then pop the 
* call stack. 
* 
* @param callStack 
*   the call stack 
*/ 
public void returnValueToCaller(Stack<FibonacciStackFrame> callStack) { 
    if (this.caller == null) { 
     System.out.println("current caller is null"); 
     this.caller = callStack.pop(); 
    } else { 
     System.out.println("Caller != null"); 
     System.out.println("getReturnValue yields: "+this.getReturnValue()); 
     this.receiveReturnValue(this.getReturnValue()); 
     this.caller = callStack.pop(); 
     System.out.println("The call stack has been popped"); 
    } 

} 

/** 
* Start or resume execution of this stack frame. This method is expected to 
* be invoked when this stack frame is on top of the call stack. When this 
* method is invoked, this stack frame can be in one of six possible states: 
* 
* <ol> 
* <li>this stack frame is computing F(0), in which case the value 0 can be 
* returned to the caller 
* <li>this stack frame is computing F(1), in which case the value 1 can be 
* returned to the caller 
* <li>this stack frame is computing F(n) and F(n) is in the cache, in which 
* case the value F(n) can be retrieved from the cache and returned to the 
* caller 
* <li>this stack frame is computing F(n - 1), in which case this stack 
* frame should push a new stack frame onto the call stack to compute F(n - 
* 1) passing <code>this</code> as the caller of the new stack frame, and 
* then return from this method 
* <li>this stack frame is computing F(n - 2), in which case this stack 
* frame should push a new stack frame onto the call stack to compute F(n - 
* 2) passing <code>this</code> as the caller of the new stack frame, and 
* then return from this method 
* <li>this stack frame is computing the sum F(n - 1) + F(n - 2), in which 
* case this stack frame should compute the sum, put the sum in the cache, 
* and return the value of the sum to the caller 
* </ol> 
* 
* <p> 
* You should write an if-else-if statement that covers the 6 cases 
* described above. 
* </p> 
* 
* @param callStack 
*   the call stack that this frame is on top of 
*/ 
public void execute(Stack<FibonacciStackFrame> callStack) { 
    System.out.println(""); 
    System.out.println("New Frame *** *** *** ***"); 

    timesExecuted ++; 
    if(timesExecuted>20){ 
     throw new IllegalArgumentException("***Stack overflow, infinite loop occuring***"); 
    } 
    System.out.println("currentFrame.n ="+this.getN()); 
    if (this.getN() == 0) { 
     timesExecuted++; 
     System.out.println("Execution #" + timesExecuted); 
     setSum(BigInteger.ZERO); 
     this.returnValueToCaller(callStack); 
    } else if (this.getN() == 1) { 
     System.out.println("running through case n==1"); 
     setSum(BigInteger.ONE); 
     System.out.println(this.sum); 
     this.returnValueToCaller(callStack); 
    } else if (cache.containsKey(this.getN())) { 
     setSum(cache.get(n)); 
     this.returnValueToCaller(callStack); 
    } else if (!getfMinus1Computed()) { 
     System.out.println("***Computing fMinus1"); 
     System.out.println("n at this point: "+this.getN()); 
     callStack.push(new FibonacciStackFrame(this.getN() - 1, this)); 
     return; 
    } else if (!getfMinus2Computed()) { 
     System.out.println("*^*Computing fMinus2"); 
     callStack.push(new FibonacciStackFrame(this.getN() - 2,this)); 
     return; 
    } else { 
     this.setSum(fMinus1); 
     this.sum.add(fMinus2); 
     cache.put(this.getN(), this.getReturnValue()); 
     System.out.println(cache.get(this.getN())+"End case"); 
     this.returnValueToCaller(callStack); 

    } 
} 

// EVERYTHING BELOW THIS LINE HAS ALREADY BEEN IMPLEMENTED FOR YOU 

/** 
* Get the return value (F(n)) from this stack frame. The return value is 
* just this.sum (which is equal to F(n-1) + F(n-2) when this frame has 
* finished all of its work). 
* 
* <p> 
* If you call this method before the frame has finished all of its work 
* then you will get the wrong value for the sum. 
* 
* @return the value of F(n) 
*/ 
public BigInteger getReturnValue() { 
    // ALREADY COMPLETED FOR YOU 
    return this.sum; 
} 

/** 
* Get the cache of already computed Fibonacci numbers. This method is here 
* for debugging and testing purposes. 
* 
* @return the cache of already computed Fibonacci numbers 
*/ 
public static Map<Integer, BigInteger> getCache() { 
    return FibonacciStackFrame.cache; 
} 

/** 
* Get the value of n. This method is here for debugging and testing 
* purposes. 
* 
* @return the value of n 
*/ 
public int getN() { 
    return this.n; 
} 

/** 
* Get the creator of this call stack. This method is here for debugging and 
* testing purposes. 
* 
* @return the creator of this call stack 
*/ 
public FibonacciStackFrame getCaller() { 
    return this.caller; 
} 

/** 
* Get the current value of fMinus1. This method is here for debugging and 
* testing purposes. 
* 
* @return the current value of fMinus1 
*/ 
public BigInteger getfMinus1() { 
    return this.fMinus1; 
} 

/** 
* Get the current value of fMinus2. This method is here for debugging and 
* testing purposes. 
* 
* @return the current value of fMinus2 
*/ 
public BigInteger getfMinus2() { 
    return this.fMinus2; 
} 

/** 
* Get the current value of fMinus1Computed. This method is here for 
* debugging and testing purposes. 
* 
* @return the current value of fMinus1Computed 
*/ 
public boolean getfMinus1Computed() { 
    return this.fMinus1Computed; 
} 

/** 
* Get the current value of fMinus2Computed. This method is here for 
* debugging and testing purposes. 
* 
* @return the current value of fMinus2Computed 
*/ 
public boolean getfMinus2Computed() { 
    return this.fMinus2Computed; 
} 

/** 
* Set the value of this.sum. This method is here for debugging and testing 
* purposes. 
* 
* @param sum 
*   the new value for this.sum 
*/ 
public void setSum(BigInteger sum) { 
    this.sum = sum; 
} 

} 내 테스트를 실행하면

, 내가 상관없이 내가 fib2 (int)를 넣어 어떤 수를 발견하지, 그것은 1과 2 사이의 n 개의 교류의 값의 루프에 박히면서 것 끝내지 않고 계속하십시오. 나는 print 명령문을 많이 썼다. 그래서 내가하는 일을 추적 할 수 있었지만 중요한 문제는 스택이 캐시와의 접합점에서 어떻게 작동 하는지를 정확히 이해하지 못하고 최종 값을 반환한다는 것이다. 나는 또한 교수님이 준 프레임에서이 수업들을 만들고 있다고 언급해야합니다.

Answer 1

나는이 라인이 문제 같아요

f = callStack.peek() 

들여다 그냥 값을 검색하지만, 스택에서 제거하지 않기 때문에 스택 empty.I는이 작업을 수행하려고 생각 얻을하지 않습니다 : 난 당신이 전화에 작은 실수를 믿는 문서를 바탕으로 자세한 내용

Answer 2

에 대한

f = callStack.pop() 

확인 the documentation.

/** 
* Returns the value of F(this.n) back to the caller. This simulates Line 21 
* of the fib(int) method described in the lab web page. 
* 
* <p> 
* If the caller is equal to null, then you should simply pop the call 
* stack. Otherwise, you should have the caller invoke 
* <code>receiveReturnValue</code> to accept the value of F(n), which can be 
* obtained from the method <code>getReturnValue</code>, and then pop the 
* call stack. 
* 
* @param callStack 
*   the call stack 
*/ 

그렇지 않으면, 당신은

... 호출 방법 getReturnValue에서 얻을 수 있습니다 F (N)의 값을 받아 receiveReturnValue를 호출을해야 그 달성하기 위해 당신이 할 :

는

this.receiveReturnValue(this.getReturnValue());

하지만 그 방법에 대한 설명서는 말한다 : 0

는 다른 FibonacciStackFrame 인스턴스에서 반환 값을받을 수 있습니다. (중점 광산)

당신은 그것을 this 프레임이라고 부릅니다. 나는 당신이 어떤 발신자에게 그 값을 실제로 돌려 보내는지를 보지 못한다. 나는 그것이 있어야 할 생각 : 당신이 스택을 사용하여 요구 사항

caller.receiveReturnValue(this.getReturnValue());