Converting a number to its roman numerals is a teasy problem for beginner programmers in any language.
The problem : A number can be converted to roman number if, N <= 3999. The roman numerals are M => 1000, D => 500, C => 100, L => 50, X => 10, V => 5, I => 1.
The roman numeral form of 3999 is MMMCMXCIX. In roman conversion we can have 3 of a kind like MMM or CCC or XXX but never 4 of that kind. We assign values like 900 a conversion by prefixing C with M which actually subtracts. On the same lines,
100 prefixes 500 to get 400(CD),
10 precedes 100 to get 90(XC),
10 precedes 50 to get 40(XL),
1 precedes 10 to get 9 (IX),
1 precedes 5 to get 4(IV).
This problem can be solved by a top down greedy approach by comparing N with each value k from 1000 down to 1 including the prefixed values, [900, 400, 90, 40, 9, 4], printing [N/k] times the mapped string and after each iteration retaining N%k.
For 3999 => 3*1000 + 1*900 + 1*90 + 1*9
Iteration 1: N = 3999, k = 1000, printed = [3999/1000] of "M"; 3999 %= 1000
Iteration 2: N = 999, k = 900, printed = [999/900] of "CM"; 999 %= 900
Iteration 3: N = 99, k = 500, N < k, next;
Iteration 4: N = 99, k = 400, N < k, next;
Iteration 5, N = 99, k = 100, N < k, next;
Iteration 6: N = 99, k = 90, printed = [99/90] of "XC"; 99 %= 90
Iteration 7: N = 9, k = 50, N < k, next;
Iteration 8: N = 9, k = 40, N < k, next;
Iteration 9: N = 9, k = 10, N < k, next;
Iteration 10: N = 9, k = 9, printed = [9/9] of "IX"; 9 %= 9
Iteration 11: N =0 ; stop;
Check out a sample implementation in C.
Solution:
#include "stdio.h"
#define MAX 80
struct Roman
{
int value;
char str[3];
} pairs[] =
{
{1000,"M" },
{900, "CM"},
{500, "D" },
{400, "CD"},
{100, "C" },
{90, "XC"},
{50, "L",},
{40, "XL"},
{10, "X" },
{9, "IX"},
{5, "V" },
{4, "IV"},
{1, "I" }
};
int main()
{
int n = 0;
int err = 0;
int i;
int j;
char line[MAX];
do
{
fprintf(stdout, "Enter your number to be displayed as words:");
fgets(line, MAX, stdin);
err = sscanf(line, "%d", &n);
} while (err < 1 || n > 3999);
for (i = 0; i < sizeof(pairs)/sizeof(*pairs); i++)
{
if (n >= pairs[i].value)
{
for (j = 0; j < n/pairs[i].value; j++)
printf("%s", pairs[i].str);
n %= pairs[i].value;
}
if (n == 0) break;
}
}
