| 수와 연산 Numbers and Operations | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#765432> 수 체계 | 자연수 (홀수 · 짝수 · 소수 · 합성수) · 정수 · 유리수 (정수가 아닌 유리수) · 실수 (무리수 · 초월수) · 복소수 (허수) · 사원수 | |
| 표현 | 숫자 (아라비아 숫자 · 로마 숫자 · 그리스 숫자) · 기수법(과학적 기수법 · E 표기법 · 커누스 윗화살표 표기법 · 콘웨이 연쇄 화살표 표기법 ·BEAF· 버드 표기법) · 진법 (십진법 · 이진법 · 8진법 · 12진법 · 16진법 · 60진법) · 분수 (분모 · 분자 · 기약분수 · 번분수 · 연분수 · 통분 · 약분) · 소수 {유한소수 · 무한소수 (순환소수 · 비순환소수)} · 환원 불능 · 미지수 · 변수 · 상수 | ||
| 연산 | 사칙연산 (덧셈 · 뺄셈 · 곱셈 구구단 · 나눗셈) · 역수 · 절댓값 · 제곱근 (이중근호) · 거듭제곱 · 로그 (상용로그 · 자연로그 · 이진로그) · 검산 · 연산자 · 교환자 | ||
| 방식 | 암산 · 세로셈법 · 주판 · 산가지 · 네이피어 계산봉 · 계산기 · 계산자 | ||
| 용어 | 이항연산(표기법) · 항등원과 역원 · 교환법칙 · 결합법칙 · 분배법칙 | ||
| 기타 | 수에 관련된 사항 (0과 1 사이의 수 · 음수 · 작은 수 · 큰 수) · 혼합 계산 (48÷2(9+3) · 111+1×2=224 · 2+2×2) · 0으로 나누기(바퀴 이론) · 0의 0제곱 | }}}}}}}}} | |
1. 개요
Stern-Brocot Tree 슈테른-브로코 트리는 각 꼭짓점이 모든 양의 유리수 [math(\dfrac mn)](m과 n은 서로소)에 일대응되는 무한 이진 트리다. 슈테른-브로코 트리에선 모든 양의 유리수가 기약분수의 형태로 정확히 한 번 나타나며 오름차순으로 정렬된다.
독일의 수학자 모리츠 슈테른(Moritz Stern)과 프랑스의 시계공 아킬 브로코(Achille Brocot)가 각각 1858년, 1861년에 독립적으로 발견했다. 아킬 브로코는 기어 장치의 설계를 연구하는 중 기어의 비를 특정값에 잘 근사하는 수치로 책정하기 위해 이 트리를 고안했다.
2. 구성
트리를 구축하는 방법은 이러하다. 먼저 양의 유리수 집합의 하한과 상한 [math(0)], [math(\infty)]을 생성한다. 하지만 당연히 [math(\infty)]는 분수로 나타낼 수 없다. 그러나 편리함을 위해 [math(\frac{1}{0})]을 0으로 나누기가 불가능 하다는 점을 무시하고 유리수 집합의 상한이라 가정하자.[math(\dfrac{0}{1})] [math(\dfrac{1}{0})]
이제 트리가 생성할 기약분수는 위 두 수 사이에 놓여있다. 그리고 어떤 두 분수 [math(\dfrac{a}{b} < \dfrac{c}{d})]가 주어졌을 때 메디언트(mediant) [math(\dfrac{a+c}{b+d})]는 [math(\dfrac{a}{b} < \dfrac{a+c}{b+d} < \dfrac{c}{d})]를 만족한다. 트리는 이 부등식을 이용한 다음의 생성 규칙을 재귀적으로 적용한다.생성 규칙: [math(\dfrac{a}{b})]와 [math(\dfrac{c}{d})]가 이웃할 경우 [math(\dfrac{a+b}{c+d})]를 그 사이에 삽입한다.
먼저 [math(\frac{0}{1})], [math(\frac{1}{0})] 사이 1을 삽입한다.[math(\dfrac{0}{1})] [math(\dfrac{1}{1})] [math(\dfrac{1}{0})]
이 최초로 삽입된 값이 슈테른-브로코 트리의 뿌리 노드이며, 부모 노드는 좌우로 생성규칙을 적용하여 항상 두 개의 자식노드를 생성한다. 다음은 생성 규칙을 재귀적으로 여러번 적용시킨 것이다.[math(\dfrac{0}{1})] [math(\dfrac{1}{2})] [math(\dfrac{1}{1})] [math(\dfrac{2}{1})] [math(\dfrac{1}{0})] (1 좌우로 생성 규칙을 적용)
[math(\dfrac{0}{1})] [math(\dfrac{1}{3})] [math(\dfrac{1}{2})] [math(\dfrac{2}{3})] [math(\dfrac{1}{1})] [math(\dfrac{3}{2})] [math(\dfrac{2}{1})] [math(\dfrac{3}{1})] [math(\dfrac{1}{0})] (1/2, 2/1 좌우로 생성 규칙을 적용)
[math(\dfrac{0}{1})] [math(\dfrac{1}{4})] [math(\dfrac{1}{3})] [math(\dfrac{2}{5})] [math(\dfrac{3}{5})] [math(\dfrac{2}{3})] [math(\dfrac{3}{4})] [math(\dfrac{1}{1})] [math(\dfrac{4}{3})] [math(\dfrac{3}{2})] [math(\dfrac{5}{3})] [math(\dfrac{2}{1})] [math(\dfrac{5}{2})] [math(\dfrac{3}{1})] [math(\dfrac{4}{1})] [math(\dfrac{1}{0})] (1/3, 2/3, 3/2, 3/1 좌우로 생성 규칙을 적용)
이와 같은 과정을 반복하면 모든 기약분수가 오름차순으로 나열된다.[math(\dfrac{0}{1})] [math(\dfrac{1}{3})] [math(\dfrac{1}{2})] [math(\dfrac{2}{3})] [math(\dfrac{1}{1})] [math(\dfrac{3}{2})] [math(\dfrac{2}{1})] [math(\dfrac{3}{1})] [math(\dfrac{1}{0})] (1/2, 2/1 좌우로 생성 규칙을 적용)
[math(\dfrac{0}{1})] [math(\dfrac{1}{4})] [math(\dfrac{1}{3})] [math(\dfrac{2}{5})] [math(\dfrac{3}{5})] [math(\dfrac{2}{3})] [math(\dfrac{3}{4})] [math(\dfrac{1}{1})] [math(\dfrac{4}{3})] [math(\dfrac{3}{2})] [math(\dfrac{5}{3})] [math(\dfrac{2}{1})] [math(\dfrac{5}{2})] [math(\dfrac{3}{1})] [math(\dfrac{4}{1})] [math(\dfrac{1}{0})] (1/3, 2/3, 3/2, 3/1 좌우로 생성 규칙을 적용)
3. 성질
* 슈테른-브로코 트리의 모든 분수는 기약분수다.
* 모든 기약분수는 슈테른-브로코 정확히 한 번 트리에 대응된다.
* 생성 규칙을 n번 적용한 트리의 모든 분자 분모는 [math(\leqq F_{n+1})]
* 모든 기약분수는 슈테른-브로코 정확히 한 번 트리에 대응된다.
* 생성 규칙을 n번 적용한 트리의 모든 분자 분모는 [math(\leqq F_{n+1})]