Considere el problema de una string < A 1 , A 2 , A 3 , A 4 > de cuatro arrays. Suponga que las dimensiones de las arrays A 1 , A 2 , A 3 y A 4 son 30 × 35, 35 × 15, 15 × 5 y 5 × 10 respectivamente. El número mínimo de multiplicaciones escalares necesarias para calcular el
producto A 1 A 2 A 3 A 4 es ____.
(A) 14875
(B) 21000
(C) 9375
(D) 11875
Respuesta: (C)
Explicación:
la respuesta es 9375
El paréntesis de array será A1 ((A2A3) A4) para el número mínimo de multiplicaciones escalares
se resolverá mediante el uso de programación dinámica como
Las dimensiones de la array dada son:
A1 (30×35), A2 (35×15), A3 (15×5) y A4 (5×10)
- A12=30×35×15=15750
- A23=35×15×5=2625
- A34=15×5×10=750
A13 = mínimo (A12 + A33 + 35×15×5 = 18375, A11 + A23 + 30×35×5=9375)
A24= mínimo (A23 + A44 + 5×10×5 =9375, A22+ A34 +5×20×5= 6776)
A14 = mín ( A11 + A24 + 10×5×5 , A12 + A34 + 10×20×5>= 6736 , A13 + A44 + 10×20×5 )
La respuesta es 9375.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA