문제 39, 스턴-브로콧 수체계, The Stern-Brocot Number System, PC/UVa ID : 110507/10077, 인기도 : C, 성공률 : 높음, 레벨 : 1

문제 39, 스턴-브로콧 수체계, The Stern-Brocot Number System, PC/UVa ID : 110507/10077, 인기도 : C, 성공률 : 높음, 레벨 : 1

이 포스트를 만든 목적

• 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
  

이 포스트의 준비물

• Mozila Firefox 5.0
  
• eclipse 3.6.1 + vrapper
  
• java
  

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 38, 스턴-브로콧 수체계, The Stern-Brocot Number System, p.159)
  

참조 링크

• http://online-judge.uva.es/p/v100/10077.html - 문제 원문
  
• http://en.wikipedia.org/wiki/Stern-Brocot_tree - 영어 못하는데 검색하면 영어만 걸린다. ㅋ
  
• http://www.codecogs.com/latex/eqneditor.php - 수식을 이미지로 만들오 주는 싸이트
  
• http://online-judge.uva.es/board/viewtopic.php?f=9&t=6840 - 잘 보면, 공통분모 개념 이용
  

간략한 이야기/프로그램의 입출력

스턴-브로콧 수체계를 이해하고, 양의 분수가 입력되었을 때, 그 분수가 스턴-브로콧 수체계에서 위치한 곳을 루트로 부터 L과 R로 표시하여 출력하라.루트는 다음 수를 기준으로 하고 루트의 1/1 로부터 외쪽으로 가면 L, 오른쪽으로 가면 R로 표기한다.

루트

이다.

입력

• 한줄에 양의 정수 m 과 n을 입력 받으며, m과 n은 서로 소다.
  
• m과 n 모두 1이 입력되면 프로그램을 종료 시킨다.
  
• m은 분자이고, n은 분모이다.
  

출력

• 루트를 기준으로 입력된 m/n의 위치를 L,R 로 출력한다.

맛보기 코드
package Problem039TheSternBrocotNumberSystem; import java.util.*; public class TheSternBrocotNumberSystem { public static void main( String[] args) { Scanner sc = new Scanner(System.in); for (;;) { int m = sc.nextInt(); int n = sc.nextInt(); if ((1 >= m && 1 >= n) || 1.0f == (double)m / (double)n) break; String strTree = getTreeString(m, n); System.out.println(strTree); } } public static String getTreeString(int m, int n) { StringBuffer sb = new StringBuffer(); int[] arrNumerator = { 0, 1, 1 }; int[] arrDenominator = { 1, 1, 0 }; sb = moveTree(sb, arrNumerator, arrDenominator, m, n); return sb.toString(); } private static StringBuffer moveTree(StringBuffer sb, int arrNumerator[], int arrDenominator[], int m, int n) { // 공통 분모를 만든다는 개념으로 보면, 이 주석는 좋지 않다. //double centerValue = (double)arrNumerator[1]/(double)arrDenominator[1]; //double targetValue = (double)m / (double)n; int centerValue = arrNumerator[1] * n; int targetValue = arrDenominator[1] * m; if (centerValue == targetValue) { return sb; } else if (centerValue > targetValue) { sb.append("L"); arrNumerator[2] = arrNumerator[1]; arrDenominator[2] = arrDenominator[1]; } else { sb.append("R"); arrNumerator[0] = arrNumerator[1]; arrDenominator[0] = arrDenominator[1]; } arrNumerator[1] = arrNumerator[0] + arrNumerator[2]; arrDenominator[1] = arrDenominator[0] + arrDenominator[2]; return moveTree(sb, arrNumerator, arrDenominator, m, n); } }
package Problem039TheSternBrocotNumberSystem; import static org.junit.Assert.*; import org.junit.Test; public class TheSternBrocotNumberSystemTest { @Test public void testGetTreeString() { assertTrue("LRRL".equals(TheSternBrocotNumberSystem.getTreeString(5, 7))); assertTrue("RRLRRLRLLLLRLRRR".equals(TheSternBrocotNumberSystem.getTreeString(878, 323))); } }

맛보기 사진

여담

• 분수를 계산할 때, 나누기보단, 곱하기를 이용해 더 빠르게 계산 가능하다.(공통분모 개념)
  
• 문제만 이해 되면, 답은 뭐 어떻게 해서든 낼 수 있으니, 전혀 어렵지 않았다.
  
• 입력 값 기준으로 역으로 루트까지 올라 가려 했으나, 공식 만들기 실패해서, 포기하고 루트에서 내려가도록 했다.
  

:wq!