Ich habe Probleme, Matrizenmultiplikation zu teilen und zu erobern. Von dem, was ich verstehe, teilen Sie die Matrizen der Größe nxn in Quadranten (jeder Quadrant ist n / 2) und dann tun Sie:
%Vor%Meine Ausgabe für "Teile und herrsche" ist sehr groß und ich habe Probleme, das Problem herauszufinden, da ich mit der Rekursion nicht sehr gut bin.
Beispielausgabe:
Ursprüngliche Matrix A:
%Vor%A x A
Klassik:
%Vor%Teilen und beherrschen:
%Vor% Könnte mir jemand sagen, was ich falsch mache, um zu teilen und zu erobern? Alle meine Matrizen sind int[][] und die klassische Methode ist die traditionelle 3 for loop Matrixmultiplikation
Sie rufen divideAndConquer rekursiv falsch auf. Was Ihre Funktion macht, ist eine Matrix. Damit die Matrixmultiplikation geteilt und überwunden werden kann, muss sie in der Lage sein, zwei potentiell unterschiedliche Matrizen zu multiplizieren.
Es sollte ungefähr so aussehen:
%Vor%Einige Debugging-Ansätze zum Ausprobieren:
Probieren Sie einige sehr einfache Testmatrizen als Eingabe aus (z. B. alle Nullen mit einer oder wenigen strategischen). Möglicherweise sehen Sie in den "Fehlern" ein Muster, das Ihnen anzeigt, wo sich Ihre Fehler befinden.
Stellen Sie sicher, dass Ihr "klassischer" Ansatz Ihnen korrekte Antworten gibt. Für kleine Matrizen können Sie Woflam Alpha online verwenden, um Antworten zu testen: Ссылка
Um die Rekursion zu debuggen: Fügen Sie printf() -Anweisungen am Eingang und Ende Ihrer Funktion hinzu, einschließlich der Aufrufargumente. Führen Sie Ihre Testmatrix aus, schreiben Sie die Ausgabe in eine Protokolldatei und öffnen Sie die Protokolldatei mit einem Texteditor. Gehen Sie Schritt für Schritt durch und schreiben Sie Ihre Notizen im Editor, um sicherzustellen, dass sie bei jedem Schritt korrekt funktionieren. Fügen Sie weitere printf() -Anweisungen hinzu und führen Sie sie bei Bedarf erneut aus.
Viel Glück bei den Hausaufgaben!
Könnte mir jemand sagen, was ich falsch mache, um zu teilen und zu erobern?
Ja:
%Vor% Sie gehen hier einen zusätzlichen Multiplikationsschritt durch: Sie sollten nicht divideAndConquer() und classical() aufrufen.
Was Sie effektiv tun, ist:
%Vor%was nicht korrekt ist.
Entfernen Sie zuerst die Aufrufe divideAndConquer() und ersetzen Sie a / b / c / d durch topLeft / topRight / etc.
Sehen Sie, ob es Ihnen die richtigen Ergebnisse gibt.
Ihre divideAndConquer() -Methode benötigt ein Paar Eingabeparameter, so dass Sie A * B verwenden können. Sobald du das geschafft hast, entferne die Aufrufe von classical() und verwende stattdessen divideAndConquer() . (Oder speichern Sie sie für Matrizen, die kein Vielfaches von 2 sind.)
Vielleicht finden Sie den Wiki-Artikel zum Strassen-Algorithmus hilfreich.
Tags und Links algorithm math matrix multiplication