Ejercicios Examen ADA

Ejercicios Examen ADA

Nombre: Danitza González Orellana.

Pregunta 3:  Ud. debe contestar una prueba n preguntas de alternativas que está diseñada de tal manera que no puede contestarse en el tiempo dado T. previamente se le entrega el puntaje y tiempo estimado para cada pregunta. diseñe un algoritmo voraz que le permita maximizar su puntaje. su algoritmo le permite obtener el óptimo? suposición: Ud. puede responder correctamente todas las respuestas.

Es un problema de optimización, similar al de la mochila.

- V almacena los puntajes de cada prueba,
- P almacena el tiempo de cada prueba,
- sol devuelve el tanto por 1 de prueba que se toma,
- punt devuelve el puntaje total,
- punt_obten almacena el puntaje parcial,
- tiem_ac almacena el tiempo parcial.

fun mochila (V [1..n], P[1..n] de nat; m: nat) dev
begin
      para j := 1 hasta n hacer
            sol [j] := 0;
      fpara
      punt_obten := 0; i:=0; tiem_ac := 0;
      mientras tiem_ac < m hacer
               si tiempo [i] + tiem_ac < m entonces
                        punt_obten := punt_obten + puntaje [i];
                         sol [i] := 1;
                         tiem_ac := tiem_ac + tiempo [i]; 
                si no
                         sol [i] := (m – tiem_ac) / tiempo [i];
                         tiem_ac := m;
                         punt_obten := punt_obten + puntaje [i] * sol [i];
                fsi
                i := i + 1; 
        fmientras
punt := punt_obten;
ffun

Pregunta 4: Se tiene un arreglo A ordenado ascendentemente de tamaño n. Diseñe una función en PseudoC tal que chequee si existe un i tal que A (i)=i y que sea de orden logarítmico. Justifique su respuesta

fun coincide(A[1..n], c, f)

//c,f: límites de la búsqueda

    casos

c > f :

coincide ← falso

c = f :

coincide ←A[c] = c

c < f :

m ← div(c + f)/2

  casos

m < A[m] :

        coincide ← coincide(A, c, m  1)

m = A[m] :

        coincide ← cierto

m > A[m] :

        coincide ← coincide(A, m + 1, f)

  fin casos

     fin casos

     devolver coinciden

fun

*Es de orden logarítmico, porque divide el problema en sub-problemas, y en este caso el uso está en la línea: m ← div(c + f)/2 , seria log2 n.

...