Witam.
// do moderatorów: proszę przed przeniesieniem mojego tematu do kosza powiadamiać mnie jakoś o powodzie, żebym mógł się poprawić; bez tego będę bezmyślnie zastanawiał się nad powodem moderacji i nie będę miał możliwości zmiany swojego postępowania, co raczej jest właśnie celem moderatora (a także moim)
Mam zadanie, które polega na obliczeniu najmniejszej ilości operacji, które trzeba wykonać, aby pomnożyć n macierzy.
Weźmy np. 5 macierzy:
13x32, 32x15, 15x30, 30x24, 24x16
Wynik wg mnie to: 26422.
Mój algorytm:
-obliczamy ilość operacji dla każdych dwóch macierzy, które są koło siebie:
13*32*15=6240, 32*15*30=14400, 15*30*24=10800, 30*24*16=11520
-wybieramy z nich najmniejszą (6240) i dodajemy do wyniku
-zamieniamy te 2 macierze na macierz wymnożoną; mamy teraz:
13x15, 15x30, 30x24, 24x16
-i postępujemy tak, aż otrzymamy jedną macierz
-kolejne mnożenia to zatem:
13x15 15x30 (13x30, 30x24, 24x16) // + 5850
13x30 30x24 (13x24, 24x16) // + 9360
13x24 24x16 (13x16) // +4992
Wynik=6240+5850+9360+4992=26422.
Dobrze myślę czy jest gdzieś błąd w moim rozumowaniu?
Minimalna ilość operacji mnożenia kilku macierzy
- scyth
- Użytkownik
- Posty: 6392
- Rejestracja: 23 lip 2007, o 15:26
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 3 razy
- Pomógł: 1087 razy
Minimalna ilość operacji mnożenia kilku macierzy
13x32, 32x15, 15x30, 30x24, 24x16
13*32*15 = 6240
15*30*24 = 10800
13x15, 15x24, 24x16
15*24*16 = 5760
13x15, 15x16
13*15*16 = 3120
suma = 25 920
Mnóż tak, żeby jak największe liczby były "w środku" (czyli mnożone tylko raz).
13*32*15 = 6240
15*30*24 = 10800
13x15, 15x24, 24x16
15*24*16 = 5760
13x15, 15x16
13*15*16 = 3120
suma = 25 920
Mnóż tak, żeby jak największe liczby były "w środku" (czyli mnożone tylko raz).
-
- Użytkownik
- Posty: 52
- Rejestracja: 24 maja 2010, o 21:36
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 14 razy
- Pomógł: 2 razy
Minimalna ilość operacji mnożenia kilku macierzy
Dzięki za odpowiedź!
Ciekawy algorytm. Czyli okazuje się, że mój jest błędny.
Niestety Twój także.
Przykład (dla którego z kolei mój wyświetla poprawną odpowiedź):
10x20, 20x3, 3x1
10*20*3=600
10x3, 3x1
10*3*1=30
suma=630
Moim algorytmem:
10x20, 20x3, 3x1
20*3*1=60
10x20, 20x1
10*20*1=200
suma=260
Ciekawy algorytm. Czyli okazuje się, że mój jest błędny.
Niestety Twój także.
Przykład (dla którego z kolei mój wyświetla poprawną odpowiedź):
10x20, 20x3, 3x1
10*20*3=600
10x3, 3x1
10*3*1=30
suma=630
Moim algorytmem:
10x20, 20x3, 3x1
20*3*1=60
10x20, 20x1
10*20*1=200
suma=260