13 schwere Kurzfragen

[volkard]

wo sind die türme von hanoi rekursiv?

[CStoll]

verschiebe(n,von,nach,über):
  verschiebe(n-1,von,über,nach)
  setze_stein(von,nach)
  verschiebe(n-1,über,nach,von)

Ist dir das nicht rekursiv genug?

[Pellaeon]

die Türmchen gibts in beiden Varianten, rekursiv und iterativ

[volkard]

CStoll schrieb:

verschiebe(n,von,nach,über):
  verschiebe(n-1,von,über,nach)
  setze_stein(von,nach)
  verschiebe(n-1,über,nach,von)

Ist dir das nicht rekursiv genug?

also gibt es einen algorithmus, der die türme von hanoi löst und der rekursiv ist. ich finde das rätsel leichter iterativ lösbar. sind deshalb die türme von hanoi rekursiv?

[CStoll]

Und wie sieht die iterative Lösung aus?
(btw, ein Problem ist weder iterativ noch rekursiv - erst eine mögliche Lösung kannst du entsprechend einordnen)

[volkard]

CStoll schrieb:

Und wie sieht die iterative Lösung aus?
(btw, ein Problem ist weder iterativ noch rekursiv - erst eine mögliche Lösung kannst du entsprechend einordnen)

//zielRichtung ist die richtung vom startturm zum zielturm
if(istUngeradeGerade(anzahlDerTürme))
 richtung:=zielRichtung
else
 richtung:=dieAndereRichtung(zielRichtung)
zieh die kleine scheibe zykisch nach richtung
solange nicht fertig
 zieh den einzig möglichen zug, der nicht die kleine scheibe benutzt
 zieh den kleinsten zykisch nach richtung

hab aber auch schon lehrbücher gesehen, in denen stand expizit drin "die türme von hanoi lassen sich nicht iterativ lösen."

edit: zum testen http://www.mazeworks.com/hanoi/index.htm

[volkard]

CStoll schrieb:

Und wie sieht die iterative Lösung aus?
(btw, ein Problem ist weder iterativ noch rekursiv - erst eine mögliche Lösung kannst du entsprechend einordnen)

auch wenn ich in der problemstellung eine rekursive definition benutze?

[finix]

volkard schrieb:

CStoll schrieb:

Und wie sieht die iterative Lösung aus?
(btw, ein Problem ist weder iterativ noch rekursiv - erst eine mögliche Lösung kannst du entsprechend einordnen)

auch wenn ich in der problemstellung eine rekursive definition benutze?

Wenn du dir daraufhin die Problemstellung nochmal iterativ verdeutlichst - hast du dann ein anderes Problem beschrieben?

[volkard]

finix schrieb:

Wenn du dir daraufhin die Problemstellung nochmal iterativ verdeutlichst - hast du dann ein anderes Problem beschrieben?

nicht, wenn es trotz der anderen beschreibung das gleiche problem ist.

also gehe ich mal von einem problem aus, das man nicht ohne rekursion beschreiben kann.

[hmmmmmm]

Wann kommen denn eigentlich die schweren Kurzfragen?

[CStoll]

hab aber auch schon lehrbücher gesehen, in denen stand expizit drin "die türme von hanoi lassen sich nicht iterativ lösen."

Also so eine Aussage wäre auch unsinnig - man kann JEDE Rekursion in eine Iteration umwandeln (notfalls indem man die rekursiven Aufrufe durch einen eigenen Rechenstack nachbildet).

volkard schrieb:

auch wenn ich in der problemstellung eine rekursive definition benutze?

Für was für ein Problem willst du denn eine rekursive Beschreibung nutzen? (Ein Problem schreibt man normalerweise in der Form "ich habe A und will B erreichen - was muß ich tun?" - wenn du an der Stelle schon über Rekursion nachdenkst, machst du etwas falsch)

[7H3 N4C3R]

CStoll schrieb:

Also so eine Aussage wäre auch unsinnig - man kann JEDE Rekursion in eine Iteration umwandeln (notfalls indem man die rekursiven Aufrufe durch einen eigenen Rechenstack nachbildet).

Dann werf ich einfach mal die Ackermann- oder Ulam-Funktion in den Raum ^^

Die Türme ließen sich afaik durch Permutationsbildung iterativ lösen. Mein Prof hatte mal ein Programm, dass das machte. Es geht auf jeden Fall.

[volkard]

CStoll schrieb:

hab aber auch schon lehrbücher gesehen, in denen stand expizit drin "die türme von hanoi lassen sich nicht iterativ lösen."

Also so eine Aussage wäre auch unsinnig - man kann JEDE Rekursion in eine Iteration umwandeln (notfalls indem man die rekursiven Aufrufe durch einen eigenen Rechenstack nachbildet).

das gilt nicht. gemeint war, daß es iterartiv nicht gehe, außer mit dem notfall-trick.

[volkard]

CStoll schrieb:

volkard schrieb:

auch wenn ich in der problemstellung eine rekursive definition benutze?

Für was für ein Problem willst du denn eine rekursive Beschreibung nutzen? (Ein Problem schreibt man normalerweise in der Form "ich habe A und will B erreichen - was muß ich tun?" - wenn du an der Stelle schon über Rekursion nachdenkst, machst du etwas falsch)

du sagst mir gerade, daß ich was falsch mache, nur weil ich mehr sachen kenne? respekt!

ich denke konkret an eine rekursive definition im buch über formale begriffsanalyse von wille und ganter. die war wirklich happig und da wäre es kein fehler, davon auszugehen, daß man iterartiv keinen ordentlichen zugang hat. das buch liegt mir im moment nicht vor und ich kann nicht nachblättern.

denken wir und erstmal ganz einfach die definition "ein elefant ist jemand, dessen beide eltern elefanten sind". das ist nicht irgend eine eine lösungsstrategie für die frage, ob jemand ein elefant ist, sondern es ist die definition. aber die läßt sich jetzt von eventuellen problemstellungen abkoppeln. daher denke ich weiter daran, die problemstellung (evtl ein wenig hintertückisch) miteinzubeziehen wie im berühmten "was ist die größte zahl, die sich nicht mit worten darstellen läßt?" (eine wort-darstellung einer zahl ist "die größte zahl, die sich nicht mit worten darstellen läßt" und schnell wird's absurd, was aber nix an der problemstellung ändert).

[templäd]

Hallo,

Volkard meinte der Zeiger auf eine nicht Klassenmethode ist 2/3 mal so groß wie ein Zeiger auf eine "normale" Funktion.
Ich dachte das wäre ein ganz normaler Zeiger auf eine Funktion, die quasi implizit den this-Pointer als Parameter mitbekommt. Lass mich gerne belehren.

[Bashar]

volkard schrieb:

das gilt nicht. gemeint war, daß es iterartiv nicht gehe, außer mit dem notfall-trick.

Kann man immer unterscheiden, ob ein Algorithmus diesen "Trick", auch verschleiert, anwendet oder "echt iterativ" ist?

[camper]

1. Wieviel Speicherplatz belegt ein Zeiger bei einem 32-Bit breiten Adressbus?

fangfrage: der 80286 hat einen 24bit breiten datenbus, das heisst noch lange nicht, dass pointer dort 24bit breit sind. und ein far-pointer auf x86 32bit architektur hat 48 bit.
@volkard: standard-konforme pointer auf member-funktionen sind immer gleich gross, dass visual c++ hier unterschiede macht, ist eine proprietäre erweiterung). das ergibt sich einfach darsu, dass ein reinterpret_cast zu einem beliebeigen anderen pointer auf memberfunktion und zurück den ursprünglichen pointer ergeben muss.

9. Beschreiben SIe drei Möglichkeiten Ergebniswerte einer Funktion an das aufrufende Programm zurückzugeben. Je ein Beisp.

möglicherweise sind hier mechanismen gemeint: also per-value als funktionswert, per-referenz (mittels referenz oder pointer) über funktionsparameter, per exception. könnte aber auch anders gemeint sein.

[volkard]

camper schrieb:

@volkard: standard-konforme pointer auf member-funktionen sind immer gleich gross, dass visual c++ hier unterschiede macht, ist eine proprietäre erweiterung).

ich meinte nicht einen zusatztrick des msvc, sondern 2*sizeof(void*) bzw 3*sizeof(void*) weil verschiedene compiler das verschieden implementieren.

kann natürlich auch jede andere größe sein, aber ich hab bisher nur diese beiden größen angetroffen.

[eigeninitiative]

is ja toll, dass ihr jetzt schon für faule Säcke die Hausaufgaben macht

[volkard]

eigeninitiative schrieb:

is ja toll, dass ihr jetzt schon für faule Säcke die Hausaufgaben macht

du kannst gerne formblatt 17a ausfüllen und an marc++us schicken und damit beantragen, daß wie deine hausaufgaben nicht machen.