Siemka,
Próbuje zrobic program ktory rekurencyjnie pomnozy mi macierze znajac juz optymalne nawiasowanie i tutaj rodzi sie problem bowiem nie moge korzystac w funkcji A z tablic stworzonych w funkcji B
Pseudokod
Int funkcja(mamy dwie tablice)
{
Tworzymy trzecia tablice
Wypelnij tab 3 na podstawie tab1 i tab2
Zwroc tab 3
}
Jak to zrobic w c++ zeby to dzialalo
Z gory dzieki
0
0
Czemu chcesz rekurencyjnie mnożyć macierze?
W każdym razie wgłąb stosu wywołań możesz po prostu podać wskaźnik do tablicy docelowej. Albo użyj std::array i traktuj je jak normalne obiekty. Przy czym to jest odpowiedź na Twoje pytanie, ale raczej nie jest to poprawne rozwiązanie problemu.
0
Takie zadanie jest w wprowadzeniu do algorytmow cormena. Znam juz optymalne nawiasowanie ciagu macierzy. Teraz mam stworzyc rekurencyjna funkcje ktora mnozny macierze na podstawie tego nawiasowania takie dziel i zwyciezaj.
Chodzi o mniej wiecej cos takiego
Mam funcje zeby pomnozyla maxiezw od 1 do n
Int macierz
Macierz =funkcja(1do x)*funkcja(x+1 do n)
Return macierz
Chodzi o to tworzenie tej macierzy i potem jej zwracanie przeciez zwracajac w wyzej opisany sposob zwracam wskaznik do nieistniejacej juz macierzy czyz nie?
1
@kq: Jest metoda mnożenia macieży o złożoności O(n2.8) oraz O(n2.38), która idzie rekurencyjnie. Więcej: https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm
0
@korec123 nie jeśli alokujesz macierz dynamicznie przez new[]
0
A przy duzych rozmiarach macierzy i duzym n trzymanie wszystkich tych tablic dynamicznych nie pociagnie za duzo pamieci?
0
A po co chcesz trzymać wszystkie? o_O Mnożysz dwie i mozesz je zwolnić bo nie są ci juz przecież potrzebne.
0
Napisałem taką funkcję do mnożenia ciągu macierzy:
int ** realmatrixmultiply(int m,int n,int* prices)
{
// zwracanie macierzy x gdy mamy wywołanie aby pomnożyć macierze od x do x
if (m==n)
return
//inicjalizacja trzech nowych macierzy
int **finalmatrix= new int*[100] ;
for(int i=0;i<100;++i)
finalmatrix[i]=new int[100];
int **matrix1= new int*[100] ;
for(int i=0;i<100;++i)
matrix1[i]=new int[100];
int **matrix2= new int*[100] ;
for(int i=0;i<100;++i)
matrix2[i]=new int[100];
//wypełnianie dwóch pomocnicznych macierzy
matrix1=realmatrixmultiply(m,arr2[m][n],prices);
matrix2=realmatrixmultiply(arr2[m][n]+1,n,prices);
//mnozenie macierzy 1 i 2 w celu otrzymania koncowej
for (int i=1 ;i<=prices[m-1] ;++i)
{
for (int j=1;j<=prices[n] ;++j)
{
finalmatrix[i][j]=0;
for(int k=1;k<=prices[arr2[m][n]] ; ++k)
finalmatrix[i][j]=finalmatrix[i][j]+(matrix1[i][k]*matrix2[k][j]);
}
}
//czyszczenie dwóch niepotrzebnych macierzy
for(int i=0;i<100;++i)
delete [] matrix1[i];
delete [] matrix1;
for(int i=0;i<100;++i)
delete [] matrix2[i];
delete [] matrix2;
return finalmatrix;
}
Jest wywoływana przez to:
int **finalpointer= realmatrixmultiply(1,n,prices);
W moim kodzie tablica prices[n+1] to tablica wymiarów kolejnych n macierzy, gdzie wymiary macierzy i=1,n to prices[i-1]*prices[i]
a tablica arr2[i][j] zwraca k ktore mowi ze aby otrzymac macierz ij trzeba pomnozyc macierze i,k oraz k+1,j
Wydaje mi się że wszystko dobrze powinno działać,ale jakby ktoś coś znalazł to niech komentuje!
ostatnie moje pytanie:
Jak wczytać macierze aby potem można było je returnować w 3 wierszu funkcji?
Chodzi mi o to że na wejściu mam n macierzy więc tak naprawdę musiałbym zadeklarować trójwymiarową tablicę w mainie do przechowywania n macierzy ale jak potem przyjemnie na tym działać?
Edit:
W sumie to można zadeklarować nową dwuwymiarową tablicę i przepisać do niej macierz z tablicy trójwymiarowej z maina ale to jest dodatkowa pamieć i operacje więc poczekam może ktoś wie jak to lepiej zrobić
0
Pierwsze primo: zapomnij o tablicach wielowymiarowych - zastanów się jak to zrobić na typie double * i odpowiednim indeksowaniu elementów (row-major, column-major).
Drugie primo:
//wypełnianie dwóch pomocnicznych macierzy
matrix1=realmatrixmultiply(m,arr2[m][n],prices);
matrix2=realmatrixmultiply(arr2[m][n]+1,n,prices);
Wypełnianie macierzy nazywa się "realmatrixmultiply"? No, spodziewałbym się czegoś innego.
Trzecie primo:
for (int i=1 ;i<=prices[m-1] ;++i)
{
for (int j=1;j<=prices[n] ;++j)
{
finalmatrix[i][j]=0;
for(int k=1;k<=prices[arr2[m][n]] ; ++k)
finalmatrix[i][j]=finalmatrix[i][j]+(matrix1[i][k]*matrix2[k][j]);
}
}
Pochwal się wydajnością tego. Strzelam, że przy takiej alokacji macierzy jak powyżej i takim mnożeniu na procku o teoretycznym Rpeak=10GFLOPS będziesz miał może ze 100MFLOPS.
Edit:
Jesteś pewien, że chcesz mnożyć macierze typu całkowitoliczbowego?
0
Przede wszystkim chcę żeby ten algorytm jakoś działał i chcę jakoś poprawić tą alokacje tablic.
Co to ma za znaczenie czy macierze całkowitoliczbowe czy nie?
2
Artykułów o podstawowym użyciu typów zmiennoprzecinkowych, to poszukałbym w jakimś kursie do programowania od podstaw.
Dlaczego nie int? Głównie dlatego, że mnożenie macierzy to zagadnienie z numeryki, a tam prawie wyłącznie używa się typów zmiennoprzecinkowych. Ktoś nawet kiedyś coś robił z intami, ale szybko wyleciał do bibliotek obsługujących inty o niemalże dowolnej długości: http://dl.acm.org/citation.cfm?id=1073899
Wracając do Twojego problemu - wyobraź sobie, że masz macierz n x m. Nie chcemy używać tablic wielowymiarowych, tylko zaalokować ciągły obszar o rozmiarze n x m x sizeof(typ). Alokacja jest stosunkowo prosta, pytanie - jak nawigować po takim obszarze? Masz dwie opcje: chcąc dostać się do elementu o indeksie (i, j) możesz zrobić dwie rzeczy:
idx = i * n + j;
lub
idx = j * m + i;
Pierwszy przypadek - row-major (wierszowo), drugi - column-major (kolumnowo). Dostajesz w efekcie po prostu indeks w tablicy jednowymiarowej. Pierwszy z tych sposobów jest domyślny dla C, drugi dla Fortrana, Pascala i wszystkich BLASów, LAPACKów i innych takich.
Odnośnie mnożenia - ja się nie czepiam, że tak nie jest w CLRS albo że to źle. Ja mówię, że to bardzo powolne (strzelam - 1% teoretycznej maksymalnej wydajności procesora). Nikt w praktyce nie stosuje tak napisanych algorytmów do mnożenia macierzy przez macierz. CLRS nie koncentruje się tutaj na niuansach działania fizycznego procesora, tylko na pokazaniu przykładowego kodu do mnożenia.
Kolejny komentarz: zauważ, że nawiasowanie formułuje Ci coś na kształt drzewa. Każdy węzeł w tym drzewie przechowuje (tymczasowo, dopóki nie policzymy sąsiada i rodzica) macierz o wymiarze p x q, gdzie p i q to liczba wierszy dajmy na to z lewego dziecka i liczba kolumn z prawego. Robiąc nawiasowanie optymalne przechodzisz po drzewie bottom-up, zwalniasz macierze tymczasowe po wymnożeniu ich w górze drzewa i w korzeniu w efekcie dostajesz iloczyn wszystkich macierzy. Nie napiszę Ci niestety kodu, bo nie mam na to czasu, ale spróbuj przemyśleć tą wskazówkę.