Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
06.12.2004, 10:28 Uhr
~Martin25
Gast

Hallo,

ich habe ein Problem und würde mich über Hilfe freuen.

Ich habe eine beliebige Ausgangsmatrix und will nun die Anzahl der quadratischen Untermatrizen mit n Spalten/Zeilen herausfinden.

Außerdem will ich dann die Anzahl der quadratischen Untermatrizen herausfinden, die zusätzlich in der Hauptdiagonalen nur Einsen haben.

Würde mich freuen, wenn mir jemand helfen könnte.

Viele Grüße Martin

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
06.12.2004, 11:18 Uhr
~Hammurabi
Gast

Wie ist denn Dein Ansatz?

Eigentlich musst Du doch die Elemente in beide Richtungen zählen. Und später nach einsen durchsuchen...

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
06.12.2004, 11:36 Uhr
~Martin25
Gast

erstmal muß ich ja versuchen irgendwie die generelle Anzahl einer quadratischen Untermatrix zu bekommen, also zum Beispiel wieviele Untermatizen gibt es mit jeweils 2 Spalten und 2 Zeilen usw.

Bin am Überlegen, ob ich die Matrix dann für ein einzugebendes n irgendwie durchlaufen lassen kann. Ich stelle mit vor die Untermatrix oben links einzusetzen und dann nach rechts durchlaufen zu lassen bis die rechte Seite der Untermatrix auf die rechte Seite der Ausgangsmatrix stößt. Dann gehts in die nächste Zeile und wieder an den linken Rand. Nur mit der Umsetzung habe ich da meine Probleme, vielleicht denke ich auch zu kompliziert.

Wie meinst du das mit den Elementen in beide Richtungen zählen?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
06.12.2004, 12:41 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)

also wenn du ein matrix der grösse nxn hast und die untermatrix kxk hat dann kannst du da genau
n/k*n/k untermatrizen (unter der annahme k teilt n an sonsten 2*n/k -1 weniger) reinpacken...

an die diagonale rankommen ist dann auch kein wirkliches problem...

einfach zwei äussere schleifen (für jede submatrix)
und zwei innere schleifen (für jedes element der submatrix (hier musst du einfach nur nen offset draufaddieren der abhängig davon ist bei der wievielten submatrix du dich gerade befindest und welche grössse die submatrizen haben
--
...fleißig wie zwei Weißbrote

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
06.12.2004, 16:54 Uhr
derphilipder

Zitat von ~Martin25:

Hallo,
Ich habe eine beliebige Ausgangsmatrix...

Zitat von Windalf:

also wenn du ein matrix der grösse nxn hast...

Trotzdem nicht schwer...

Bei sowas hilft mir immer eine kleine Skizze, mit der ich mir dann ein Schleifenkonstrukt zurechtbastle. Aber ich denke, das kriegst Du auch allein hin.

--
Konfuzius says: "A man who goes to bed with an itchy asshole is a man who wakes up with stinky finger!"

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
06.12.2004, 18:34 Uhr
~Martin25
Gast

Zitat von derphilipder:

[quote ~Martin25]Hallo,
Ich habe eine beliebige Ausgangsmatrix...

Zitat von Windalf:

also wenn du ein matrix der grösse nxn hast...

Trotzdem nicht schwer...

Bei sowas hilft mir immer eine kleine Skizze, mit der ich mir dann ein Schleifenkonstrukt zurechtbastle. Aber ich denke, das kriegst Du auch allein hin.

[/quote]

Glaube mir, ich hätte nicht gepostet, wenn ich nicht wirklich damit ein Problem und schon vieles ausprobiert hätte. Freut mich aber, daß du es nicht schwer findest und der Meinung bist, daß ich es alleine hinbekomme.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
06.12.2004, 18:49 Uhr
~Martin25
Gast

Was haltet ihr denn von folgender Formel zum Berechnen der Anzahl?

anzahl=((z-n+1)*(s-n+1)) Matrix(z/s) QuadMatrix(n/n)

also Beispiel Matrix(4/3) und QuadMatrix(2/2)

wäre ja in dem Fall (4-2+1)*(3-2+1) = 3 * 2 = 6 Untermatrizen mit n = 2 und die würden ja genau reinpassen.

1 1 1
0 1 0
1 0 1
1 1 1

Aber ich stehe wohl immer noch auf dem Schlauch.Wie darf ich denn das mit der Schleifenbildung verstehen?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
07.12.2004, 01:52 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)

ach so meinst du das ...
jo wenn du eine matrix a x b hast und da ein quadratische matrix matrix c x c reinpacken willst geht das

(a-c+1)*(b-c+1) für c<=a und c<=b
sonst 0... ups seh gerade hast ja die gleiche formel

auf die schnelle würd ich sagen so

C++:

int anzahl1erdiag(int *m,int a,int b,int c){

    int i,j,k,l,rv=0;
    for(j=0;j<=b-c;++j)
        for(i=0;i<=a-c;++i,rv+=l)
            for(k=0,l=1;l&&k<c;++k)
                if(m[(j+k)*a+i+k]!=1)
                    l=0;

    return rv;
}

int main(){

    int m[]={ 63, -34,  49,  10,   7,  13, -12,   7,
             -31,  23,  14,  1,    3,   4,   6,  -1,
              15,  14,   3, -12,   1,  -7,   3,   9,
              -9,  -7, -14,   8,   4,   1,   3,   2,
              -5,   9,  -1,   1,   4,   6,  -2,   2,
               3,   0,  -3,   2,   1,  -2,   0,   4,
               5,  11,   5,   6,   0,   3,  -4,   4};
    int a,b,c;
    a=8;b=7;c=2;

    printf("%d\n",anzahl1erdiag(m,a,b,c));

}

--
...fleißig wie zwei Weißbrote

Dieser Post wurde am 07.12.2004 um 01:54 Uhr von Windalf editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
07.12.2004, 10:05 Uhr
~Matrin25
Gast

Zitat von Windalf:

ach so meinst du das ...
jo wenn du eine matrix a x b hast und da ein quadratische matrix matrix c x c reinpacken willst geht das

ja genau, deswegen habe ich ja am Anfang geschrieben beliebige Ausgangsmatrix und quadratische Untermatrizen.
Trotzdem danke für die Hilfe.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
07.12.2004, 12:46 Uhr
~Martin25
Gast

als wenn jemand einen Tipp hat, würde mich freuen...

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: