Problem
Römische Zahlen verwenden die Zeichen I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 und M = 1000. Die Zeichen werden vom größten zum kleinsten geschrieben und addiert, mit Ausnahme von sechs Subtraktionspaaren: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 und CM = 900. Wandle n in die übliche Schreibweise um. Sie verwendet immer ein Subtraktionspaar statt vier gleicher Zeichen hintereinander (4 ist IV, niemals IIII).
Implementiere integer_to_roman(n).
Eingabe
n: Die umzuwandelnde Zahl.
Ausgabe
Gib die römische Zahl als String aus Großbuchstaben zurück.
Einschränkungen
1 ≤ n ≤ 3999
Beispiele
Eingabe:
n = 1994
Erwartete Ausgabe:
expected = "MCMXCIV"
Eingabe:
long long n = 1994;
Erwartete Ausgabe:
std::string expected = "MCMXCIV";
Eingabe:
long n = 1994;
Erwartete Ausgabe:
string expected = "MCMXCIV";
Erläuterung
1000 + 900 + 90 + 4 ergibt M, CM, XC, IV: "MCMXCIV".
Eingabe:
n = 58
Erwartete Ausgabe:
expected = "LVIII"
Eingabe:
long long n = 58;
Erwartete Ausgabe:
std::string expected = "LVIII";
Eingabe:
long n = 58;
Erwartete Ausgabe:
string expected = "LVIII";
Erläuterung
50 + 5 + 3 ergibt L, V, III: "LVIII".
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Schreibe die Zeichen und die sechs Subtraktionspaare gemeinsam in eine nach Wert sortierte Liste.
Hinweis 2
Nimm immer wieder den größten Wert, der noch in den Rest passt.
Hinweis 3
Rechne 4, 9 und 3999 von Hand nach, um deine Tabelle zu prüfen.
Erwartete Komplexität
Zeit O(1), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.