[UVA] 10183 How many Fibs?
Posted 2008/05/02 22:3910의 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();
}
}
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 |
- Filed under : C.S.E/Algorithm
- Tag : Algorithm, BigInteger, fibonacci, uva
- Comment Trackback
