Exámen Septiembre 2014 con respuestas.pdf PDF

Preview

Summary

Ingenier ́ıa Informatica - Depto. de Inform ́ atica e Ingenier ́ ́ıa de SistemasExamen de Programacion 2 - 11 de septiembre de 2014 ́Problema 1o(2 puntos)El coste en tiempo de ejecutar una invocacion del m ́ etodo ́ calcular(T)es asintoticamente constante, ́ es decir es delO(1). El coste en tiempo d...

Description

´ - Depto. de Informatica ´ Ingenier´ıa Informatica e Ingenier´ıa de Sistemas Examen de Programacion ´ 2 - 11 de septiembre de 2014 Problema 1o (2 puntos) El coste en tiempo de ejecutar una invocaci´on del m´etodo calcular(T) es asint´oticamente constante, on del m´etodo reorganizar(T,n) es es decir es del O(1). El coste en tiempo de ejecutar una invocaci´ 2 atico en n, es decir es del O(n ). asint´oticamente cuadr´ /∗∗ ∗ Pre: n > 0 ∗ Post : Devuelve ... ( irrelevante ) ... ∗/ private static double f (double[] T, int n) { if (n0 ∗ Post : menor(T) = (Min alfa EN [0,T. length −1].T[alfa ]) ∗/ private static double menor (double[] T) { double m1 = menor(T, 0, T. length /3); double m2 = menor(T, T. length /3, T. length −1); /∗ P ∗/ if (m10 AND i>=0 AND i 0 ⇒ [Prueba la satisfacci´on de la precondici´on de menor(T, 0, T.length/3)] T.length > 0 ∧ 0 ≥ 0 ∧ 0 ≤ T.length/3 ∧ T.length/3 < T.length */ /* T.length > 0 ⇒ [Prueba la satisfacci´on de la precondici´on de menor(T, T.length/3, T.length-1)] T.length > 0 ∧ T.length/3 ≥ 0 ∧ T.length/3 ≤ T.length − 1 ∧ T.length − 1 < T.length */ /* T.length > 0 ∧ menor(T, 0, T.length/3) = (Min α ∈ [0, T.length/3].T [α]) ∧ menor(T, T.length/3, T.length − 1) = (Min α ∈ [T.length/3, T.length − 1].T [α]) ⇒ [Prueba que es correcta la secuencia de dos instrucciones siguientes] T.length > 0 ∧ menor(T, 0, T.length/3) = (Min α ∈ [0, T.length/3].T [α]) ∧ menor(T, T.length/3, T.length − 1) = (Min α ∈ [T.length/3, T.length − 1].T [α]) */ double m1 = menor(T, 0, T.length/3); /* T.length > 0 ∧ m1 = (Min α ∈ [0, T.length/3].T [α]) ∧ menor(T, T.length/3, T.length − 1) = (Min α ∈ [T.length/3, T.length − 1].T [α]) */ double m2 = menor(T, T.length/3, T.length-1); /* P: T.length > 0 ∧ m1 = (Min α ∈ [0, T.length/3].T [α]) ∧ m2 = (Min α ∈ [T.length/3, T.length − 1].T [α]) */ if ( m1 0 */ double m1 = menor(T, 0, T.length/3); double m2 = menor(T, T.length/3, T.length-1); /* P: T.length > 0 ∧ m1 = (Min α ∈ [0, T.length/3].T [α]) ∧ m2 = (Min α ∈ [T.length/3, T.length − 1].T [α]) */ if ( m1 0 ∧ m1 = (Min α ∈ [0, T.length/3].T [α]) ∧ m2 = (Min α ∈ [T.length/3, T.length − 1].T [α]) ∧ m1 ≤ m2 ⇒ [Prueba que es correcta la instrucci´on siguiente] m1 = (Min α ∈ [0, T.length − 1].T [α]) */ return m1; } else { /* T.length > 0 ∧ m1 = (Min α ∈ [0, T.length/3].T [α]) ∧ m2 = (Min α ∈ [T.length/3, T.length − 1].T [α]) ∧ m1 > m2 ⇒ [Prueba que es correcta la instrucci´on siguiente] m2 = (Min α ∈ [0, T.length − 1].T [α]) */ return m2; } /* menor(T ) = (Min α ∈ [0, T.length − 1].T [α]) */ }

7

Una soluci´on del problema 3o Dise˜no recursivo del m´etodo resumir(T). /∗∗ ∗ Pre: T!=null AND (PT alfa EN [0,T. length −2].T[alfa]=0 AND j=0 AND j T[j+1] %2=1) ∗ AND cuenta = (N´um alfa EN [0,T. length −1].T[alfa] %2=0) ∗/

9...