ECAES

 

7. Dada la siguiente instrucci�n for (A y D son condiciones; C y E son instrucciones; A, D, C, E

no modifican el valor de i):

 

for (i= 1; i<=1000; i= i+1)

if (A) C;

else if (D) E;

else C;

 

Si A es cierta con probabilidad 0.6 y D es cierta con probabilidad 0.8, el n�mero esperado de

ejecuciones de C, es

 

A. 80

B. 480

C. 600

D. 920

E. 680

 

Es la opci�n E ya que al correr el codigo, el for va a realizar 1000 iteraciones. La condici�n� if(A) en cierto va correr la instrucci�n C 600 veces, por la P(A)=0.6, luego cuando if(A) es falso cae las otras 400 veces, de las cuales, si la condici�n if (D) es cierto, el c�digo b corre 320 veces, por la P(B)=0.8, por ultimo cuando if(D) es falso C se corre las restantes 80 veces, en total la instrucci�n C corre 680 veces de las 1000 iteraciones.

 

10. Indique cu�l de los siguientes fragmentos de programa es correcto con respecto a

la especificaci�n

�

(x mod y es el residuo de la divisi�n entera de x por y):

Pre: Existe k (k>=0): pot == 2k

Pos: pot == 1

 

A. while (pot/2 == 0) pot= pot mod 2;

B. while (pot mod 2 == 0) pot= pot/2;

C. while (2 mod pot == 0) pot= pot/2;

D. if (pot mod 2 == 0) pot= 1; else pot= 0;

E. if (pot/2 == 0) pot= 1; else pot= 0;

�

Es la C ya que si el numero pot es par, entra en el while y se divide en dos, luego vuelve y verifica si es par, si lo es vuelve y entra tantas veces como pueda hasta que es un numero impar. Si el impar es 1 es una potencia de 2, ya que al hacer el proceso a la inversa el pot variar�a asi: {1,2,4,8,16,32,64,�.}; si pot es un impar> 1 entonces no es una potencia de 2, ya que por ejemplo si pot =3 al hacer el proceso a la inversa el pot variar�a asi: {3,6,12,24,48,96,192,�.} serie de n�meros los cuales no son potencias de 2.

 

12. Mar�a escoge un n�mero entre 1 y 64. Pedro debe identificar el n�mero haciendo preguntas que se responden con un �s�� o con un �no�. Pedro sabe que Mar�a siempre responde con la verdad. Si Pedro usa una estrategia �ptima �cu�ntas preguntas debe hacer en el peor de los casos?

A. 1

B. 32

C. 6

D. 5

E. 7

Es la C ya que Maria al solo poder responder si o no, podemos solucionar este problema de una forma �ptima utilizando un algoritmo divide y venceras, con T(n) = 2T(n/2), el cual tiene una complejidad de , con lo cual� para n=64 el T(n)=6.

 

 

13. El siguiente programa calcula en r el producto de dos n�meros a y b mediante

sumas:

 

/* Q: b > 0 */

r= 0;

n= b;

while (n!=0){

r= r+a;

n= n-1;

}

/* R: r == ab */

 

De las siguientes aserciones, es un invariante para el ciclo

 

A. r == b(a-n)

B. r == a(b-n)

C. r == b2 -bn

D. r == ab-n

E. r == an-ab

 

Es la aserci�n B ya que para i=0, n=b-i, n=b, r₀=0, se supone cierto para i, r_i=a(b-n_i), r_i=a*i y para i=i+1 es n_i+1=b-(i+1) , n_i+1=b-i-1, r_i+1=a(b-(b-i-1)), r_i+1=a(b-b+i+1), r_i+1=a(i+1) lo cual es cierto para al iteraci�n i+1 don de n= b-i-1, es decir por inducci�n que la aserci�n c es cierta.