3
Wie, Division und Modulooperator nur mit Addition und Subtraktion in Java?
Die gesamte Aufgabenstellung lautet wie folgt:
Es soll die ganzzahlige Division und der Modulooperator nur mit Hilfe von
Addition und Subtraktion realisiert werden. Schreiben Sie dazu jeweils eine iterative und eine rekursive
Methode (DivIter, DivRek, ModIter und ModRek).
Was ich bis jetzt schon habe sind die Itterativen Lösungen zur Division und Mudolo. Diese sehen bei mir wie folgt aus:
Itterative Division mit + und * ------------------------------
static double DivIter (int x, int y){
int rest = x;
double erg = 0;
int nachkommaerg = 0;
int counter = 0;
while (rest >= y){
rest = rest - y;
erg = erg +1;
}
if (rest != 0){
while ((rest != 0)&(counter <= 15)){
counter++;
rest = rest *10;
while (rest >= y){
rest = rest - y;
nachkommaerg = nachkommaerg + 1;
}
erg = erg + nachkommaerg * Math.pow(10, counter * -1);//Damit werden die Nachkommastellen immer hintendran gehangen, bis Max 15, weil dann double zu Ende ist
nachkommaerg = 0;
}
}
return erg;
}
Itterative Mudolooperation ------------------------------
static int ModIter (int a, int b){
int rest = a;
int erg = 0;
if (a<b){
return a;
}else{
while (rest >= b){
rest = rest - b;
erg = erg +1;
}
return rest;
}
}
Meine Frage ist nun folgende:
Wie sieht die jeweilige rekursive Lösung aus?
Oder könnt ihr mir ein paar Hilfen geben wie man auf die Lösung kommt?
Hierzu noch:
Ich weiß, dass man das Problem auf ein kleineres reduziert und das dann wieder versucht mit der Rekusion zu lösen. z.B. Fibonaccizahl von 5 = Fibonaccizahl von 4 + Fibonaccizahl von 3.
freu mich auf viele gute Antworten
Mfg Shamaz
Itterative Division mit + und * ------------------------------
static double DivIter (int x, int y){
int rest = x;
double erg = 0;
int nachkommaerg = 0;
int counter = 0;
while (rest >= y){
rest = rest - y;
erg = erg +1;
}
if (rest != 0){
while ((rest != 0)&(counter <= 15)){
counter++;
rest = rest *10;
while (rest >= y){
rest = rest - y;
nachkommaerg = nachkommaerg + 1;
}
erg = erg + nachkommaerg * Math.pow(10, counter * -1);//Damit werden die Nachkommastellen immer hintendran gehangen, bis Max 15, weil dann double zu Ende ist
nachkommaerg = 0;
}
}
return erg;
}
Itterative Mudolooperation ------------------------------
static int ModIter (int a, int b){
int rest = a;
int erg = 0;
if (a<b){
return a;
}else{
while (rest >= b){
rest = rest - b;
erg = erg +1;
}
return rest;
}
}
Meine Frage ist nun folgende:
Wie sieht die jeweilige rekursive Lösung aus?
Oder könnt ihr mir ein paar Hilfen geben wie man auf die Lösung kommt?
Hierzu noch:
Ich weiß, dass man das Problem auf ein kleineres reduziert und das dann wieder versucht mit der Rekusion zu lösen. z.B. Fibonaccizahl von 5 = Fibonaccizahl von 4 + Fibonaccizahl von 3.
freu mich auf viele gute Antworten
Mfg Shamaz
Share on Facebook
Share on Twitter
Share on Reddit
Share on LinkedinPlease also mark the comments that contributed to the solution of the article
Content-Key: 133973
Url: https://administrator.de/contentid/133973
Printed on: April 26, 2024 at 02:04 o'clock
3 Comments
Latest comment
Hallo,
grob:
int div(divid, divis){
if(divid > divis)
return 1 + div(divid - divis, divis)
else
return 0
}
Also: wenn der der Divisor größer als der Divident ist (z.B. 4 : 5), dann 0 zurückgeben (4 ist nicht durch 5 teilbar). Wenn der Divident noch einmal reinpasst (z.B. 9 : 5), dann diese 1 "merken", und den Rest nochmal probieren zu teilen (und das Ergebnis davon zu dieser 1 addieren). Ich denke, daraus solltest du auch den Modulo-Operator herleiten können...
Gruß
Filipp
grob:
int div(divid, divis){
if(divid > divis)
return 1 + div(divid - divis, divis)
else
return 0
}
Also: wenn der der Divisor größer als der Divident ist (z.B. 4 : 5), dann 0 zurückgeben (4 ist nicht durch 5 teilbar). Wenn der Divident noch einmal reinpasst (z.B. 9 : 5), dann diese 1 "merken", und den Rest nochmal probieren zu teilen (und das Ergebnis davon zu dieser 1 addieren). Ich denke, daraus solltest du auch den Modulo-Operator herleiten können...
Gruß
Filipp
Also dein Vorschlag hat mich meinem Ziel schon einmal sehr nahe gebracht. Mein Quelltext sieht nun wie folgt für die rekursive Division aus:
static double DivRek(double a, double b){
String s = new String ();
if(a == 0){
return 0;
}else{
if (a >= b){
s = s + (1 + DivRek(a - b, b));
return Double.valueOf(s).doubleValue();
}else{
a = a * 10;
return (DivRek (a,b))* Math.pow(10, -1);
}
}
}
den kleinen Trick mit dem String mache ich damit auch die Nachkommastellen immer schön hinten drann gehangen werden. Also, so wie man es auch mit Stift und Papier macht. Wie ich jetzt nochmal auf das math.pow Zeug gekommen bin,weiß ich gearde mal selber nicht mehr. aber es geht.
Jetzt gibt es leider nur noch das Problem mit dem Beenden. Wenn ich für a=1 und b=3 einsetzte, dann ist dies ja ein unendlicher Bruch. Also 0.3333333333333333333... das erzeugt dann auch dierekt nach 16 Durchläufen (das was eine double Variable aufnehmen kann) einen "java.lang.StackOverflowError"
Bei meiner itterativen Lösung verwende ich einen Zähler, der dann halt nach dem 15ten Mal die Sache zum Abbruch bringt. Bei meiner rekursiven Methode kann ich solch einen aber nicht verwenden, weil ich als Rückgabewert den Rest liefere.
Mein Lösungsgedanke ich jetzt, dass ich den "java.lang.StackOverflowError" mit "Try, catch " abfange und dann die Zahl ausgeben lasse.
Leider habe ich mit Fehlersituationen noch nicht befasst und weiß nicht wie ich das bewekstelligen soll.
Deshalb frage ich jetzt nach einer Möglichkeit das zu beheben, wenn überhaupt geht?
static double DivRek(double a, double b){
String s = new String ();
if(a == 0){
return 0;
}else{
if (a >= b){
s = s + (1 + DivRek(a - b, b));
return Double.valueOf(s).doubleValue();
}else{
a = a * 10;
return (DivRek (a,b))* Math.pow(10, -1);
}
}
}
den kleinen Trick mit dem String mache ich damit auch die Nachkommastellen immer schön hinten drann gehangen werden. Also, so wie man es auch mit Stift und Papier macht. Wie ich jetzt nochmal auf das math.pow Zeug gekommen bin,weiß ich gearde mal selber nicht mehr. aber es geht.
Jetzt gibt es leider nur noch das Problem mit dem Beenden. Wenn ich für a=1 und b=3 einsetzte, dann ist dies ja ein unendlicher Bruch. Also 0.3333333333333333333... das erzeugt dann auch dierekt nach 16 Durchläufen (das was eine double Variable aufnehmen kann) einen "java.lang.StackOverflowError"
Bei meiner itterativen Lösung verwende ich einen Zähler, der dann halt nach dem 15ten Mal die Sache zum Abbruch bringt. Bei meiner rekursiven Methode kann ich solch einen aber nicht verwenden, weil ich als Rückgabewert den Rest liefere.
Mein Lösungsgedanke ich jetzt, dass ich den "java.lang.StackOverflowError" mit "Try, catch " abfange und dann die Zahl ausgeben lasse.
Leider habe ich mit Fehlersituationen noch nicht befasst und weiß nicht wie ich das bewekstelligen soll.
Deshalb frage ich jetzt nach einer Möglichkeit das zu beheben, wenn überhaupt geht?
Soo, da niemand weiter auf diesen Beitrag hin antwortet und mein Abgabetermien schon lange vorbei ist, poste ich hier mal die Lösung die ich abgegeben habe.
An dieser stelle sei gesagt, das dieser Quelltext von jedem verwendet werden kann wer will. Was ihr, du damit macht ist mir egal... außer natürlich es stellt sich heraus, das man damit ne Unmenge an Geld machen kann, dann will ich auch was davon
.
So da isser endlich:
Wenn jemand natürlich noch weiter mit mir über ne richtige Lösung diskutieren will, der kann das gerne tun. Denn zur Zeit ist es so, dass je nachdem welche Zahl in die Rekursive Division übergeben wird, kann es sein, z.B. bei 1/3, dass eine NullPointerExeption geschmissen wird, weil der Algorythmus nie zum Ende kommt.
Mfg Shamaz
An dieser stelle sei gesagt, das dieser Quelltext von jedem verwendet werden kann wer will. Was ihr, du damit macht ist mir egal... außer natürlich es stellt sich heraus, das man damit ne Unmenge an Geld machen kann, dann will ich auch was davon
.So da isser endlich:
static double DivIter (int x, int y){
int rest = x;
double erg = 0;
int nachkommaerg = 0;
int counter = 0;
while (rest >= y){
rest -= y;//rest = rest -b, steht da eigentlich
erg = erg +1;
}
if (rest != 0){
while ((rest != 0)&(counter <= 15)){
counter++;
rest = rest *10;
while (rest >= y){
rest -= y;
nachkommaerg = nachkommaerg + 1;
}
erg = erg + nachkommaerg * Math.pow(10, counter * -1);
nachkommaerg = 0;
}
}
return erg;
}
static double DivRek(double a, double b, int counter){
String s = new String ();
--counter;
if (counter == 0){return 0;
}else {
if(a == 0){
return 0;
}else{
if (a >= b){
s = s + (1 + DivRek(a - b, b, counter));
return Double.valueOf(s).doubleValue();
}else{
a = a * 10;
return (DivRek (a,b,counter))* Math.pow(10, -1);
}
}
}
}
static int ModRek (int a, int b){
if (a>=b)
return ModRek (a-b,b);
else
return a;
}
static int ModIter (int a, int b){
int rest = a;
int erg = 0;
if (a<b){
return a;
}else{
while (rest >= b){
rest -= b;
erg += 1;
}
return rest;
}
}
Wenn jemand natürlich noch weiter mit mir über ne richtige Lösung diskutieren will, der kann das gerne tun. Denn zur Zeit ist es so, dass je nachdem welche Zahl in die Rekursive Division übergeben wird, kann es sein, z.B. bei 1/3, dass eine NullPointerExeption geschmissen wird, weil der Algorythmus nie zum Ende kommt.
Mfg Shamaz
