Turbo Pascal - Algorytm Strassena

[Lilo]

Witam wielkich programistów i proszę o pomoc. Muszę napisać program w Turbo Pascalu mnożący macierze NxN algorytmem Strassena. Wiem jak wygląda to dla macierzy 2x2 lecz nie wiem jak zrobić by działało dla macierzy dowolnego stopnia.

 

Druga sprawa nie wiem w jaki sposób wpisać clrscr; by zadziałał. Próbowałem na różne sposoby i zawsze wyskakuje jakiś błąd.

 

Po trzecie czy da się zadeklarować tablice, której długość można wczytać potem z klawiatury?

 

Wielkie dzięki za każdą pomoc.

Edytowane 6 Czerwca 2005 przez Lilo

[luminat]

1. Do procedury clrscr; potrzebna jest deklaracja modulu crt.

 

2. W Pascalu nie mozna zadeklarowac tablicy dynamicznej. Ale twoj problem mozna rozwiazac nieco inaczej...

 

..... randomize;write('Wielkosc tablicy: ');repeatreadln(wiel_tab);until (wiel_tab>=1) and (wiel_tab<=15); {15 - to rozmiar zadeklarowanej tablicy}for i:=1 do wiel_tab   for j:=1 do wiel_tab        tablica[i,j]:=random(99)+1;.......

Edytowane 18 Maja 2005 przez luminat

[Lilo]

Wielkie dzięki za odpowiedź.

 

Pozostaje jednak jeszcze sprawa algorytmu Strassena.

 

Może to pomoże wam mi pomóc.

 

Algorytm wygląda następująco dla macierzy 2x2:

 

* obliczamy 7 pomocniczych macierzy mi o rozmiarze n/2 x n/2.

m1=(A12-A22)*(B21+B22)

m2=(A11+A22)*(B11+B22)

m3=(A11-A21)*(B11+B12)

m4=(A11+A12)*B22

m5=A11*(B12-B22)

m6=A22*(B21-B11)

m7=(A21+A22)*B11

 

* obliczamy składowe Cij macierzy wynikowej C

C11=m1+m2-m4+m6

C12=m4+m5

C21=m6+m7

C22=m2-m3+m5-m7

Edytowane 6 Czerwca 2005 przez Lilo

[Lilo]

OK. Już zrozumiałem ten algorytm.

 

Ale mam następny problem. Jak napisać coś takiego (aaaa+dddd)*(eeee+hhhh) oczywiście w sposób ogólny, żeby działało też na macierzach 6x6, 8x8 itd.

 

 

( aa | bb ) ( ee | ff )

( aa | bb ) ( ee | ff )

(---+---) (---+---)

(cc | dd ) ( gg | hh )

(cc | dd ) ( gg | hh )

 

Myślałem o pętli od 1 do n/2 ale nie chce działać.

Edytowane 6 Czerwca 2005 przez Lilo

[ULLISSES]

Hmm.. Może coś takiego:

 

procedure potega(x,n)  var   i: Integer;  begin if n>1 then  begin  for i:=2 to n do   begin   x:=x*x;   end;  end; return x; end;

 

Pisałem w notatniku (nie kompilowałem), więc mogą być krzaki.. ale chodziło mi o ogólny pomysł...

Edytowane 8 Czerwca 2005 przez ULLISSES

[Lilo]

Nie wiem jak to się ma do mojego problemu.

[ULLISSES]

Hmm..

Jeśli zapis "aaaa" oznacza (jak mi się wydaje) mnożenie a*a*a*a i jest zależny od rozmiaru macierzy, to chyba się przyda...

[Lilo]

Nie. Chodzi o

 

(aa dd) (ee hh)

(aa + dd)* (ee + hh)

Edytowane 18 Czerwca 2005 przez Lilo