문제 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)

참조 링크

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

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

루트

이다.

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

출력

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

맛보기 코드

맛보기 사진

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

:wq!

저작자 표시
신고

'책 정리 > Programming Challenges : 알고리즘 트래이닝 북' 카테고리의 다른 글

문제 44, 표현식, Expressions, PC/UVa ID : 110604/10157, 인기도 : C, 성공률 : 보통, 레벨 : 2  (0) 2015.02.04
문제 43, 셈, Counting, PC/UVa ID : 110603/10198, 인기도 : B, 성공률 : 높음, 레벨 : 2  (2) 2011.08.22
문제 42, 땅 나누기, How many Pieces of Land?, PC/UVa ID : 110602/10213, 인기도 : B, 성공률 : 보통, 레벨 : 2  (1) 2011.08.01
문제 41, 피보나치 수의 개수, How many Fibs?, PC/UVa ID : 110601/10183, 인기도 : B, 성공률 : 보통, 레벨 : 1  (0) 2011.07.29
문제 40, 모든 쌍의 합, Pairsumonious Numbers, PC/UVa ID : 110508/10202, 인기도 : B, 성공률 : 높음, 레벨 : 4  (0) 2011.07.27
문제 39, 스턴-브로콧 수체계, The Stern-Brocot Number System, PC/UVa ID : 110507/10077, 인기도 : C, 성공률 : 높음, 레벨 : 1  (0) 2011.07.03
문제 38, 다항식의 계수, Polynomial Coefficients, PC/UVa ID : 110506/10105, 인기도 : B, 성공률 : 높음, 레벨 : 1  (0) 2011.06.14
문제 37, 곱하기 게임, A Multiplication Game, PC/UVa ID : 110505/847, 인기도 : A, 성공률 : 높음, 레벨 : 3  (0) 2011.05.07
문제 36, 1의 개수, Ones, PC/UVa ID : 110504/10127, 인기도 : A, 성공률 : 높음, 레벨 : 2  (0) 2011.05.05
문제 35, 고고학자의 딜레마, The Archeologist's Dilemma, PC/UVa ID : 110503/701, 인기도 : A, 성공률 : 낮음, 레벨 : 1  (0) 2011.05.05
문제 34, 뒤집어서 더하기, Reverse and Add, PC/UVa ID : 110502/10018, 인기도 : A, 성공률 : 낮음, 레벨 : 1  (0) 2011.03.10
posted by 농사를 짓는 게임 프로그래머 최익필

댓글을 달아 주세요