algorithm the stern brocot number system - andstudy/forge GitHub Wiki

Mastojun

문제 풀이

그래프를 잘 들여다 보면 숫자의 배열에 규칙을 발견할 수 있습니다. 하지만 풀이엔 "참고로, 유리수 m/n과 p/q의 대소를 비교하는데 실제로 m을 n으로, p를 q로 나누어 실수 변수에 대입하는 일은 하지 말자." 라고 되어 있는데.... 전 실제로 나누었습니다 단 float으로 하면 제대로 비교가 될꺼 같지 않아 double로 했어요.

Programming-Challenges 로봇의 문제점

UVa에서는 Accepted를 받았지만 (UVa에서는 Solved를 Accepted라고 표현합니다) PC에서는 Presentation Error를 받았습니다. 저번에도 비슷한 문제로 메일 보낸적이 있었는데 MD5문제라고 하던거 같은데. 이번에도 메일 보냈으니 몇일 이내로 고쳐질꺼라 생각해요.

답장이 왔습니다.

     Hello,
     there were a mistake with the md5sum check, as some time in the past we fixed the 'correct' output and the people in charge, possibly forgot to actualize the database. Sorry and thanks. Take a look in a few minutes, as now we are rejudging all the submissions. I hope yours will get a 'Solved' verdict.
    
     Miguel

이젠 Solved라고 뜨네요

소스 코드

    #include <iostream>
    
    using namespace std;
    
    struct Number
    {
    	int numerator;
    	int denominator;
    
    	double GetRatio()
    	{
    		if( denominator == 0 ) return -1;
    		return ((double)numerator)/denominator;
    	}
    
    	bool operator!=(Number& rhs)
    	{
    		return (rhs.numerator!=numerator)||(rhs.denominator!=denominator);
    	}
    
    	Number operator+(Number& rhs)
    	{
    		Number Temp = *this;
    		Temp.numerator += rhs.numerator;
    		Temp.denominator += rhs.denominator;
    
    		return Temp;
    	}
    };
    
    int main()
    {
    	int n, d;
    
    	while( cin >> n >> d )
    	{
    		if( n == 1 && d == 1 ) break;
    
    		Number Input = {n, d}, Now = {1, 1};
    		Number LeftNumber = {0, 1}, RightNumber = {1, 0};
    
    		while( Now != Input )
    		{
    			if(Input.GetRatio() > Now.GetRatio())
    			{
    				cout << "R";
    				LeftNumber = Now;
    				Now = Now+RightNumber;
    			}
    			else
    			{
    				cout << "L";
    				RightNumber = Now;
    				Now = Now+LeftNumber;
    			}
    		}
    
    		cout << endl;		
    	}
    }

CynicJJ

트리라는 개념에 낚여 한참 헤맸음
- Mastojun님 코드보고 완전 OTL
입출력 처리는 대충 했음. 종료 조건 처리하지 않음.
테스트코드는 너무 길어서 뺐음

!SternBrocotTree.vb

    ' $Id: SternBrocotTree.vb 111 2008-02-26 01:37:22Z 정희종 $
    
    Public Class SternBrocotTree
    
    	Private _root As Node
    	ReadOnly Property Root() As Node
    		Get
    			If _root Is Nothing Then
    				_root = TreeMaker.CreateRoot()
    			End If
    			Return _root
    		End Get
    	End Property
    
    	Function GetPath(ByVal aRational As Rational) As String
    		Dim path As String = ""
    
    		Dim aNode As Node = Root
    		While aRational <> aNode.Rational
    			If aRational < aNode.Rational Then
    				path += "L"
    				aNode = aNode.Left
    			ElseIf aRational > aNode.Rational Then
    				path += "R"
    				aNode = aNode.Right
    			End If
    		End While
    
    		Return path
    	End Function
    
    End Class

Rational.vb

    ' $Id: Rational.vb 109 2008-02-26 01:16:04Z 정희종 $
    
    Public Class Rational
    
    	Sub New(ByVal numerator As Integer, ByVal denominator As Integer)
    		_numerator = numerator
    		_denominator = denominator
    	End Sub
    
    	Sub New(ByVal leftVal As Rational, ByVal rightVal As Rational)
    		_numerator = leftVal.Numerator + rightVal.Numerator
    		_denominator = leftVal.Denominator + rightVal.Denominator
    	End Sub
    
    	Private _numerator As Integer
    	ReadOnly Property Numerator() As Integer
    		Get
    			Return _numerator
    		End Get
    	End Property
    
    	Private _denominator As Integer
    	ReadOnly Property Denominator() As Integer
    		Get
    			Return _denominator
    		End Get
    	End Property
    
    	Shared Operator <(ByVal leftVal As Rational, ByVal rightVal As Rational) As Boolean
    		If leftVal = rightVal Then
    			Return False
    		Else
    			Return Not (leftVal > rightVal)
    		End If
    	End Operator
    
    	Shared Operator >(ByVal leftVal As Rational, ByVal rightVal As Rational) As Boolean
    		Return (leftVal.Numerator * rightVal.Denominator) > (rightVal.Numerator * leftVal.Denominator)
    	End Operator
    
    	Shared Operator =(ByVal leftVal As Rational, ByVal rightVal As Rational) As Boolean
    		Return (leftVal.Numerator * rightVal.Denominator) = (rightVal.Numerator * leftVal.Denominator)
    	End Operator
    
    	Shared Operator <>(ByVal leftVal As Rational, ByVal rightVal As Rational) As Boolean
    		Return Not (leftVal = rightVal)
    	End Operator
    
    	Overrides Function Equals(ByVal compared As Object) As Boolean
    		Return Me = compared
    	End Function
    
    End Class

Node.vb

    ' $Id: Node.vb 113 2008-02-26 02:06:51Z 정희종 $
    
    Public Class Node
    
    	Private _left As Node
    	ReadOnly Property Left() As Node
    		Get
    			If _left Is Nothing Then
    				_left = TreeMaker.CreateLeftNode(Me)
    			End If
    			Return _left
    		End Get
    	End Property
    
    	Private _right As Node
    	ReadOnly Property Right() As Node
    		Get
    			If _right Is Nothing Then
    				_right = TreeMaker.CreateRightNode(Me)
    			End If
    			Return _right
    		End Get
    	End Property
    
    	Private _rational As Rational
    	Property Rational() As Rational
    		Get
    			Return _rational
    		End Get
    		Set(ByVal value As Rational)
    			_rational = value
    		End Set
    	End Property
    
    End Class

!TreeMaker.vb

    ' $Id: TreeMaker.vb 113 2008-02-26 02:06:51Z 정희종 $
    
    Module TreeMaker
    
    	Private _rationals As List(Of Rational)
    
    	Sub InitRationals()
    		_rationals = New List(Of Rational)
    		_rationals.Add(New Rational(0, 1))
    		_rationals.Add(New Rational(1, 1))
    		_rationals.Add(New Rational(1, 0))
    	End Sub
    
    	Function CreateRoot() As Node
    		InitRationals()
    
    		Dim root As Node = New Node
    		root.Rational = _rationals(1)
    
    		Return root
    	End Function
    
    	Function CreateLeftRational(ByVal parentRational As Rational) As Rational
    		Dim matchIndex As Integer = _rationals.IndexOf(parentRational)
    
    		Dim left As Rational = _rationals(matchIndex - 1)
    
    		Dim leftRational As Rational = New Rational(left, parentRational)
    		_rationals.Insert(matchIndex, leftRational)
    
    		Return leftRational
    	End Function
    
    	Function CreateRightRational(ByVal parentRational As Rational) As Rational
    		Dim matchIndex As Integer = _rationals.IndexOf(parentRational)
    
    		Dim right As Rational = _rationals(matchIndex + 1)
    
    		Dim rightRational As Rational = New Rational(parentRational, right)
    		_rationals.Insert(matchIndex + 1, rightRational)
    
    		Return rightRational
    	End Function
    
    	Function CreateLeftNode(ByVal parentNode As Node) As Node
    		Dim left As Node = New Node
    		left.Rational = CreateLeftRational(parentNode.Rational)
    
    		Return left
    	End Function
    
    	Function CreateRightNode(ByVal parentNode As Node) As Node
    		Dim right As Node = New Node
    		right.Rational = CreateRightRational(parentNode.Rational)
    
    		Return right
    	End Function
    End Module

!ModuleMain.vb

    Module ModuleMain
    
    	Sub Main()
    		While True
    			Dim input As String = Console.ReadLine()
    			Dim tree As SternBrocotTree = New SternBrocotTree
    			Dim rational As Rational = GetRationalFromInput(input)
    			Console.WriteLine(tree.GetPath(rational))
    		End While
    	End Sub
    
    	Function GetRationalFromInput(ByVal input As String) As Rational
    		Dim separator() As Char = {" "c}
    		Dim strs() As String = input.Split(separator, StringSplitOptions.RemoveEmptyEntries)
    
    		Dim numerator As Integer = Integer.Parse(strs(0))
    		Dim denominator As Integer = Integer.Parse(strs(1))
    
    		Return New Rational(numerator, denominator)
    	End Function
    
    End Module

kukuman

풀이
- 분수를 나타내는 FraExpress 를 이용하여 문제를 해결함
- 분수 간의 크기 비교는 분자 분모 항이동을 통해 비교하였다. 소숫점 비교를 피함
  - a/b 와 x/y의 비교는 ay 와 bx의 값의 비교를 통해 구했다
- 실제 트리 순회는 1/1로부터 현재 노드 값보다 크면 오른쪽 작으면 왼쪽으로 이동 되게 구현 하였다
  - 이동 작업은 현재 노드,왼쪽 노드,오른쪽 노드의 변경으로 구현

소스

  import java.io.IOException;
  
  public class Main implements Runnable {
  	static String ReadLn(int maxLength) { // utility function to read from
  											// stdin,
  		// Provided by Programming-challenges, edit for style only
  		byte line[] = new byte[maxLength];
  		int length = 0;
  		int input = -1;
  		try {
  			while (length < maxLength) {// Read untill maxlength
  				input = System.in.read();
  				if ((input < 0) || (input == '\n'))
  					break; // or untill end of line ninput
  				line[length++] += input;
  			}
  
  			if ((input < 0) && (length == 0))
  				return null; // eof
  			return new String(line, 0, length);
  		} catch (IOException e) {
  			return null;
  		}
  	}
  
  	public static void main(String[] args) {
  		Main main = new Main();
  		main.run();
  	}
  	public void run() {
  		while(true){
  			String line = ReadLn(255).trim();
  			if(line == null || line.equals("1 1")){
  				break;
  			}
  			String [] strSplit = line.split(" ");
  			if(strSplit.length!=2){
  				break;
  			}
  			String result = SBTreeTravelResult(new FraExpress( Integer.parseInt(strSplit[0]), Integer.parseInt(strSplit[1])));
  			System.out.println(result);
  		}
  	}
  
  	public String SBTreeTravelResult(FraExpress searchVal) {
  		FraExpress curNode = new FraExpress(1, 1);
  		FraExpress leftNode = new FraExpress(0, 1);
  		FraExpress rightNode = new FraExpress(1, 0);
  		StringBuilder builder = new StringBuilder();
  		while (curNode.compareTo(searchVal) != 0) {
  			int compareResult = searchVal.compareTo(curNode);
  			if (compareResult > 0) {
  				// 찾을 값이 현재 노드보다 크다면 오른쪽으로 서칭
  				builder.append("R");
  				leftNode = curNode;
  				curNode = curNode.add(rightNode);
  			} else if (compareResult < 0) {
  				// 찾을 값이 현재 노드보다 작으면 왼쪽으로 서칭
  				builder.append("L");
  				rightNode = curNode;// 현재 노드는 오른쪽으로 이동됨
  				curNode = curNode.add(leftNode);
  			} else {
  				// 현제노드값이 찾는 값이면 검색 종료
  				break;
  			}
  		}
  		return builder.toString();
  	}
  
  }
  
  class FraExpress implements Comparable<FraExpress> {
  	private int denominator; // 분자
  
  	private int numerator; // 분모
  
  	public FraExpress(int denominator, int numerator) {
  		this.denominator = denominator;
  		this.numerator = numerator;
  	}
  
  	public int compareTo(FraExpress o) {
  		/**
  		 * x a -- 와 -- 의 비교는 xb 와 ay의 비교와 같다 y b
  		 */
  		int left = this.denominator * o.numerator;
  		int right = this.numerator * o.denominator;
  		if (left < right)
  			return -1;
  		else if (left > right)
  			return 1;
  		else
  			return 0;
  	}
  
  	public FraExpress add(FraExpress addend) {
  		return new FraExpress(this.denominator + addend.denominator,
  				this.numerator + addend.numerator);
  	}
  }

테스트 케이스

  import junit.framework.TestCase;
  
  
  public class SternBrocot extends TestCase {
  	public void testFraExpressCompare(){
  		FraExpress a = new FraExpress(1,2);
  		FraExpress b = new FraExpress(1,1);
  		FraExpress c = new FraExpress(2,1);
  		assertEquals(0,a.compareTo(a));
  		assertEquals(-1,a.compareTo(b)); // a<b
  		assertEquals(1,b.compareTo(a)); // b<a
  		assertEquals(-1,a.compareTo(c)); // a<c
  	}
  	
  	public void testSBTreeTravelResult(){
  		Main main = new Main();
  		assertEquals("LRRL", main.SBTreeTravelResult(new FraExpress(5,7)));
  		assertEquals("RRLRRLRLLLLRLRRR", main.SBTreeTravelResult(new FraExpress(878 ,323)));
  	}
  }

Outbreak

문제 요약

스턴-브로콧 숫자 시스템이 Binary Search Tree 인 것을 알아채는 문제

문제 해결

Left(m/n), Current(m+M/n+N), Right(M/N) 을 재귀로 돌렸다.
- 입력값의 크기가 상당히(?) 클 때 재귀 호출을 하면 스택 오버 플로우가 발생할 수 있다.
  - Solver2를 C++로 포팅하고 테스트 해본결과, Debug모드로 돌리면 StackOverflow, Relase모드로 돌리면 제대로 수행됩니다. 꼬리재귀가 동작하는듯 한데.. C#은 Debug로하든, Release로 하든 뻗어버리는군요 (.NET 2005로 테스트했어요)
  - C# 에는 Tail Recursion 이 구현 안되어 있는 것 같습니다.
  - 그러고 보니 .NET 가상 머신 오버플로우 내서 죽인다고 했을 때 이 방법을 썼었네요
  - http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx
  - 위 자료를 요약하면 ".NET 에는 Tail-Recursion IL 명령이 있지만, C#에서는 지원하지 않는다" 낭패 ^^;
    
    int TestFun() { return TestFun(); }
위와 같은 코드로도 테스트 해봤는데 마찬가지의 결과가 나옵니다. Debug모드는 꼬리재귀가 안되는건지.... 아니면 C++ Release모드는 스택용량이 재한없는건지....;;;
스택 사용량을 줄이려고 노력했으나..
결국 Iteration 버전도 만들었다 ^^

기타

scheme 으로 하기 딱 좋은 문제라는 생각.. 만 ^^;
Tail Recursion 을 만들려고 했는데 출력 때문에 불가

코드 1 - Recursion

    using System;
    using System.Collections.Generic;
    using System.Text;
    
    namespace Scort
    {   
        class Solver
        {
            int m;
            int n;
    
            public Solver(int m, int n)
            {
                this.m = m;
                this.n = n;
            }
    
            // invariant : the fraction must be existed between 0/1 and 1/0        
            public void Traverse(int lM, int lN, int rM, int rN)
            {
                // l(left)  c(center)   r(Right)
                int cM = lM + rM;
                int cN = lN + rN;
    
                // c의 왼쪽
                if (cM * n > m * cN) 
                {
                    Console.Write("L");
                    Traverse(lM, lN, cM, cN);
                }
                // c의 오른쪽
                else if (cM * n < m * cN) 
                {
                    Console.Write("R");
                    Traverse(cM, cN, rM, rN);
                }            
            }
    
            public void Run()
            {
                if (m > 0 && n > 0)
                {                
                    Traverse(0, 1, 1, 0);
                    Console.WriteLine();
                }          
            }
        }
    }

코드 2 - Recursion

    namespace Scort
    {
        class Solver2
        {
            int m, n;
    
            int lM, lN, rM, rN;
            int cM, cN;
    
            public Solver2(int m, int n)
            {
                this.m = m;
                this.n = n;
    
                lM = 0; lN = 1;
                rM = 1; rN = 0;
            }
    
    
            public void Traverse()
            {
                cM = lM + rM;
                cN = lN + rN;
    
                if (cM * n > m * cN)
                {
                    Console.Write("L");
                    rM = cM;
                    rN = cN;
                    Traverse();
                }
                else if (cM * n < m * cN)
                {
                    Console.Write("R");
                    lM = cM;
                    lN = cN;
                    Traverse();
                }            
            }
    
            public void Run()
            {
                if (m > 0 && n > 0)
                {
                    Traverse();
                    Console.WriteLine();
                }
            }
        }
    }

코드 3 - Iteration

    namespace Scort
    {
        class Solver3
        {
            int m, n;
    
            int lM, lN, rM, rN;
            int cM, cN;
    
            public Solver3(int m, int n)
            {
                this.m = m;
                this.n = n;
    
                lM = 0; lN = 1;
                rM = 1; rN = 0;
            }
    
            public bool Traverse()
            {
                cM = lM + rM;
                cN = lN + rN;
    
                if (cM * n > m * cN)
                {
                    Console.Write("L");
                    rM = cM;
                    rN = cN;
                    return false;
                }
    
                else if (cM * n < m * cN)
                {
                    Console.Write("R");
                    lM = cM;
                    lN = cN;
                    return false;
                }
    
                return true;
            }
    
            public void Run()
            {
                if (m > 0 && n > 0)
                {
                    while(true)
                    {
                        if( Traverse() == true )
                        {
                            break;
                        }
                    }
    
                    Console.WriteLine();
                }
            }
        }
    }

유닛테스트

    using System;
    using System.Collections.Generic;
    using System.Text;
    
    namespace Scort
    {     
        class Program
        {
            static void Main(string[] args)
            {
                // 눈으로 유닛테스트.. 후후
    
                // Recursion
                Solver solver = new Solver(878,323);
                solver.Run();
    
                // 스택 덜 쓰는 Recursion
                Solver2 solver2 = new Solver2(878, 323);
                solver2.Run();
    
                // Iteration
                Solver3 solver3 = new Solver3(878, 323);
                solver3.Run();
    
                solver3 = new Solver3(2007777777, 3);
                solver3.Run();
            }
        }
    }

스터디에서제작

한글로 코딩 해봤습니다. -0-
- 재귀로 문제를 해결

코드

  public class Main {
  	private StringBuilder result ;
  	public String SBTreeTravelResult(분수 찾을값) {
  		분수 오른쪽 = new 분수(1,0);
  		분수 왼쪽 = new 분수(0,1);
  		result = new StringBuilder();
  		SBTreeTravelResult(찾을값, 오른쪽,왼쪽);
  		return result.toString();
  	}
  
  	private void SBTreeTravelResult(분수 찾을값, 분수 오른쪽, 분수 왼쪽) {
  		분수 현재노드 = 오른쪽.add(왼쪽);
  		if(찾을값.compareTo(현재노드) ==0){
  			return ;
  		}
  
  		if(찾을값.compareTo(현재노드) >0){
  			왼쪽 = 현재노드;
  			result.append("R");
  		}else if(찾을값.compareTo(현재노드) <0){
  			오른쪽 = 현재노드;
  			result.append("L");
  		}
  		SBTreeTravelResult(찾을값,  오른쪽, 왼쪽);
  	}
  }

분수

  public class 분수 implements Comparable<분수>{
  	private int 분모;
  	private int 분자;
  	public 분수(int 분자, int 분모) {
  		this.분자 = 분자;
  		this.분모 = 분모;
  	}
  	public int compareTo(분수 비교대상) {
  		long 가= 비교대상.분모 * this.분자;
  		long 나 = this.분모 * 비교대상.분자;
  		if(가 == 나){
  			return 0;
  		}else if(가 > 나 ){
  			return 1;
  		}else{
  			return -1;
  		}
  			
  		
  	}
  	public 분수 add(분수 덧수) {
  		int 분자 = this.분자 + 덧수.분자;
  		int 분모 = this.분모 + 덧수.분모;
  		return new 분수(분자,분모);
  	}
  
  }

테스트

  import junit.framework.TestCase;
  
  
  public class MainTestCase extends TestCase {
  	public void test분수비교하기(){
  		분수 bun1 = new 분수(3,4);
  		분수 bun2 = new 분수(3,4);
  		분수 bun3 = new 분수(1,2);
  		분수 bun4 = new 분수(1,1);
  		assertEquals(0, bun1.compareTo(bun2));
  		assertEquals(1, bun1.compareTo(bun3));
  		assertEquals(-1, bun3.compareTo(bun4));
  		
  	}
  	
  	public void test결과계산(){
  		Main main = new Main();
  		assertEquals("LRRL", main.SBTreeTravelResult(new 분수(5,7)));
  		assertEquals("RRLRRLRLLLLRLRRR", main.SBTreeTravelResult(new 분수(878 ,323)));
  	}
  }

algorithm the stern brocot number system - andstudy/forge GitHub Wiki

Mastojun

문제 풀이

Programming-Challenges 로봇의 문제점

소스 코드

CynicJJ

!SternBrocotTree.vb

Rational.vb

Node.vb

!TreeMaker.vb

!ModuleMain.vb

kukuman

Outbreak

문제 요약

문제 해결

기타

코드 1 - Recursion

코드 2 - Recursion

코드 3 - Iteration

유닛테스트

스터디에서제작

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️