HowManyFibs？/황재선

2006.1.4

접근 방법

반복적인 계산을 줄이기 위해서, bottom-up 방식으로 수열을 처음부터 계산하였다. 계산된 이전 값을 사용하여 다음 수열을 빠르게 얻을 수 있었다. Dynamic Programming을 처음으로 해보았다 :)

소스 코드

import java.math.BigInteger;
import java.util.Scanner;

public class Fibonacci {
	
	public String readLine() {
		return new Scanner(System.in).useDelimiter("\n").next().trim();
    }
	
	public int howManyFib(BigInteger start, BigInteger end) {
		int howMany = 0;
		
		BigInteger zero = new BigInteger("0");
		BigInteger one = new BigInteger("1");
		BigInteger two = new BigInteger("2");
		
		if ((start.equals(zero) && end.equals(one)) ||
				(start.equals(one) && end.equals(one)) || 
				(start.equals(two) && end.equals(two))) { 
            return 1; 
        } 
        else if (start.equals(one) && end.equals(two)) { 
            return 2; 
        } 
        else if (start.equals(one)) {
        	howMany = 2; 
        } 
        else if (start.equals(two)) { 
        	howMany = 1; 
        }
		
		BigInteger[] fibRoom = new BigInteger[4];
		
		fibRoom[1] = one;
		fibRoom[2] = two;

		while(true) {
			fibRoom[3] = fibRoom[1].add(fibRoom[2]);

			if (start.compareTo(fibRoom[3]) <= 0 && fibRoom[3].compareTo(end) <= 0) {
				howMany++;
			}

			if (fibRoom[3].compareTo(end) > 0) {
				break;
			}
			
			fibRoom[1] = fibRoom[2];
			fibRoom[2] = fibRoom[3];	
		}
		return howMany;
	}
	
	public void printNumOfFibs(int numOfFibs) {
		System.out.println(numOfFibs);
	}

	public static void main(String[] args) {
		Fibonacci fib = new Fibonacci();
		
		while(true) {
			String line = fib.readLine();			
			if (line.equals("0 0")) {
				break;
			}
			
			BigInteger start = new BigInteger(line.split(" ")[0]);
			BigInteger end = new BigInteger(line.split(" ")[1]);
			
			int numOfFibs = fib.howManyFib(start, end);
			fib.printNumOfFibs(numOfFibs);
		}
	}

}

Test Code

import java.math.BigInteger;

import junit.framework.TestCase;

public class TestFibonacci extends TestCase {
	public void testSample() {
		Fibonacci fib = new Fibonacci();
		
		assertEquals(5, fib.howManyFib(new BigInteger("10"), new BigInteger("100")));
		assertEquals(4, fib.howManyFib(new BigInteger("1234567890"), 
				new BigInteger("9876543210")));
		
		assertEquals(1, fib.howManyFib(new BigInteger("1"), new BigInteger("1")));
		assertEquals(1, fib.howManyFib(new BigInteger("0"), new BigInteger("1")));
	}
}

---

HowManyFibs？