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;
}

No comments :

Post a Comment