Re: Algorithms

Patricia Shanahan <pats@acm.org> wrote:


True, but in this case I get the feeling that the problem was more in
understanding the problem than in finding an algorithm. I get the sense
that the person who asked would have trouble answering basic clarifying
questions about the problem. The biggest is: if there are multiple
possible roman numerals for a given number, what criteria are used to
decide which one is desired? Without an answer to that, the most clear
and elegant algorithm is a simple greedy algorithm that looks like this:

    String[] syms = { "C", "L", "X","V","I"}
    int[] vals = { 100, 50, 10, 5, 1 }

    ans = "";

    for (int i = 0; i < syms.length; i++)
    {
        while (value > vals[i])
        {
            ans += syms[i];
            value -= vals[i];
        }
    }

    return ans;

I suspect that most people will be unhappy with the result, but why?
The answer is a perfectly valid roman numeral. There are many ways of
writing most numbers in roman numerals. Some are shorter than others.
Some come from context (for example, when expressing a year, it's
customary to separate the thousands/hundreds from the tens/ones, so 1990
would never be written as XMM). Until the requirements are nailed down
in this way, it's too early to think about algorithms.

--
Chris Smith