Teile-und-herrsche Prinzip

Aufrufe: 804     Aktiv: 13.11.2020 um 14:41
0

Hallo zusammen

 

Den ersten Schrit habe ich gemacht, return (A,1,3) * (A, 3+1, 8) -> (A,1,3) * (A,4,8) = Wie kann ich die beiden multiplizieren, die Unterscheiden sich ja. Im ersten ist (A,l,q) und der zweite von der Multiplikation ist (A,q+1,r). Wie berechnet machen dies?

 

 

Vielen Dank für eure Hilfe!

 

Schöne Grüsse

Sayuri

 

Diese Frage melden
gefragt

Student, Punkte: 205

 
Kommentar schreiben
2 Antworten
1

Ich bin dabei leider kein Experte, aber das sieht mir sehr nach einem informatischen Problem aus. Eventuell stellst du die Frage auf informatikfragen.de

Diese Antwort melden
geantwortet

Student, Punkte: 101

 
oh danke!   ─   sayuri 08.11.2020 um 12:35

Kommentar schreiben

1

Es handelt sich hierbei um einen rekursiv definierten Algorithmus, d.h. du musst hier den Algorithmus so lange immer wieder aufrufen, bis nur noch Zahlen dastehen, die man multiplizieren kann.

Übrigens hast du in deiner Berechnung einen kleinen Fehler bei der unteren Gaußklammer gemacht. Es ist \( \lfloor \frac{7}{4} \rfloor = 1 \).

Diese Antwort melden
geantwortet

Student, Punkte: 7.02K

 
Was hier passiert ist folgendes: \( UN(A,1,8) \) \( = UN(A,1,2) \cdot UN(A,3,8) \) \( = ( UN(A,1,1) \cdot UN(A,2,2) ) \cdot ( UN(A,3,4) \cdot UN(5,8) ) \) \( = (6 \cdot 4) \cdot ( ( UN(A,3,3) \cdot UN(A,4,4) ) \cdot ( UN(5,5) \cdot UN(6,8) ) ) \) \( = 24 \cdot ( (2 \cdot 9) \cdot ( 2 \cdot ( UN(A,6,6) \cdot UN(A,7,8) ) ) ) \) \( = 24 \cdot ( 18 \cdot ( 2 \cdot ( 8 \cdot ( UN(A,7,7) \cdot UN(A,8,8) ) ) ) ) \) \( = 24 \cdot ( 18 \cdot ( 2 \cdot ( 8 \cdot ( 7 \cdot 5 ) ) ) ) \) \( = 24 \cdot ( 18 \cdot ( 2 \cdot ( 8 \cdot 35 ) ) ) \) \( = 24 \cdot ( 18 \cdot (2 \cdot 280) ) \) \( = 24 \cdot ( 18 \cdot 560 ) \) \( = 24 \cdot 10 \ 080 = 241 \ 920 \) (Ich hoffe, ich hab mich nicht irgendwo vertan. Aber das Prinzip sollte damit klar sein).   ─   42 08.11.2020 um 13:05
vielen Dank, aber ist es nicht bei meiner Berechnung 7/4 = 1,75 + 1 = 2.75 aufgerundet = 3? Warum ist es 1? Warum ist es A,1,8 gleich A,1,2 * A,3,8?   ─   sayuri 08.11.2020 um 14:02
\( \lfloor \cdot \rfloor \) ist die untere Gaußklammer. Das bedeutet immer abrunden, also \( \lfloor \frac{7}{4} \rfloor = \lfloor 1,75 \rfloor = 1 \).   ─   42 08.11.2020 um 15:50
Vielen Dank!   ─   sayuri 09.11.2020 um 09:44
Sorry, könntest du mir noch erklären warum UN(A,1,8) = UN(A,1,2) * (A,3,8), dieser Teil ist mir klar, aber danach verstehe ich es nicht ganz = UN(A,1,1) * UN(A,2,2) * UN(A,3,4) * UN(5,8) (6 *4)? Warum (6 * 4)? Woher kommt diese Zahl? Könntest du mir die rekursive Funktion erklären, verstehe es immer noch nicht ganz! :(   ─   sayuri 09.11.2020 um 09:48
Allgemein tritt bei \( UN(A,n,n) \) ja der Fall "if \( l=r \)" ein und der Algorithmus gibt \( A[n] \) aus. Für das konkrete Array bedeutet das \( UN(A,1,1)= A[1] = 6 \) und \( UN(A,2,2) = A[2] = 4 \).
Der Algorithmus funktioniert eigentlich ganz leicht. Wenn \( l=r \) ist, dann gibt er \( A[n] \) zurück. Ansonsten teilt er sich die Aufgabe auf (deshalb auch "teile und herrsche") und ruft sich für diese Teile erneut auf. Das Ziel des Algorithmus ist es, das Produkt aller Array-Einträge zurückzugeben.   ─   42 09.11.2020 um 10:54
Also, dann muss ich solange return UN(A, l, q) * UN(A, q+1, l) durchführen bis es l = r entspricht?   ─   sayuri 09.11.2020 um 11:14
Ja, du musst den Algorithmus so lange durchführen, bis er einen "vernünftigen" Rückgabewert ausgibt.   ─   42 09.11.2020 um 11:29
Danke dir, wie muss ich vorgehen, damit ich die Recurrence aufschreiben kann?   ─   sayuri 13.11.2020 um 14:41

Kommentar schreiben