hi, ich soll ein programm schreiben das arabische zahlen in römische zahlen umrechnet, dabei soll ich rekursiv vorgehen. kann mir da jemand helfen?
iterativ hab ich das hinbekommen, (das hat aber mindestens eine laufzeit von O(n^2) ca würd ich jetzt mal schätzen) nur weiß ich jetzt nicht wie ich diese iterative lösung in eine rekusive umwandeln kann. hier mein iterativer umrechner:
public class Roman {
static String toRoman(int n) {
String [] roman = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
int [] arab = {1,4,5,9,10,40,50,90,100,400,500,900,1000};
String Output ="";
for (int i = roman.length-1; i >= 0; i--) {
int times = n / arab[i];
for (int j = 1; j <= times; j++) {
Output = Output + roman[i];
}
n = n % arab[i];
}
return Output;
}
public static void main(String[] args) {
if (args.length==0) return;
int N = Integer.parseInt(args[0]);
System.out.println(toRoman(N));
}
}
danke schon mal im voraus!
1 Antwort
Ich hätte hierfür schon einen rekursiven Lösungsansatz.
Nach dem Prinzip:
Betrachtung der Dezimalzahl von links nach rechts:
Über die Zahl und dessen Exponent kann man auf die korrekten Buchstaben schließen:
z.B.:
Zahl: 314:
Ergibt:
3 * 10HOCH2 + 1 * 10HOCH1 + 4 * 10HOCH0
So kann man dieselbe Methode Aufrufen, und sich den Exponenten nach, "nach unten arbeiten".
Schritt 1: Ermittle Wert für 300. Reduziere Basiswert 314 um 300.
Schritt 2: Ermittle Wert für 10. Reduziere Basiswert 14 um 10.
Schritt 3: Ermittle Wert für 4. Reduziere Basiswert 4 um 4.
So würde meine Lösung mit Rekursion aussehen: