아래와 같이 생성된 분수 수열에 번호를 붙인 무한한 포화이진트리를 생각해보자.

* 루트는 1/1 이다. * p/q 의 왼쪽 자식은 p/(p+q) 이다. * p/q 의 오른쪽 자식은 (p+q)/q 이다.

이 트리의 일부 모습은 아래와 같다.

이 트리의 방문 순서는 너비우선탐색이다. 따라서 트리의 k번째 값을 F(k)라고 할 때, 값들을 나열하면 F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F[5] = 3/2, F[6] = 2/3 .... 이 된다.

분수 수열 F(n) = p/q, 가 주어질 때, F(n+1)을 구하는 프로그램을 작성하시오.

분수 수열 timer 1s memory 16MB

분수 수열 1s 16MB