Help me with an algorithm please?

Help me with an algorithm that takes a number and converts it into roman numeral?





hey guys i need help on how to make a program that reads an input number between 1000~3000 and gives you its roman numeral in the console. I have been really having trouble figuring out an algorithm for this. If any of you have tips I'd greatly appreciate it. I know this is really not a math question, but i posted this question in programming %26amp; design and got no responses. My second best option was to post in math.





this is similar to what i have to make...





http://www.ivtech.com/roman/





(also, i use dev c++ 4)

Help me with an algorithm please?
One way would be to break the number down to its digits.





thousands, hundreds, tens, units





For thousands map as follows:


1 --%26gt; M


2 --%26gt; MM


3 --%26gt; MMM





For hundreds map as follows:


0 --%26gt; nothing


1 --%26gt; C


2 --%26gt; CC


3 --%26gt; CCC


4 --%26gt; CD


5 --%26gt; D


6 --%26gt; DC


7 --%26gt; DCC


8 --%26gt; DCCC


9 --%26gt; CM





Tens:


0 --%26gt; nothing


1 --%26gt; X


2 --%26gt; XX


3 --%26gt; XXX


4 --%26gt; XL


5 --%26gt; L


6 --%26gt; LX


7 --%26gt; LXX


8 --%26gt; LXXX


9 --%26gt; XC





Units:


0 --%26gt; nothing


1 --%26gt; I


2 --%26gt; II


3 --%26gt; III


4 --%26gt; IV


5 --%26gt; V


6 --%26gt; VI


7 --%26gt; VII


8 --%26gt; VIII


9 --%26gt; IX





That's rather inelegant. You could improve it by having an array of the roman numerals (IVXLCDM) and using some logic to generate each of these strings (rather than a big lookup).





Let's imagine you had an array of letters


aLetter[] = "IVXLCDM"





And you had a function that would take the following arguments:


nPlace (0 = units (10^0), 1 = tens (10^1), 2 = hundreds (10^2), 3 = thousdands (10^3).


nValue (0 to 9 representing that digit)





The nPlace value corresponds to an offset.





// Get the array offsets.


nOffset = 2*nPlace;





// The main logic would be something like the following pseudo-code


switch (nValue)


case 0,1,2,3:


// get aLetters[nOffset] and repeat it nValue times


// Generates I, II, III or X, XX, XXX or C, CC, CCC depending on the offset.


break;


case 4:


// get the characters at aLetters[nOffset] and aLetters[nOffset + 1]


// Generates IV, XC or CD


break;


case 5, 6, 7, 8:


// get aLetters[nOffset+1] and follow by


// aLetters[nOffset] repeated (nValue-5) times,


// Generates V, VI, VII, VIII or L, LX, LXX, LXXX or D, DC, DCC or DCCC


break;


case 9:


// get aLetters[nOffset] followed by aLetters[nOffset+2]


// Generates IX, XC or CM


break;
Reply:There are different ways you could do this. One algorithm that's somwhat short is something like:





- Input N


- Break this up into a 4-digit array from left to right, n[0], n[1], n[2], n[3] (where there are leading zeroes if necessary, so that n[0] = 0 if it's not a 4-digit number, etc.)


- Make another array called "numerals" with the values {"M", "D", "C", "L", "X", "V", "I"}


- Now loop through each digit as follows:





for i = 0 to n[0]


print "M"


next i





for i = 1 to 3


{


Let N = n[i]


If N = 1, print numeral[i+1] once


If N = 2, print numeral[i+1] twice


If N = 3, print numeral[i+1] thrice


If N = 4, print numeral[i+1] once followed by numeral[i]





For N between 5 and 10, repeat the above, only shift up to using numeral[i+2] and numeral[i+1]. You can use a modulus "%5" command to deal with this


}
Reply:Here is a complete working code (Pascal), You can easily convert to whatever algorithmic language You wish, I'll use . . . as placeholders, marking the indents, because Yahoo Answers trims all leading spaces from text lines.





function ArabicToRoman(Y:integer):string;





const Factors:array[1..3] of integer = (100, 10, 1);


const WholeRangeChars:array[1..3] of char = ('M', 'C', 'X');


const HalfRangeChars: array[1..3] of char = ('D', 'L', 'V');


const PrefixChars:array[1..3] of char = ('C', 'X', 'I');


var i:integer;





begin Y:=abs(Y); // no negative input values allowed


// but no need to be necessarily in 1000..3000 bounds


Result:=''; // null string


for i:=1 to 3 do begin


. . . while Y %26gt;= 10*Factors[i] do


. . . . . . . . begin Result:=Result + WholeRangeChars[i];


. . . . . . . . . . . . . decrement(Y, 10*Factors[i]) end;


. . . if Y %26gt;= 9*Factors[i] then


. . . . . begin Result:=Result + PrefixChars[i] + WholeRangeChars[i];


. . . . . . . . . . decrement(Y, 9*Factors[i]); end


. . . else if Y %26gt;= 5*Factors[i] then


. . . . . begin Result:=Result + HalfRangeChars[i];


. . . . . . . . . . decrement(Y, 5*Factors[i]); end


. . . else if Y %26gt;= 4*Factors[i] then


. . . . . begin Result:=Result + PrefixChars[i] + HalfRangeChars[i];


. . . . . . . . . . decrement(Y, 4*Factors[i]) end;


end; // for i


while Y %26gt;= 1 do begin Result:=Result + 'I'; decrement(Y) end;


end; // Arabic =%26gt; Roman
Reply:I am not going to get into the code specifics, but here is the logic I would use


First, count the digits of input; (limit 4 digits, being 3000)


add exclusions for range greater than 3000 and null entry





for 4 digits


{do this


go to 3 digit function


set great digits yes}





for 3 digits


{if hundreds-value=0 proceed to 2, else continue, do this, append to output if greater digits 'yes', proceed to 2 digits}





for 2 digits


if { tens-value=0 proceed to 1, else continue, do this function, append to output if greater digits 'yes', proceed to 1 digit}





for 1 digit


{ if units-value=0 print the buffer, else continue, do this function, append to output if greater digits 'yes', print result}





"do this function" (above) will basically be assigning a roman numeral as a result of a table lookup function


the reason for breaking it out is that the 4 digits will use M, MM, or MMM for their output, whilst 3digits will use CM, DCCC, DCC, DC, D, CD, CCC, CC, C for their function output, and 2digits would use ... etc etc you get the idea





Doing it backwards instead of forwards means you don't have to append blanks to the output





Hope this helps,


Good Luck

flowers on line