Re: Algorithms

Chris Smith wrote:
Patricia Shanahan <pats@xxxxxxx> 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. ;)


piotr
.

Relevant Pages

  • Re: Algorithms
    ... or feeling like dynamic programming. ... understanding the problem than in finding an algorithm. ... possible roman numerals for a given number, ...
    (comp.lang.java.help)
  • Re: Algorithms
    ... or feeling like dynamic programming. ... but in this case I get the feeling that the problem was more in understanding the problem than in finding an algorithm. ... Personally, I prefer the data version, unless you need to handle old style non-subtractive Roman numerals. ...
    (comp.lang.java.help)
  • Re: MP needed for 24x36 print?
    ... how well the algorithm works. ... produce much better results than unsharp mask. ... >>> If the image is "much better" using that algorithm, shouldn't it>>>be completely obvious, rather than giving you just a feeling that it ... That, in my opinion, results ...
    (rec.photo.digital)
  • Re: difference btw H/W & S/W implementations
    ... you should repost, maybe in ... >Feeling really intelligent today.. ... >How do you say an algorithm is faster in one and slower in other.. ... David C. Ullrich ...
    (sci.crypt)