2006.1.9
¶
- 구 close form 겠;
- 기 . 값 기 구. 기 값 계 값 기 .
¶
~java
import java.util.Scanner;
public class DescribingSequence {
private final int MAX = 673366;
public int readNumber() {
return new Scanner(System.in).nextInt();
}
public int getSequence(int n) {
if (n == 1) {
return 1;
}
else if (n == 2 || n == 3) {
return 2;
}
int[] describing = new int[MAX + 1];
describing[3] = 2;
int input = 4;
int output = 3;
int numRepeat;
while(true) {
numRepeat = describing[output];
for(int i = 0; i < numRepeat; i++) {
if (input == n) {
return output;
}
if (input > MAX) {
input++;
}
else {
describing[input++] = output;
}
}
output++;
}
}
public void printValue(int value) {
System.out.println(value);
}
public static void main(String[] args) {
DescribingSequence ds = new DescribingSequence();
while(true) {
int n = ds.readNumber();
if (n == 0) {
break;
}
int value = ds.getSequence(n);
ds.printValue(value);
}
}
}
~java
import junit.framework.TestCase;
public class TestDescribingSequence extends TestCase {
public void testBasic() {
DescribingSequence ds = new DescribingSequence();
assertEquals(1, ds.getSequence(1));
assertEquals(2, ds.getSequence(2));
assertEquals(2, ds.getSequence(3));
}
public void testAfter() {
DescribingSequence ds = new DescribingSequence();
assertEquals(3, ds.getSequence(4));
assertEquals(3, ds.getSequence(5));
assertEquals(4, ds.getSequence(6));
}
public void testSample() {
DescribingSequence ds = new DescribingSequence();
assertEquals(21, ds.getSequence(100));
assertEquals(356, ds.getSequence(9999));
assertEquals(1684, ds.getSequence(123456));
assertEquals(438744, ds.getSequence(1000000000));
assertEquals(673365, ds.getSequence(2000000000));
}
}
Self-describingSequence
