imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:01Z

New page

2006.1.9

== 쓰레드 ==
* 구현은 했는데 close form으로 식을 못 만들겠다;
* 메모리 사용을 줄이기 위한 방안이 필요하다. 또한 입력값에 맞는 배열 크기 할당이 요구된다. 여기는 입력 값에 관계없이 최대 입력 값에 맞는 배열 크기를 할당하였다.

== 소스 코드 ==
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);
}
}
}

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]]

Self-describingSequence/황재선 - Revision history

imported>Unknown at 05:28, 7 February 2021