문제 41, 피보나치 수의 개수, How many Fibs?, PC/UVa ID : 110601/10183, 인기도 : B, 성공률 : 보통, 레벨 : 1

문제 41, 피보나치 수의 개수, How many Fibs?, PC/UVa ID : 110601/10183, 인기도 : B, 성공률 : 보통, 레벨 : 1

이 포스트를 만든 목적

• 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
  

이 포스트의 준비물

• Mozila Firefox 6.0
  
• eclipse 3.6.1 + vrapper
  
• java
  

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 41, 피보나치 수의 개수, How many Fibs?, p.172)
  

참조 링크

• http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1124 : 문제 원문
  
• http://www.algorithmist.com/index.php/UVa_10183 : 문제 원문
  
  
• http://belbesy.wordpress.com/2011/05/31/uva-10183-how-many-fibs/ : 문제 풀이
  
• http://cherrykyun.tistory.com/219 : 문제 풀이
  

간략한 이야기/프로그램의 입출력

피보나치 수는 다음 처럼 정의 된다.

f₁ := 1
f₂ := 2
f_n := f_n-1 + f_n-2     (n>=3)

두개의 수 a 와 b 가 주어졌을 때, 이 두 수 사이에 얼마나 많은 피보나치 수가 있는지 계산해라.

입력

• 여러개의 테스트 케이스가 입력될 수 있다.
  
• 각 테스트 케이스는 두개의 수 a, b를 입력 받는다.
  
• a 와 b가 0일 경우, 프로그램은 종료된다.
  
  
• a와 b의 범위는 a<=b<=10¹⁰⁰ 이며, a, b는 양의 정수이다.

출력

• 각 테스트 케이스는 한 라인에 a<=f_i<=b. 의 피보노치 수의 개수를 출력 한다.
  

맛보기 코드

package Problem041HowManyFibs; import java.util.*; import java.math.BigInteger; public class HowManyFibs { public static void main(String args[]) { Scanner sc = new Scanner(System.in); for (;;) { BigInteger a = sc.nextBigInteger(); BigInteger b = sc.nextBigInteger(); if (BigInteger.ZERO.equals(a) && BigInteger.ZERO.equals(b)) break; int answer = HowManyFibsReal.calculate(a, b); System.out.println(answer); } } } class HowManyFibsReal { public static int calculate(BigInteger a, BigInteger b) { BigInteger n[] = new BigInteger[3]; n[0] = BigInteger.ZERO; n[1] = BigInteger.ONE; int number = 0; for (;;) { n[2] = n[0].add(n[1]); n[0] = n[1]; n[1] = n[2]; if (0 < a.compareTo(n[2])) continue; if (0 > b.compareTo(n[2])) return number; else ++number; } } }
package Problem041HowManyFibs; import static org.junit.Assert.*; import java.math.BigInteger; import org.junit.Test; public class HowManyFibsTest { @Test public void testCalculateFibsNumber1() { assertTrue(5 == HowManyFibsReal.calculate( new BigInteger("10"), new BigInteger("100"))); } @Test public void testCalculateFibsNumber2() { assertTrue(4 == HowManyFibsReal.calculate( new BigInteger("1234567890"), new BigInteger("9876543210"))); } }

맛보기 사진

여담

• 최대 100 자리수까지 고려해야 하므로, C 에선 문자열로 처리해 주어야 한다.
  
• JAVA 에선 BigInteger 클래스를 이용하면, 100 자리수도 계산할 수 있다.
  
• 피보노치 수를 테이블 표로 만들고, 이 표의 범위로 개수를 찾는 방법으로 푼 것을 보았다.(재미있었다.)
  
• 어려운건 없었다.
  
  

:wq!