Chris Smith wrote:
Patricia Shanahan <pats@acm.org> wrote:
There are design patterns for algorithms. Once you learn them, with a
bit of practice algorithm problems start feeling like
divide-and-conquer, or feeling like dynamic programming.
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])
Should be '>=' here.
{
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.
Yes. And the algorithm is valid as well. It only lack some data for
the different requirements, e.g.:
String[] syms = { "M",
"CM","D","CD","C","XC","L","XL","X","IX","V","IV","I" };
int[] vals = { 1000,900, 500,400, 100,90, 50, 40, 10, 9, 5,
4, 1 };
Until the requirements are nailed down in this way, it's too early to
think about algorithms.
Almost true -- your algorithm is the exception. ;)