Teile-und-herrsche Prinzip

Aufrufe: 85     Aktiv: vor 2 Wochen, 3 Tagen

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

 

gefragt vor 3 Wochen, 1 Tag
s
sayuri,
Student, Punkte: 108

 
Kommentar schreiben Diese Frage melden
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

geantwortet vor 3 Wochen, 1 Tag
s
staffymon23
Student, Punkte: 101
 

oh danke!   ─   sayuri, vor 3 Wochen, 1 Tag
Kommentar schreiben Diese Antwort melden
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 \).

geantwortet vor 3 Wochen, 1 Tag
g
anonym
Student, Punkte: 3.77K
 

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).   ─   anonym, vor 3 Wochen, 1 Tag

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, vor 3 Wochen, 1 Tag

\( \lfloor \cdot \rfloor \) ist die untere Gaußklammer. Das bedeutet immer abrunden, also \( \lfloor \frac{7}{4} \rfloor = \lfloor 1,75 \rfloor = 1 \).   ─   anonym, vor 3 Wochen

Vielen Dank!   ─   sayuri, vor 3 Wochen

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, vor 3 Wochen

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.
  ─   anonym, vor 3 Wochen

Also, dann muss ich solange return UN(A, l, q) * UN(A, q+1, l) durchführen bis es l = r entspricht?   ─   sayuri, vor 3 Wochen

Ja, du musst den Algorithmus so lange durchführen, bis er einen "vernünftigen" Rückgabewert ausgibt.   ─   anonym, vor 3 Wochen

Danke dir, wie muss ich vorgehen, damit ich die Recurrence aufschreiben kann?   ─   sayuri, vor 2 Wochen, 3 Tagen
Kommentar schreiben Diese Antwort melden