Algo: Matrix rekursiv transponieren?

häh

fällt jemanden dazu etwas ein? Wäre ein leichtes die Matrix einfach durchzugehen und die Elemente zu vertauschen aber rekursiv fällt mir da nichts clevers ein. Habe mir gedacht die Matrix rekursiv immer zu Halbieren sodas am Ende immer Paare von Indizees übrig bleiben die man dann vertauschen könnte. aber wie? also naheliegend ist das doch nicht?

Hier die genaue Aufgabe:

Gegeben seien m Listen von n Zeichen, m,n
1. Sie sind wiederum in einer Liste M zusammengefaßt. M soll transponiert
werden, d.h. die Zeilen sollen mit den Spalten vertauscht werden.
Hierzu soll ausschließlich der Datentyp list verwendet werden; außerdem soll der Algorithmus transpose rekursiv sein.

thx

WebFritzi

Für quadratische Matrizen:

// M: Zu transponierende Matrix
// n: Anzahl der Reihen (bzw. Spalten) von M
void Transpose(int n, CMatrix* M)
{
   if(n > 1)
   {      
      for(int i=1; i<n; ++i)
      {
         int dummy = M[i][n];
         M[i][n] = M[n][i];
         M[n][i] = dummy;
      }
      Transpose(n-1, &M);
   }
}

M[i][j] soll dabei der Eintrag in der i-ten Zeile und j-ten Spalte sein. Und nun überleg dir mal nen Code für nicht quadratische Matrizen. Das Prinzip kennst du ja jetzt.

[ Dieser Beitrag wurde am 08.01.2003 um 03:38 Uhr von WebFritzi editiert. ]

hi

danke mit deiner Lösung wird zwar nur die links obere Dreiecksmatrix transponiert aber ich mach einfach noch eine 2te for Schleife rein..

Werde jetzt erst mal die rechteckigen matrizen mit Nullen auffüllen, sodass ich eine quaratische bekomme. Hälst Du das für eine adequate Lösung?

WebFritzi

Meine Lösung war Blödsinn. Natürlich müssen zuerst die Umformungen und dann das rekursive Transpose() kommen. Ich hab das oben jetzt editiert.

hi auch diese Version funktioniert nicht Deine 2te Version transponiert die dreiecks matrix jetzt nur von aussen nach Innen statt anders rum. so funktioniert es die ganze Matrix zu transponieren:

{
        //rekursiver Aufruf
        transpose(n-1, matrix);
        //Dreiecksmatrix links oben transponieren
        for(int i=0; i<n-1; i++){
            char dummy = (*matrix)[i][n-i-1];
            (*matrix)[i][n-i-1] = (*matrix)[n-i-1][i];
            (*matrix)[n-i-1][i] = dummy;
        }

        //Dreiecksmatrix rechts unten transponieren
        for(i=1; i<n; i++){
            int dummy = (*matrix)[i][n-1];
            (*matrix)[i][n-1] = (*matrix)[n-1][i];
            (*matrix)[n-1][i] = dummy;
        }       
    }

WebFritzi

Original erstellt von <heiner>:
hi auch diese Version funktioniert nicht

Äh... doch!