Blatt 2

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Blatt 2
Hey Leute,
kurze Frage zur Aufgabe 3: darf man davon ausgehen, dass n kleiner als B ist, weil sonst wird es ja schwer k zu berechnen, weil mein n ja dann keine Ziffer mehr ist, oder sehe ich das falsch?


n ist hier die Anzahl an Ziffern, und somit immer mindestens 1. (Frage missverstanden.)


ja n ist mindestens 1 aber darf man eine obergrenze annehmen?


Ah sorry, ich hab dich falsch verstanden.
Aber nein, du darfst keine Obergrenze für n annehmen. Wofür auch, was ist bitte dein k?

btw: Soweit ich das in der Vorlesung richtig verstanden habe, ist ein Vergleich wie z.B. if (n==1) ... zulässig und kostet noch nicht einmal eine Operation :wink: (falls es das ist worauf du raus willst).


Mm ja das hat sich jetzt geklärt ich hatte da einen Denkfehler. Jetzt hab ich aber trotzdem noch kurz ne Frage: Auf dem ersten Übungsblatt hab ich das bei der Aufgabe 1 so verstanden, dass mein q nicht wieder zur Basis B dargestellt werden muss…
Also wenn B=3, und x=10, dann hätte ich gesagt, dass halve(10)=(5,0) sein muss ist das so richtig?


Also für B=3 und x=10 gilt
halve(10)=(1,1) wegen 2+1=10


da hätte man ja aber wohl auch dazuschreiben können, dass das do gemeint ist!


Wie denn sonst?

1 „Gefällt mir“

ich hatte auf dem letzten übungsblatt das immer so interpretiert: halve(10)=(5,0) egal zu welcher basis, weil eben nicht dasteht, dass q wieder zur basis B gesehen wird.
Heißt das dann bei 444 zur Basis 5 würde ich also (62,0) zurückgeben oder etwas anderes?


Edit: vllt Denkfehler
Edit zurueck, kein Denkfehler.

halve_5(444) = (222,0).
Und wie bekommst du eine Ziffer 6 zur Basis 5?

Edit2: Wie man drauf kommt, steht hier.


Danke, das hat mir schonmal geholfen.

Jetzt habe ich noch bei AUfgabe 3 eine Frage zu der Induktion. Ich habe in der Rekurrenzgleichung wieder Aufrufe drinnen stehen wie T(n/2) wobei das n/2 zum Beispiel abgerundest sein soll.
Wenn ich jetzt einen geschlossenen AUsdruck erzeugen soll, geht das ja irgendwie nicht so schön … soll man dann einfach für n=2^k setzen? Und die obere Laufzeit dann dadurch abschätzen, dass ich immer n<=2^k hab, und statt Induktion über n das dann für Induktion über k zeige?


Auch auf die Gefahr hin hier mild belächelt zu werden:

Ich habe bei Aufgabe 3.1 anscheinend ein grundlegendes Problem:

Wenn z.b. Basis 10 nehme und meine Ziffer 1234567890 aufteile, erhalte ich ja

110⁹+210⁸+310⁷+410⁶+510⁵+610⁴+710³+810²+910¹+010⁰ oder?

Jedoch erschließt sich mir nicht, wie ich anschließend mit dem Rest von halve umgehen muss, da ich für das Ergebnis 617283945 aus 110⁹+210⁸ eine 6 erzeugen muss :frowning:

Wäre super wenn mir jemand sagen könnte, wo der Denkfehler liegt


Den Rest musst man mit den folgenden Ergebnissen verrechnen,
was offensichtlich erst beim Merge-Vorgang funktioniert.

Edit: Ich nehme an, dass die Lösung der Aufgabe 3) ebenfalls in Pseudocode verfasst werden soll?


Mir will allerdings auch nach einigen Überlegungen der Sinn hinter dem geforderten Divide-&-Conquer verfahren nicht recht einleuchten:

Wir erhalten als Eingabe einen “Vektor”, bei dem wir auf jede Ziffer einzeln zugreifen können… da macht divide-&-Conquer nur Sinn, wenn man den Code parallel ausführen möchte.

Wollen wir hier allerdings offensichtlich nicht, da bei der Umsetzung des Verfahrens zu viele Freiheiten gegeben sind.
Ursprünglich hatte ich die Implementierung auf parallelität ausgelegt, die halve_B aufrufe dann jedoch aufgrund von Performancegründen in die halve() reingezogen, da dort die nachträglichen Add-Aufrufe eingespart werden.
Zählt das denn nun noch als Divide-&-Conquer? Das Problem wurde in kleinstmögliche Teile unterteilt, macht nur nicht mehr viel Sinn.


Hallo zusammen,

ich stehe bei der Aufgabe 3 ehrlich gesagt auch noch etwas auf dem Schlauch. Mir ist klar, wie ich das rekursiv aufbauen muss, aber mir fehlt die Idee, wie ich die letzten k und die ersten n-k Stellen getrennt als eine Zahl zu behandeln habe. Ich kann auf die einzelnen Ziffern zugreifen, klar, und mir Horner könnte ich mir daraus auch wieder eine Zahl basteln, aber das ist ja nicht der Sinn. Wie muss ich da vorgehen?
Bin für jeden Tipp dankbar!