online advertising

Sunday, October 26, 2014

UVa Problem 10077 - The Stern-Brocot Number System

Problem:

Please find the problem here.

Solution:

The key observations are, it is easy to generate the children node if we know the previous node and next node, and the tree is actually a binary search tree. So the algorithm is effectively no different from a standard binary tree search.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1018

#include "UVa10077.h"

#include <iostream>
#include <string>
#include <map>

using namespace std;

int UVa10077()
{
while (true)
{
int m, n;
cin >> m >> n;
if (m == 1 && n == 1)
{
break;
}
int prev_m = 0;
int prev_n = 1;
int next_m = 1;
int next_n = 0;
while (true)
{
int middle_m = prev_m + next_m;
int middle_n = prev_n + next_n;

if (middle_m == m && middle_n == n)
{
break;
}
else
{
if (middle_m * n > middle_n * m)
{
cout << "L";
next_m = middle_m;
next_n = middle_n;
}
else
{
cout << "R";
prev_m = middle_m;
prev_n = middle_n;
}
}
}
cout << endl;
}

return 0;
}