Potenzieren nur mit den Operatoren "+" und "-" in C

[Dimitrij]

Hallo,

ich soll in einer Übungsaufgabe für die Programmiersprache C eine frühere Rechenmaschine per Programm nachbilden. Sie kann nur addieren und subtrahieren. Wie mache ich das? Ich habe mich daran schon versucht komm aber jetzt nicht mehr vorwärts. Kann mir mal jemand von euch helfen? thx

[Senior Sanchez]

Hallo,

ich soll in einer Übungsaufgabe für die Programmiersprache C eine frühere Rechenmaschine per Programm nachbilden. Sie kann nur addieren und subtrahieren. Wie mache ich das? Ich habe mich daran schon versucht komm aber jetzt nicht mehr vorwärts. Kann mir mal jemand von euch helfen? thx

Naja, einfache Potenzen sind ja kein problem. 2 ^5 etwa kannste auch so formulieren:
2 +2 = 4
4 + 4 = 8
8 + 8 = 16
16 + 16 = 32

Man merkt, dass es im Grunde immer eine Addition der vorigen Summe mit sich selbst ist. Sprich in diesem Fall ist 2 ^ n = 2 ^ (n - 1) + 2 ^ (n - 1) bis n = 2.
Das ganze kannste jetzt leicht rekursiv durchkaspern und musst nur auf die Grenzen achten, sprich wenn n - 1 = 1 ist, so ist der rekursive Abstieg erreicht.

Schwieriger wirds natürlich bei Potenzen mit gebrochenem Exponenten usw. Vllt hilft dir das trotzdem weiter.

Wurzeln ließen sich btw im Grunde genau anders herum gestalten ;) Musst halt die Summe immer halbieren und da de dazu nich einfach durch 2 teilen darfst (oder?) kannste dir dafür auch noch was überlegen *gg*

[Dimitrij]

Naja das ist ja nur ein kleines Programm mit ca. 100 Programmzeilen. Ich denke mal das man da auf solche "Kleinigkeiten" nicht achten muss. Es ist ja nur ein Einführungsbeispiel über Funktionen in C. Noch eine Verständnisfrage, Rekursion is doch das wo sich die Funktion so oft wie benötigt selbst aufruft. Oder hab ich mir das von der Ausbildung falsch gemerkt? Das ist schon ein paar Jahre her, seitdem hab ich nicht mehr soviel mit C gemacht. Und etz im Studium kommt C wieder.

[Senior Sanchez]

Naja das ist ja nur ein kleines Programm mit ca. 100 Programmzeilen. Ich denke mal das man da auf solche "Kleinigkeiten" nicht achten muss. Es ist ja nur ein Einführungsbeispiel über Funktionen in C. Noch eine Verständnisfrage, Rekursion is doch das wo sich die Funktion so oft wie benötigt selbst aufruft. Oder hab ich mir das von der Ausbildung falsch gemerkt? Das ist schon ein paar Jahre her, seitdem hab ich nicht mehr soviel mit C gemacht. Und etz im Studium kommt C wieder.

Japs, genau. Rekursion meint eine Funktion oder ein Element das vollständig oder teilweise durch sich selbst beschrieben wird.

Hilft dir das soweit oder soll ichs noch in Pseudo-Code formulieren? Ich könnte dir nötigenfalls noch nen Java oder C++ Code basteln, aber C ist nicht meine Stärke *g*

[Coda]

Ehm Sanchez, das funktioniert aber nur mit 2^n

[Senior Sanchez]

Ehm Sanchez, das funktioniert aber nur mit 2^n

Ehm, ja, stimmt, habn detail übersehen.
Die Anzahl der Summanden entspricht der Ausgangsbasis *g*

Also bei 2 ist es (jetzt mal verkürzt geschrieben):

2 ^ n = 2 * (2 ^ (n - 1))
3 ^ n = 3 * (3 ^ (n - 1))
4 ^ n = 4 * (4 ^ (n - 1))

usw. *g*

Das Produkt kann man natürlich leicht in ne Addition umwandeln.

EDIT: Ich habs jetzt mal schnell in Java gehacked, wenn de es brauchst, sag Bescheid. Funktionierte bei mir auf Anhieb ;)

[Dimitrij]

Könntest du es mir schicken? Ich denk ich werde es dann schon so umsetzen können, dass es gültiger C Code ist. thx

[Senior Sanchez]

Ich hoffe es hilft.

public class Test {

private double start_basis = 0;

public Test(double start) {
this.start_basis = start;
}

public double potenz(double basis, double n) {
if(n - 1 == 0) {
return basis;
}

double summand = potenz(basis, n-1);
double sum = 0;
for(int i=0; i < start_basis; i++) {
sum += summand;
}

return sum;
}

public static void main(String[] args) {
double start = 3;
double exp = 9;
Test test = new Test(start);
System.out.println(test.potenz(start, exp));
}
}

[Trap]

Oder in rekursiv in Lisp:
(defun mult (x y)
(if (= y 0)
0
(+ x (mult x (1- y))))))
(defun pot (x y)
(if (= y 0)
1
(mult x (pot x (1- y)))))
Funktioniert für nicht allzu große Integer (stack overflow) und y>=0

@Senior Sanchez:
Double für den exponent und dann falsch lösen scheint mir nicht ganz geglückt, außerdem terminiert a^0 glaub ich nicht.

Edit: Fallunterscheidung bei Multiplikation hübscher gemacht

[Senior Sanchez]

Oder in rekursiv in Lisp:
(defun mult (x y)
(cond ((= y 0) 0)
((= y 1) x)
(t (+ x (mult x (1- y))))))
(defun pot (x y)
(if (= y 0)
1
(mult x (pot x (1- y)))))
Funktioniert für nicht allzu große Integer (stack overflow) und y>=0

@Senior Sanchez:
Double für den exponent und dann falsch lösen scheint mir nicht ganz geglückt, außerdem terminiert a^0 glaub ich nicht.

Die Verwendung von double ist da allgemein nicht glücklich, long wäre besser, denn bei gebrochenen Basen/Exponenten wirds schwierig ;)
Was meinst du mit falsch lösen?
a^0 terminiert nicht, das ist richtig, hatte ich jetzt in der Schnelle nicht bedacht. Ne zusätzliche Abfrage rein und das sollte gehen ;)

Ich hats halt auf die schnelle gemacht und nicht alle Grenzen abgesteckt, dass sollte die Aufgabe des Threaderstellers sein :tongue:


EDIT: etwas hübscher *g*

public class Test {

private long start_basis = 0;

public Test(long start) {
this.start_basis = start;
}

public static void main(String[] args) {
long start = 3;
long exp = 3;
Test test = new Test(start);
System.out.println(test.potenz(start, exp));
}

public long potenz(long basis, long n) {
if(n == 1) {
return basis;
}

if(n == 0) {
return 1;
}

long summand = potenz(basis, n-1);
long sum = 0;
for(int i=0; i < start_basis; i++) {
sum += summand;
}

return sum;
}

}

[HellHorse]

Oder in rekursiv in Lisp:
Bähh, das ist nicht tail-rekursiv!!!!11111einself :P

[Trap]

Bähh, das ist nicht tail-rekursiv!!!!11111einself :P
Richtig, das ist eine Übung für interessierte Leser ;)

[Senior Sanchez]

Richtig, das ist eine Übung für interessierte Leser ;)

Der Sourcecode war aber heute noch anders ;)

Ich versuche gerade mich da nen bissl reinzudenken, auch wenn ich lisp (noch) nicht kenne. Trotzdem komm ich da mit der Syntax nicht so ganz klar. Könnte einer von euch, Trap oder HellHorse vllt mal zeilenweise die Syntax erklären bzw. was das Programm dort genau macht? Ich meine, grob bekomme ich es ja hin, aber z.B. die Parameterübergabe an die Funktionen checke ich überhaupt nicht.


Und was ist einer nicht endständigen Rekursion (denke mal, dass das mit tail-rekursion gemeint ist ;) ) so schlimm? *g*

[Trap]

Syntax von Lisp ist primitiv:
(funktionsname arg1 arg2 arg3 ...)

if ist aber keine Funktion, sondern eine "special form". Beschrieben hier: http://www.lisp.org/HyperSpec/Body/speope_if.html

Endrekursion kann vom Compiler intern in Iteration umgewandelt werden und dann läuft es ohne zusätzlich Speicher auf dem Stack zu verbrauchen. Machen übrigens alle modernen Compiler, egal welche Sprache.

[Senior Sanchez]

Syntax von Lisp ist primitiv:
(funktionsname arg1 arg2 arg3 ...)

if ist aber keine Funktion, sondern eine "special form". Beschrieben hier: http://www.lisp.org/HyperSpec/Body/speope_if.html

Endrekursion kann vom Compiler intern in Iteration umgewandelt werden und dann läuft es ohne zusätzlich Speicher auf dem Stack zu verbrauchen. Machen übrigens alle modernen Compiler, egal welche Sprache.

Oha, danke für die Erklärung :)

jetzt musst du mir nur noch erklären warum du 1 - y machst und nicht y - 1.

Das mit der Rekursion hab ich gar net gewusst, danke für die Info :)

[Trap]

jetzt musst du mir nur noch erklären warum du 1 - y machst und nicht y - 1.
Die Funktion heißt 1-, es gibt auch 1+. Ist Vorgänger und Nachfolger. Sonst müsste ich schreiben (- y 1) und da brauch ich 1 Leerzeichen mehr ;)

[Senior Sanchez]

Die Funktion heißt 1-, es gibt auch 1+. Ist Vorgänger und Nachfolger. Sonst müsste ich schreiben (- y 1) und da brauch ich 1 Leerzeichen mehr ;)

Ach das ist ne Funktion? ui, da muss man aber aufpassen.
Ist praktisch nen Dekrement bzw. Inkrement, hm?
Dann isses natürlich klar und das du nen Leerzeichen sparen möchtest mehr als löblich. :uup: