Minimalna ilość operacji mnożenia kilku macierzy

[kokosek]

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?

[scyth]

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).

[kokosek]

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

[scyth]

Nie wiem jaka jest odpowiedź na twoje pytanie, pokazałem tylko, że raczej nie taka, jak podałeś.

[kokosek]

Znalazłem algorytm rozwiązujący ten problem, gdyby ktoś potrzebował: