Algoritmos y Estructuras de Datos I

Facultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Primer Cuatrimestre de 2000

 

Resolución de la Práctica 4

 

Ejercicio 1

 

1.1.i)

a) P º {n=N₀ Ù m=M₀}

 

1.1.ii)

b) Q º {ret_value = M₀*N₀}

 

1.1.iii)

b)Pc º {ret_value = 0 Ù i = 0 Ù n=N₀ Ù m=M₀}

  B º {i < f_abs n }

  I º {ret_value = m*i Ù 0 £ i £ (f_abs n) Ù n=N₀ Ù m=M₀}

  Fv = (f_abs n) - i

  Qc º {ret_value = (f_abs n) * m Ù n=N₀ Ù m=M₀}

 

1.1.iv)

Precondición y postcondición para la función abs:

P º {n=N₀}

Q º {ret_value = f_abs N₀}

 

1.2.i) a) P º {n=N₀ }

 

1.2.ii) c) Q º { (ret_value = f_primo(N₀) ) }

 

Ejercicio 2

 

2i)

function Potencia (n:integer,m:integer):integer

 

  var

    i:integer:=0;

 

ret_value:=1; // no hace falta declarar a retvalue porque se declara

              // automáticamente con el tipo declarado en la función

 

  while (i<m) do

    i:=i+1;

    ret_value:=retvalue*n;

  od;

 

endfunction

 

2ii)

function Factorial (n:integer):integer

 

  var

    i:integer:=0;

 

  ret_value:=1;

 

  while (i<n) do

    i:=i+1;

    ret_value:=ret_value*i;

  od;

 

endfunction

 

2iii) (2do cuat. 99)

function Fibonacci (n:integer):integer

 

  var

    i:integer:=1;

    j:integer:=0;

   

 ret_value:=1;

 

 if ((n==0) || (n==1)) then

    ret_value:=n;

  else

    while (i<n) do

      ret_value:=ret_value+j;

      j:=ret_value-j;

      i:=i+1;

    od;

  fi;

 

enfunction

 

2iii) Está mal la especificación

 

Ejercicio 3

 

a-vii) Pº{i=I₀ Ù n=N₀ Ù I₀>0 Ù (f_par(I₀)Þ N₀³0)}

a-ix) Qº{ret_value=f_raizEnesima I₀ N₀}

 

b-i) Pº{TRUE}

b-iv) Qº{ret_value=101}

 

Ejercicio 4

 

4-i) No concuerda.

     La guarda no coincide con lo que se encuentra adentro del while.

 

4-ii)

 

Código que respeta los estados: (hay un error en el I?)

 

function Hay_algun_cuadrado2 (n:integer, m:integer):bool

  var

    i:integer:=n;

 

  ret_value:=false;

 

  while (i<=m) do

    ret_value=(cuadrado?(i) Ú ret_value);

    i:=i+1;

  od;

 

Estados que respetan el código:

P º{ n = N₀ Ù m = M₀ }

Pc º { i=m Ù ret_valueºfalse Ù ((N₀>=M₀) => (n=N₀ Ù m=M₀ )) Ù

       ((N₀<M₀) => (n=M₀ Ù m=N₀)}

//I º { (ret_value º ($k)((n <= k < i - 1) Ù es_cuadrado(k))) Ù (n <= i <= m + 1)

  Ù n = N₀ Ù m = M₀ Ù N₀ <= M₀ }

B º ( i>n )

//Fv = m – i

//Qc º Q º{ ret_value º ($k)(( N₀ <= k <= M₀) Ù es_cuadrado?(k)) }

 

EL CODIGO NUNCA ENTRA AL CICLO

 

Ejercicio 5

 

5-a-i) No, pues el invariante está mal. No puede ser que antes de entrar al ciclo

       ret_value ya dé la suma.

5-a-ii) No, por la misma razón que i

5-a-iii) No, porque en el invariante aparece ret_value=ret_value+i lo cual no tiene

         sentido

5-a-iv) SI

 

5-b)

function SumMenMul (n:integer, m:integer)

 

  ret_value:=0;

 

  while (n>0) do

    if (es_mult(n,m) then

      ret_value:=ret_value+n;

    else

      skip;

    fi;

    n:=n-1;

  od;

 

endfunction   

 

5-c)SI

 

Ejercicio 6

 

6-i)

P º {n=N₀ Ù m=M₀ Ù M₀>0 Ù N₀³0}

Q º {ret_value=f_resto N₀ M₀}

Pc º {ret_value=N₀}

Qc º Q

B º {ret_value³m}

I º {(f_resto ret_value m = f_resto N₀ M₀) Ù (0≤ret_value≤n)}

Fv = (f_resto N₀ M₀) - ret_value

 

//resto:: Nat -> Nat -> Nat

//resto n d | (d==0) = error “No se puede dividir por 0”

//          | (n==0) = 0

//          | (n<d) = n

//          | (n==d) = 0

//          | otherwise = resto (n-d) d

 

function Resto (n:integer,m:integer):integer

 

  ret_value:=n;

 

  while (ret_value³m) do

    ret_value:=ret_value-m;

  od;

   

endfunction

 

6-ii)

P º {n=N₀ Ù m=M₀ Ù M₀>0 Ù N₀³0}

Q º {ret_value = f_division N₀ M₀}

Pc º {ret_value=0}

Qc º Q

B º {n³m}

I º {(f_resto n m = f_resto N₀ M₀) Ù (ret_value*m + n = N₀) Ù (0≤n≤N₀)}

Fv = n - (f_resto N₀ M₀)

 

//division:: Nat -> Nat -> Nat

//division n d = division2 n d 0

 

//division2:: Nat -> Nat -> Nat -> Nat

//division2 n 0 v = error "No sea bruto, no se puede dividir por cero."

//division2 0 d v = 0

//division2 n d v |(n<d) = v

//                |(n==d) = v+1

//                | otherwise = division2 (n-d) d (v+1)

 

function División_entera (n:integer,m:integer):integer

 

  ret_value:=0;

 

  while (n³m) do

    n:=n-m;

    ret_value:=ret_value+1;

  od; 

 

endfunction

 

 

 

 

 

 

 

 

 

6-iii)

P º {n=N₀ Ù m=M₀ Ù ⌐(N₀=0 Ù M₀=0) Ù (N₀³0) Ù (M₀³0)}

Q º {ret_value = f_mcd N₀ M₀}

Pc º P

Qc º {n=f_mcd N₀ M₀ Ù m=n}

B º {n¹m}

I º {f_mcd(N₀,M₀)=f_mcd(n,m) Ù (f_mcd(N₀,M₀)≤n≤N₀) Ù (f_mcd(N₀,M₀)≤m≤M₀)}

FV = (n+m) – 2*(f_mcd N₀ M₀)

 

//mcd:: Nat -> Nat -> Nat

//mcd 0 m = m

//mcd n 0 = n

//mcd n m = mcd m (resto n m)

 

 

function MCD (n:integer,m:integer):integer

 

  while (n¹m) do

    if (n>m) then

               n:=n-m;

             else

               m:=m-n;

  od;