Search Results for 'fibonacci'

1 POSTS

  1. 2008/05/02 [UVA] 10183 How many Fibs?

[UVA] 10183 How many Fibs?

Posted 2008/05/02 22:39

10의 100승보다 작은 어떤 수 두 수 a와 b가 주어진다. Fibonacci숫자(1,2,3,5,8..) 중에서 a보다 크고 b보다 작은 숫자가 몇개인지 찾는문제이다.

Fibonacci 수열은 리커젼으로 해결 할 경우 O(2의N승)의 시간복잡도를 보이므로 매우 오랜시간이 걸린다.

그러므로 순차적으로 문제를 해결해야 하며 10의 100승까지의 숫자를 처리하기 위해 Java의 BigInteger class를 사용하였다.

과거에 BigInteger로 코딩을 몇번 해본적이 있는데 덕분에 금방 문제를 해결할 수 있었다.


//10183 How many Fibs?

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

public class Main {
        Scanner in = new Scanner(System.in);

        public Main() {
                while(true) {
                        BigInteger startNum = new BigInteger(in.next());
                        BigInteger endNum = new BigInteger(in.next());
                       
                        if(startNum.compareTo(BigInteger.valueOf(0)) == 0 &&
                           endNum.compareTo(BigInteger.valueOf(0)) == 0)
                                break;
                       
                        BigInteger bigFiboNum1 = new BigInteger("1");
                        BigInteger bigFiboNum2 = new BigInteger("2");
                        BigInteger bigFiboNum3 = new BigInteger("0");
                        BigInteger bigTemp = new BigInteger("0");

                        int fiboCount = 0;
                        for(int i=1 ; ; i++) {
                                if(i == 1)
                                        bigFiboNum3 = BigInteger.valueOf(1);
                                else if(i == 2)
                                        bigFiboNum3 = BigInteger.valueOf(2);
                                else {
                                        bigTemp = BigInteger.valueOf(0);
                                        bigTemp = bigTemp.add(bigFiboNum3);
                                       
                                        bigFiboNum3 = bigFiboNum1.add(bigFiboNum2);
                                       
                                        bigFiboNum1 = BigInteger.valueOf(0);
                                        bigFiboNum1 = bigFiboNum1.add(bigTemp);
                                       
                                        bigFiboNum2 = BigInteger.valueOf(0);
                                        bigFiboNum2 = bigFiboNum2.add(bigFiboNum3);
                                }
                               
                                if(bigFiboNum3.compareTo(startNum) >= 0) {
                                        if(bigFiboNum3.compareTo(endNum) <= 0) {
                                                fiboCount++;
                                        }
                                        else {
                                                System.out.println(fiboCount);
                                                break;
                                        }
                                }
                        }
                }
        }

        public static void main(String[] args) {
                new Main();
        }
}


 

이올린에 북마크하기

'C.S.E > Algorithm' 카테고리의 다른 글

[UVA] 10198 Counting  (0) 2008/05/06
[UVA] 10099 The Tourist Guide  (0) 2008/05/04
[UVA] 10183 How many Fibs?  (0) 2008/05/02
[UVA] 10069 Distinct Subsequences  (0) 2008/05/01
자바 알고리즘 경진대회(JAC) 기대와 아쉬운점  (6) 2008/04/18
[UVA] 10131 Is Bigger Smarter?  (2) 2008/04/08
« PREV : 1 : NEXT »