Suponga que multiplicar una array G 1 de dimensión p×q con otra array G 2 de dimensión q×r requiere multiplicaciones escalares pqr. Calcular el producto de n arrays G 1 G 2 G 3 ….. G n se puede hacer entre paréntesis de diferentes maneras. Defina G i G i+1 como un par calculado explícitamente para un paréntesis dado si se multiplican directamente. Por ejemplo, en la string de multiplicación de arrays G 1 G 2 G 3 G 4 G 5 G 6 usando paréntesis (G 1 (G2 G 3 ))(G 4 (G 5 G 6 )), G 2 G 3 y G 5 G 6 son solo pares calculados explícitamente.
Considere una string de multiplicación de arrays F 1 F 2 F 3 F 4 F 5 , donde las arrays F 1 ,F 2 ,F 3 ,F 4 y F 5 tienen dimensiones 2×25,25×3,3×16,16×1 y 1×1000, respectivamente. En el paréntesis de F 1 F 2 F 3 F 4 F 5 que minimiza el número total de multiplicaciones escalares, los pares calculados explícitamente son
(A) F 1 F 2 y F 3 F 4 solamente
(B) F 2 F 3 solamente
(C) F 3 F 4 solamente
(D) F 1 F 2 y F 4 F 5 solamente
Respuesta: (C)
Explicación: Array F5 es de dimensión 1 X 1000, lo que va a causar mucho costo de multiplicación. Así que evaluar F5 por fin es óptimo.
El número total de multiplicaciones escalares es 48 + 75 + 50 + 2000 = 2173 y el paréntesis óptimo es ((F1(F2(F3 F4)))F5).
Como se concluyó, F3, F4 son pares calculados explícitamente.
La opción (C) es correcta.
Cuestionario de esta pregunta
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