PUERTA | GATE-CS-2014-(Conjunto-1) | Pregunta 51

Considere el siguiente pseudocódigo. ¿Cuál es el número total de multiplicaciones a realizar?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3

(A) La mitad del producto de los 3 enteros consecutivos.
(B) Un tercio del producto de los 3 enteros consecutivos.
(C) Un sexto del producto de los 3 enteros consecutivos.
(D) Ninguna de las anteriores.

Respuesta: (C)
Explicación: La instrucción “D = D * 3” se ejecuta n*(n+1)*(n-1)/6 veces. Veamos cómo.
Para i = 1, la instrucción de multiplicación se ejecuta (n-1) + (n-2) + .. 2 + 1 veces.
Para i = 2, la sentencia se ejecuta (n-2) + (n-3) + .. 2 + 1 veces
………………………..
……………………….
Para i = n-1, la instrucción se ejecuta una vez.
Para i = n, la declaración no se ejecuta en absoluto

Entonces, en general, la declaración se ejecuta después
de [(n-1) + (n-2) + .. 2 + 1] + [(n-2) + (n-3) + .. 2 + 1] + … + 1 + 0

La serie anterior se puede escribir como
S = [n*(n-1)/2 + (n-1)*(n-2)/2 + ….. + 1]

La suma de la serie anterior se puede obtener restando la serie de la Serie estándar S1 = n2 + (n-1)2 + .. 12. La suma de esta serie estándar es n*(n+1)*(2n+ 1)/6

S1 – 2S = n + (n-1) + … 1 = n*(n+1)/2
2S = n*(n+1)*(2n+1)/6 – n*(n+1)/ 2
S = n*(n+1)*(n-1)/6

La solución anterior se basa en un truco para obtener la suma de la serie, pero hay una forma mucho más sencilla de obtener el mismo resultado:

Para i = 1, la instrucción de multiplicación se ejecuta (n-1) + (n-2) + .. 2 + 1 veces.

Para i = 2, la instrucción se ejecuta (n-2) + (n-3) + .. 2 + 1 veces

Por tanto, para cada i, el número de veces que se ejecuta la sentencia es:

$\sum_{k=1}^{n-i}k$

Esta es la suma de n números naturales de 1 a n – i. Por lo tanto, se puede simplificar a:

$\frac{(n -i) \times (n - i + 1)}{2}$

Multiplicando obtendremos lo siguiente:

$\frac{n^{2}-2ni + n + i^{2} - i}{2}$

Ahora, esta es la cantidad de veces que se ejecutará la declaración para cada i. Por tanto, en total, el número de veces que se ejecutará la sentencia es:

$\frac{1}{2}\sum_{i = 1}^{n}\left ( n^{2}-2ni + n + i^{2} - i \right )$