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 5

 

Ejercicio 2

 

La longitud de L es Par

 

Para todas las posiciones pares de L, sucede que hay un elemento en L₀ que es igual a cada elemento de L y para todos los elementos de L₀, sucede que hay un elemento en las posiciones Pares de L, que es igual a cada elemento de L₀.

 

Todas las posiciones pares de L son diferentes entre si.

 

Para todas las posiciones pares de L sucede que en la sig. posicion aparece la cantidad de apariciones de L₀.

 

2-a) El procedimiento pone en las posiciones pares los elementos de L₀ y en las impares la cantidad de veces que aparece cada elemento en L₀.

 

2-b-i) Podria pasar que no estén todos los elementos de L₀ puestos en L.

2-b-ii) Podria pasar que estén todos los elementos pero que haya repetidos.

2-b-iii) Podria pasar que la lista quede impar, con lo cual quedaria un elemento en la ultima posicion y no estaria la cantidad de veces que aparece en la lista original (y se seguria cumpliendo Q)

 

Ejercicio 3

 

3-i)

P º {n=N₀}

Q º {n=N₀+1}

 

Procedure Incrementar(in-out:n:integer)

 

  n:=n+1;

 

endprocedure

 

3-ii)

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

Q º {(N₀³M₀ Ù n=N₀ Ù m=M₀) Ú (N₀<M₀ Ù n=M₀ Ù m=N₀)}

 

Procedure Ordint (in-out:n:integer,in-out:m:integer)

 

  if (n³m) then skip;

           else Swap(n,m);            

  fi;

 

endprocedure

 

//PROCEDIMIENTO AUXILIAR Swap

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

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

 

Procedure Swap(in-out:n:integer,in-out:m:integer)

 

  var

    tmp:integer:=n;

 

  n:=m;

  m:=tmp;

 

endprocedure

 

3-iii)

P º {n=N₀}

Q º {(Par(N₀)Ù(n=N₀/2)) Ú (⌐Par(N₀) Ù n=N₀)}

 

Procedure Divpar(in-out:n:integer)

 

  if (Resto(n,2)=0) then

    n:=Division_entera(n,2);

  else

    skip;

  fi;

 

endfunction

 

3-iv)

P º {p=P₀ Ù q=Q₀ Ù r=R₀}

Q º {p=(P₀+Q₀+R₀)*P₀ Ù q=Q₀ Ù r=R₀}

 

procedure ej3iv (in-out:p:integer,in-out:q:integer,in-out:r:integer)

 

  p:=(p+q+r)*p;

 

endprocedure

 

3-v) VERSION 1

P º {A=A₀}

Q º {A^dim(A)=f_incrementa A₀^dim(A)}

Pc º {i=0}

Qc º {i=dim(A) Ù A^dim(A)=f_incrementa_hasta (A₀^dim(A)) dim(A)}

B º {i<dim(A)}

I º {A^dim(A)=f_incrementa_hasta (A₀^dim(A)) i Ù (0≤i≤dim(A))}

Fv = dim(A)-i

 

//incrementa::[Int]->[Int]

//incrementa [] = []

//incrementa (x:xs) = (x+1):incrementa xs

 

//incrementa_hasta::[Int]->Int->[Int]

//incrementa_hasta [] _ = []

//incrementa_hasta (x:xs) n | (n==0) = x:xs

//                          | otherwise = (x+1):(incrementa_hasta xs (n-1))

 

procedure Incrementa(in-out:A:arreglo de integer)

 

  var

    i:integer:=0;

 

  while (i<dim(A)) do

    incrementar(A[i]);

    incrementar(i);

  od;

 

endprocedure

 

 

3-v) VERSION 2

P º {A=A₀}

Q º {("i)(0≤i<dim(A) => A[i]=A₀[i]+1)}

Pc º {i=0}

Qc º {i=dim(A)} Ù Q

B º {i<dim(A)}

I º {0≤i≤dim(A) Ù ("j)(0≤j<i => A[j]=A₀[j]+1) Ù ("j)(i≤j<dim(A) => A[j]=A₀[j])}

Fv = dim(A)-i

 

procedure Incrementa(in-out:A:arreglo de integer)

 

  var

    i:integer:=0;

 

  while (i<dim(A)) do

    incrementar(A[i]);

    incrementar(i);

  od;

 

endprocedure

 

Demostraciones

 

1)     Pc =>? I

 

{i=0} =>? {0≤i≤dim(A) Ù ("j)(0≤j<i => A[j]=A₀[j]+1) Ù

           ("j)(i≤j<dim(A) => A[j]=A₀[j])}

 

{0≤0≤dim(A) Ù ("j)(0≤j<0 => ...) Ù ("j)(0≤j<dim(A) => A[j]=A₀[j]}

      T     Ù        ( F  =>  ¿)  Ù                 A=A₀  

      T     Ù               T     Ù                  T

 

2)IÙB en c/iteración

 

IÙB º {i<dim(A) Ù 0≤i≤dim(A) Ù ("j)(0≤j<i => A[j]=A₀[j]+1) Ù

       ("j)(i≤j<dim(A) => A[j]=A₀[j]) }

E1 º {i=i₁ Ù A=A₁ Ù i₁<dim(A) Ù 0≤i₁≤dim(A) Ù ("j)(0≤j<i₁ => A₁[j]=A₀[j]+1) Ù

      ("j)(i₁≤j<dim(A) => A₁[j]=A₀[j])}

 

E2 º {i₂=i₁ Ù A₂[i₂]=A₁[i₂]+1 Ù ("j)(j¹i₂ Ù 0≤j<dim(A) => A₂[j]=A₁[j])}

 

E3 º {i₃=i₂+1 Ù A₃=A₂}

 

QPQ E3 => I

 I º {0≤i≤dim(A) Ù ("j)(0≤j<i => A[j]=A₀[j]+1) Ù ("j)(i≤j<dim(A) => A[j]=A₀[j])}

 

{i₃=i₁+1 Ù 0≤i₁<dim(A)} => {0≤i₃≤dim(A)} 1

 

{A₂[i₁]=A₁[i₁]+1 Ù ("j)(j¹i₁ Ù 0≤j<dim(A) => A₂[j]=A₁[j]) Ù

("j)(0≤j<i₁ => A₁[j]=A₀[j]+1) Ù ("j)(i₁≤j<dim(A) => A₁[j]=A₀[j])}