스턴-브로콧 트리 계산기
L/R 경로로 기약분수를 찾거나, 기약분수로 경로를 구합니다. 모든 양의 기약분수가 정확히 한 번씩 나타나는 이진트리입니다.
분수
2/3
뿌리는 1/1입니다. L로 가면 더 작은 분수 쪽으로, R로 가면 더 큰 분수 쪽으로 내려갑니다. 경로의 L·R 뭉치 길이는 유클리드 호제법의 몫과 정확히 대응합니다.
계산 방법
- 1경로 → 분수인지 분수 → 경로인지 고릅니다.
- 2L/R 경로 또는 분자·분모를 입력합니다.
- 3결과를 확인합니다.
자주 묻는 질문
모든 양의 기약분수(더 못 약분하는 분수)를 정확히 한 번씩 담는 이진트리입니다. 뿌리는 1/1이고, 왼쪽 경계 0/1과 오른쪽 경계 1/0에서 시작해 두 경계의 중앙값(분자끼리·분모끼리 더한 값)이 각 노드의 값이 됩니다.
왼쪽으로 가면 오른쪽 경계가 방금 노드의 값으로 좁혀지고, 오른쪽으로 가면 왼쪽 경계가 좁혀집니다. 그래서 왼쪽 자식은 항상 부모보다 작고, 오른쪽 자식은 항상 부모보다 큽니다 — 이진 탐색 트리처럼 동작합니다.
증명이 필요한 정리지만 직관적으로는, 중앙값 연산 자체가 두 기약분수 사이에 있는 "가장 간단한" 분수를 만들어내고, 이 과정이 유클리드 호제법과 정확히 대응하기 때문입니다. 모든 양의 유리수는 유클리드 호제법으로 유일하게 표현되므로, 트리에서의 위치도 유일합니다.
분수를 찾아가는 경로에서 L이나 R이 연달아 나오는 뭉치의 길이가 연분수 전개의 계수, 즉 유클리드 호제법에서 나오는 몫과 정확히 같습니다. 예를 들어 5/2를 찾는 경로는 RR L(대략)처럼 되는데, 이는 5=2×2+1, 2=1×2+0이라는 나눗셈의 몫 2, 2와 대응됩니다.
알아두면 좋은 점
- 경로가 너무 길면(예: 서로 가까운 큰 분모의 분수) 계산에 시간이 걸릴 수 있어 상한을 둡니다.
함께 보면 좋은 도구
파레이 수열분모가 n 이하인 0~1 사이 기약분수를 모두 늘어놓고, 이웃한 두 항이 bc − ad = 1을 만족하는 것과 중항이 그 사이에 들어오는 것을 보여 줍니다.연분수 계산수를 연분수 [a0; a1, a2, …]로 펼치고 단계마다 얻는 근사분수를 보여줍니다.죄수와 상자죄수 수와 열 수 있는 상자 수를 넣으면 아무 상자나 여는 전략과 사이클을 따라가는 전략의 전원 성공 확률을 각각 구합니다.15퍼즐 판정슬라이딩 퍼즐 배치를 넣으면 아무리 밀어도 맞출 수 있는 배치인지 판정합니다.열전도 유한차분막대의 온도 분포를 외재적 유한차분으로 시간에 따라 계산합니다.
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.