Diviser et Conquérir de Multiplication de Matrice
Je vais avoir de la difficulté à se diviser et conquérir de multiplication de matrice de travail. Ce que je comprends, vous divisez les matrices de taille nxn dans les quadrants (chaque quadrant est n/2) et puis tu fais:
C11 = A11⋅ B11 + A12 ⋅ B21
C12 = A11⋅ B12 + A12 ⋅ B22
C21 = A21 ⋅ B11 + A22 ⋅ B21
C22 = A21 ⋅ B12 + A22 ⋅ B22
Ma sortie pour diviser et conquérir est vraiment grand et j'ai du mal à comprendre le problème que je ne suis pas très bon avec la récursivité.
exemple de sortie:
Original De La Matrice A:
4 0 4 3
5 4 0 4
4 0 4 0
4 1 1 1
X
Classique:
44 3 35 15
56 20 24 35
32 0 32 12
29 5 21 17
Diviser pour régner:
992 24 632 408
1600 272 720 1232
512 0 512 384
460 17 405 497
Quelqu'un pourrait-il me dire ce que je fais de mal pour diviser et conquérir? Tous mes matrices sont int[][]
et classique est la méthode traditionnelle de 3 pour la boucle de multiplication de matrice
Pourquoi est-ce que vous voulez faire de la multiplication de matrice de cette façon? Si vous êtes intéressé par la performance brute il y a des bibliothèques numériques disponibles, j'en suis sûr, serait plus rapide que ce que vous pouvez écrire sur votre propre dans un laps de temps raisonnable. Si vous êtes intéressés à en apprendre sur le calcul numérique, je voudrais commencer avec boucle de carrelage (wikipedia a un article) au lieu d'une solution récursive.
ses devoirs à la maison.
ses devoirs à la maison.
OriginalL'auteur Raptrex | 2011-01-31
Vous devez vous connecter pour publier un commentaire.
Vous sont récursivement appel
divideAndConquer
dans le mauvais sens. Ce que votre fonction n'est carrée d'une matrice. Dans le but de diviser et conquérir de multiplication de matrice de travail, il doit être capable de se multiplier deux potentiellement différentes matrices ensemble.Il devrait ressembler à quelque chose comme ceci:
OriginalL'auteur Null Set
Un peu de débogage approches pour essayer:
Essayer quelques très simple test de matrices d'entrée (par exemple, tous les zéros, avec un seul ou de quelques stratégiques). Vous pouvez voir un modèle dans les "échecs" qui va vous montrer où est votre erreur(s).
Assurez-vous que votre "classique" de l'approche est de vous donner les réponses correctes. Pour les petites matrices, vous pouvez utiliser Woflram Alpha en ligne de réponses de test: http://www.wolframalpha.com/examples/Matrices.html
Pour déboguer la récursivité: ajouter
printf()
déclarations à l'entrée et à la sortie de votre fonction, y compris l'invocation d'arguments. Exécutez le test de la matrice, écrire la sortie dans un fichier journal, et ouvrez le fichier journal avec un éditeur de texte. Étape à travers chaque cas, écrire des notes à vos côtés dans l'éditeur pour vous assurer qu'elle fonctionne correctement à chaque étape. Ajouter plus deprintf()
états et exécutez à nouveau si nécessaire.Bonne chance avec les devoirs à la maison!
Oui, une matrice de zéros, vous donnera zéro. Mais ajouter QUELQUES stratégiques, (comme tous dans une ligne ou une colonne ou diagonale) vous donnera une meilleure tests.
OriginalL'auteur payne
Oui:
Vous allez par le biais d'un supplément de multiplication: vous ne devriez pas appeler les deux
divideAndConquer()
etclassical()
.Ce que vous êtes effectivement en train de faire est de:
qui n'est pas correct.
Tout d'abord, retirez le
divideAndConquer()
appels, et de remplacer un a/b/c/d par topLeft/haut/etc.Voir si elle vous donne un bon résultat.
Votre
divideAndConquer()
méthode a besoin d'une paire de paramètres d'entrée, de sorte que vous pouvez utiliser A*B. une Fois que vous obtenir que le travail, de se débarrasser des appels àclassical()
, et l'utilisationdivideAndConquer()
à la place. (ou les enregistrer pour les matrices qui ne sont pas un multiple de 2 dans la longueur.)OriginalL'auteur Jason S
Vous pouvez trouver l'article de Wiki sur L'algorithme de Strassen utile.
OriginalL'auteur Charlie Martin