Self-describing Sequence/황재선

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