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])}

=>

{("j)(0≤j<i₃ => A₃[j]=A₀[j]+1) � ("j)(i₃≤j<dim(A) => A₃[j]=A₀[j])} 2

De 1 y 2 (E3 => I)

3)FV decreciente y acotada

FV₁=dim(A)-i₀

FV₃=dim(A)-i₀-1

Y está acotada en 0 pues 0≤i≤dim(A)

4) I � ⌐B =>? Qc

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

{i�dim(A)} =>? Qc

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

5) Qc => Q Es trivial

Ejercicio 4

4-i)

P � {A=A₀ � B=B₀ � C=C₀ � dim(A)=dim(B)=dim(C)}

Q � {A=A₀ � B=B₀ � ("j)(0≤j<dim(A) => C[j]=A[j]+B[j])}

Pc � {i=0} � P

Qc � {i=dim(A)} � Q

B � {i<dim(A)}

I � {0≤i≤dim(A) � ("j)(0≤j<i => C[j]=A[j]+B[j]) �

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

FV = dim(A)-i

procedure sumpoli

(in:A:arreglo de integer,in:B:arreglo de integer,out:C:arreglo de integer)

var

i:integer:=0;

while (i<dim(A)) do

C[i]:=A[i]+B[i];

i:=i+1;

od;

endfunction

4-ii)

P � {A=A₀ � B=B₀ � C=C₀ � dim(A)=dim(B)=((dim(C)-1)/2)}

Q � {A=A₀ � B=B₀ �

("j)(0≤j<2*dim(A)-1 => C[j]=f_coef_j_mult (A^dim(A)) (B^dim(B)) j)}

Pc � {i=0} � P

Qc � {i=dim(A)*2-1} � Q

B � {i<dim(A)*2-1}

I � {0≤i≤dim(A)*2-1 � ("j)(0≤j<i => C[j]=f_coef_j_mult (A^dim(A)) (B^dim(B)) j) �

("j)(i≤j<dim(A)*2-1 => C[j]=C₀[j]}

FV = dim(A)-i

type Polinomio = [Int]

coef:: Polinomio -> Int -> Int

coef pol i = i_esimo pol ((longitud pol-1)-i)

coef_j_mult:: Polinomio -> Polinomio -> Int -> Int

coef_j_mult p1 p2 j = sumar p1 p2 j 0

-- sumar es "sumar coeficientes de grado j cuando multiplico p1 por p2"

sumar:: Polinomio -> Polinomio -> Int -> Int -> Int

sumar p1 p2 j cont

| (j==cont) = (coef p1 j)*(coef p2 0)

| otherwise = (coef p1 cont)*(coef p2 (j-cont)) +

sumar p1 p2 j (cont+1)

procedure multpoli

(in:A:arreglo de integer,in:B:arreglo de integer,out:C:arreglo de integer)

var

i:integer:=0;

while (i<dim(A)*2-1) do

�C[i]:=Coef_j_mult(A,B,i);

i:=i+1;

od;

endfunction

//FUNCION AUXILIAR Coef_j_mult

P � {A=A₀ � B=B₀ � dim(A)=dim(B) � j=J₀}

Q � {ret_value=f_coef_j_mult (A^dim(A)) (B^dim(B)) J₀ � A=A₀ � B=B₀}

Pc � {cont=0 � ret_value=0} � P

B � {cont≤j}

Qc � {cont=j+1 � ret_value=f_sumar_n_veces A^dim(A) B^dim(B) j cont}

I � {0≤cont≤j+1 � ret_value=f_sumar_n_veces A^dim(A) B^dim(B) j cont

FV = j+1-cont

sumar_n_veces:: Polinomio -> Polinomio -> Int -> Int -> Int

sumar_n_veces p1 p2 j 0 = 0

sumar_n_veces p1 p2 j n = sumar p1 p2 j (j-n+1)

function Coef_j_mult (A:arreglo de integer,B:arreglo de integer,j:integer):integer

var

cont:integer:=0;

ret_value:=0;

while (cont≤j) do

ret_value:=ret_value+A[j-cont]*B[cont];

cont:=cont+1;

od;

endfunction

4-iii)

P � {A=A₀ � ⌐("j)(0≤j<dim(A) => A[j]=0) � x=X₀ � res=res₀}

Q � {res=f_evaluar A₀^dim(A) X₀}

Pc � {i=0 � res=0}

Qc � {i=dim(A) � res=f_evaluar (f_drop (A₀^dim(A)) (dim(A)-i)) X₀}

B � {i<dim(A)}

I � {0≤i≤dim(A) � res=f_evaluar (f_drop (A₀^dim(A)) (dim(A)-i)) X₀ � A=A₀ � x=X₀}

FV = dim(A)-i

grado pol = vergrado pol 0

vergrado:: Polinomio -> Int -> Int

vergrado pol i | (i_esimo pol i) == 0 = vergrado pol (i+1)

| otherwise = (longitud pol)-1-i

-- El polinomio nulo NO tiene grado

evaluar:: Polinomio -> Int -> Int

evaluar [] _ = 0

evaluar p x = ev_sumandos p x 0 (grado p)

ev_sumandos:: Polinomio -> Int -> Int -> Int -> Int

ev_sumandos p x i g

| (i==g) = (coef p i)*(x^i)

| otherwise = (coef p i)*(x^i) + ev_sumandos p x (i+1) g

procedure Evaluar(in:A:arreglo de integer,in:x:integer,out:res:integer)

var

i:integer:=0;

res:=0;

while (i<dim(A)) do

res:=res+A[i]*(x^i);

i:=i+1;

od;

endfunction

4-iv)

P � {A=A₀ � B=B₀ � C=C₀ � dim(A)=dim(B)=dim(C) � x=X₀ � res=res₀ �

⌐("j)(0≤j<dim(A) => A₀[j]+ B₀[j]=0)}

Q � {A=A₀ � B=B₀ � ("j)(0≤j<dim(A) => C[j]=A[j]+B[j]) �

res=f_evaluar C^dim(A) X₀}

procedure evsuma(in:A:arreglo de integer,in:B:arreglo de integer,in:C:arreglo de integer,in:x:integer,out:res:integer)

Sumpoli(A,B,C);

Evaluar(C,x,res);

endprocedure

Ejercicio 6

INTERPRETO QUE HAY QUE ORDENAR EL ARREGLO DE MENOR A MAYOR

6-i)

P � {A=A₀}

Q � {A^dim(A)=f_ordenar_crec A₀^dim(A)}

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

var

L:lista de integer;

L:=Ordenar(A);

List2Array(L,A);

Reverse(A);

endprocedure

//Procedimiento auxiliar List2Array

P � {L=L₀ � A=A₀ � dim(A)=f_long L₀}

Q � {L=L₀ � A^dim(A)=L₀}

Pc � {i=0 � L=L₀ � A=A₀}

Qc � {i=f_long L₀ � A^dim(A)=L₀}

B � {i<f_long L}

I � {0≤i≤f_long L₀ � L=L₀ � A^i=f_take L i}

FV = f_long L - i

Procedure List2Array (in:L:lista de integer,in-out:A:Arreglo de integer)

var

i:integer:=0;

while (i<Long(L)) do

A[i]:=Iesimo(L,i);

i:=i+1;

od;

endprocedure

// PROCEDIMIENTO AUXILIAR Reverse

P � {A=A₀}

Q � {("j)(0≤j<dim(A) => A[j]=A₀[dim(A₀)-j-1])}

Pc � {i=0 � L=A₀^dim(A) � L=L₀}

Qc � {i=dim(A) � ("j)(0≤j<i => A[j]=A₀[dim(A₀)-j-1])}

B � {i<dim(A)}

I � {(0≤i≤dim(A)) � ("j)(0≤j<i => A[j]=A₀[dim(A₀)-j-1]) �

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

Fv = dim(A)-i

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

var

i:integer:=0;

L:lista de integer;

L:=Array2List(A);

while (i<dim(A)) do

A[i]:=Iesimo(L,dim(A)-i-1);

i:=i+1;

od;

endfunction

6-ii)

P � {A=A₀}

Q � {A^dim(A)=f_burb_n_veces A₀^dim(A) (dim(A)-1)}

Pc � {i=0}

Qc � {i=dim(A)-1 � A^dim(A)=f_burb_n_veces A₀^dim(A) i}

B � {i<dim(A)-1}

I � {0≤i≤dim(A)-1 � A^dim(A)=f_burb_n_veces A₀^dim(A) i)

FV = dim(A)-1-i

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

var

i:integer:=0;

while (i<dim(A)-1) do

Burbujear(A);

i:=i+1;

od;

endprocedure

//PROCEDIMIENTO AUXILIAR BURBUJEAR

P � {A=A₀}

Q � {A^dim(A)=f_burbujear A₀^dim(A)}

Pc � {i=0}

I � {0≤i≤dim(A)-1 � A^dim(A)=f_burb_hta A₀^dim(A) i}

Qc � {i=dim(A)-1 � A^dim(A)=f_burb_hta A₀^dim(A) i}

B � {i<dim(A)-1}

FV = dim(A)-1-i

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

var

i:integer:=0;

while (i<dim(A)-1) do

Ordint(A[i+1],A[i]);

i:=i+1;

od;

endprocedure

Ejercicios 2-99

3i)

Ei � {tab=tab₀}

Ef � {ret_value=f_cant_casillas_negras tab₀}

Eic � {i=0 � ret_value=0}

Efc � {i=f_cant_filas tab₀ �

� ret_value=f_cant_casillas_negras_hasta_f tab₀ (f_cant_filas tab₀)}

B � {i<Cant_filas tab}

I � {ret_value=f_cant_casillas_negras_hasta_f tab₀ i � (0≤i≤f_cant_filas tab₀)}

Fv = Cant_filas tab - i

//cant_casillas_negras::Tab -> Int

//cant_casillas_negras tab = cant_casillas_negras_hasta_f tab (cant_filas tab)

//cant_casillas_negras_hasta_f::Tab -> Fila -> Int

//cant_casillas_negras_hasta_f _ 0 = 0

//cant_casillas_negras_hasta_f tab f

//| (f==1) = cant_casillas_negras_fila tab 1 1

//| ow = cant_casillas_negras_fila tab f 1 + cant_casillas_negras_hasta tab (f-1)

//cant_casillas_negras_fila::Tab -> Fila -> Columna -> Int

//cant_casillas_negras_fila tab f c

//| (c==cant_columnas tab) = cheq_negra tab f c

//| otherwise = cheq_negra tab f c + cant_casillas_negras_fila tab f (c+1)

//cheq_negra:: Tab -> Fila -> Columna -> Int

//cheq_negra tab f c | (color_casilla tab f c == Negro) = 1

// | otherwise = 0

function Cant_cas_negras(tab:Tablero):integer

var

i:integer:=0;

ret_value:=0;

while (i<Cant_filas tab) do

ret_value:=ret_value+ContarNegras (Fila(tab,i+1))

incrementar(i);

od;

endfunction

// Funcion auxiliar ContarNegras

Ei � {A=A₀}

Ef � {ret_value=f_contarnegras A₀^dim(A)}

Eic � {ret_value=0 � i=0}

Efc � {ret_value=f_contarnegras A₀^dim(A) � i=dim(A)}

B � {i<dim(A)}

I � {ret_value=f_contarnegras A₀^i � (0≤i≤dim(A))}

Fv = dim(A)-i

//contarnegras:: [Color] -> Int

//contarnegras [] = 0

//contarnegras (x:xs) | (color_casilla x == negro) = 1 + contarnegras xs

// | otherwise = contarnegras xs

function ContarNegras(A:arreglo de colores):integer

var

i:integer:=0;

ret_value:=0;

while (i<dim(A)) do

if (A[i]==negro) then

ret_value:=ret_value+1;

else

skip;

fi;

i:=i+1;

od;

endfunction

3ii)

Ei � {tab=tab₀}

Ef � {ret_value=f_cant_casillas_negras2 tab₀}

Eic � {i=0 � ret_value=0}

Efc � {i=f_cant_columnas tab₀ �

� ret_value=f_cant_casillas_negras_hta_c tab₀ (f_cant_columnas tab₀)}

B � {i<Cant_columnas tab}

I � {ret_value=f_cant_casillas_negras_hta_c tab₀ i � (0≤i≤f_cant_columnas tab₀)}

Fv = Cant_columnas tab - i

//cant_casillas_negras2::Tab -> Int

//cant_casillas_negras2 tab = cant_casillas_negras_hta_c tab (cant_columnas tab)

//cant_casillas_negras_hta_c::Tab -> Columna -> Int

//cant_casillas_negras_hta_c _ 0 = 0

//cant_casillas_negras_hta_c tab c

//| (c==1) = cant_casillas_negras_col tab 1 1

//| ow = cant_casillas_negras_col tab 1 c + cant_casillas_negras_hta_c tab (c-1)

//cant_casillas_negras_col::Tab -> Fila -> Columna -> Int

//cant_casillas_negras_col tab f c

//| (f==cant_filas tab) = cheq_negra tab f c

//| otherwise = cheq_negra tab f c + cant_casillas_negras_col tab (f-1) c

function Cant_cas_negras2(tab:Tablero):integer

var

i:integer:=0;

ret_value:=0;

while (i<Cant_Columnas tab) do

ret_value:=ret_value+ContarNegras (Columna(tab,i+1))

incrementar(i);

od;

endfunction

3iii)

Ei � {tab=tab₀}

Ef � {ret_value=f_cant_casillas_negras3 tab₀}

Eic � {f=0 � c=0 � ret_value=0}

Efc � {f=f_cant_filas tab₀ � c=f_cant_columnas tab₀ �

� ret_value=f_rec_hta_fc tab₀ f c}

B � {not(f==Cant_filas tab and c==Cant_columnas tab)}

I � {ret_value=f_rec_hta_fc tab₀ f c � (0≤f≤f_cant_filas tab₀) �

� (0≤c≤f_cant_columnas tab₀)}

Fv = ((Cant_filas tab)*(Cant_columnas tab))-(c+(f-1)*(Cant_columnas tab))

//Nota:(c+(f-1)*((Cant_columnas tab)-1)) convierte fila y columna en una posicion

//cant_casillas_negras3::Tab -> Int

//cant_casillas_negras3 tab = rec_hta_fc tab (cant_filas tab) (cant_columnas tab)

//rec_hta_fc::Tab -> Fila -> Columna -> Int

//rec_hta_fc _ 0 0 = 0

//rec_hta_fc tab f c

//| ((f==1)&&(c==1)) = cheq_negra tab f c

//| ow = cheq_negra tab f c + rec_hta_fc (antFil f) (antCol c)

//antFil:: Tablero -> Fila -> Columna -> Fila

//antFil tab f c | (c==1) = f-1

// | othwerwise = f

//antCol:: Tablero -> Columna -> Columna

//antCol tab c | (c==1) = cant_columnas tab

// | otherwise = c-1

function Cant_cas_negras3(tab:Tablero):integer

var

f:integer:=0;

c:integer:=0;

ret_value:=0;

while (not (f==Cant_filas tab and c==Cant_columnas tab)) do

if (Color tab (sigFil tab f) (sigCol tab c) == Negro) then

ret_value:=ret_value+1;

else

skip;

fi;

f:=sigFil tab f c;

c:=sigCol tab c;

od;

endfunction

//Funcion auxiliar sigFil

Ei � {tab=tab₀ � f=f₀ � c=c₀}

Ef � {(c₀=f_cant_columnas tab)�(f=f₀+1) ú (c₀<f_cant_columnas tab)�(f=f₀)}

function sigFil(tab:tablero,f:integer,c:integer):integer

if (c==Cant_columnas tab) then

f:=f+1;

else

skip;

fi;

endfunction
//Funcion auxiliar sigCol

Ei � {tab=tab₀ � c=c₀}

Ef � {(c₀=f_cant_columnas tab)�(c=1) ú (c₀<f_cant_columnas tab)�(c=c₀+1}

function sigCol(tab:tablero,c:integer):integer

if (c==Cant_columnas tab) then

c:=1;

else

c:=c+1;

fi;

endfunction

3iv)

Ei � {tab=tab₀ � Cant_filas tab₀�3 � Cant_columnas tab₀�3}

Ef � {ret_value=f_cantidad_cruces_negras tab₀}

Eic � {f=1 � c=1 � ret_value=0}

Efc � {f=(f_cant_filas tab₀)-1 � c=(f_cant_columnas tab₀)-1 �

� ret_value=f_cant_cruces_hta tab₀ f c}

B � {not(f==(Cant_filas tab)-1 and c==(Cant_columnas tab)-1)}

I � {ret_value=f_cant_cruces_hta tab₀ f c � (0≤f≤(f_cant_filas tab₀)-1) �

� (0≤c≤(f_cant_columnas tab₀)-1)}

Fv=(((Cant_filas tab)-1)*((Cant_columnas tab)-1))-(c+(f-1)*((Cant_columnas tab)-1))

//Nota:(c+(f-1)*((Cant_columnas tab)-1)) convierte fila y columna en una posicion

//cantidad_cruces_negras:: Tablero -> Nat

//cantidad_cruces_negras tab

// | (cant_filas tab) < 2 || (cant_columnas tab) < 2 = 0

// | otherwise = cant_cruces_hta tab (cant_filas tab)-1 (cant_columnas tab)-1

//cant_cruces_hta::Tab -> Fila -> Columna -> Int

//cant_cruces_hta _ 1 1 = 0

//cant_cruces_hta tab f c

//| ((f==2)&&(c==2)) = cheq_cruz tab f c

//| ow = cheq_cruz tab f c + cant_cruces_hta (antFil4 f) (antCol4 c)

//antFil4:: Tablero -> Fila -> Columna -> Fila

//antFil4 tab f c | (c==2) = f-1

// | othwerwise = f

//antCol4:: Tablero -> Columna -> Columna

//antCol4 tab c | (c==2) = cant_columnas tab

// | otherwise = c-1

//cheqcruz:: Tablero -> Fila -> Columna -> Nat

//cheqcruz tab f c | es_cruz tab f c = 1

| otherwise = 0

//es_cruz:: Tablero -> Fila -> Columna -> Bool

//es_cruz tab f c =

//(color_casilla tab f c == negro) && (color_casilla tab (f-1) c == negro) &&

//&& (color_casilla tab f (c-1) == negro) && (color_casilla tab f (c+1) == negro) &&

//&& (color_casilla tab (f+1) c == negro)

function Cant_cruces_negras(tab:tablero):integer

var

f:integer:=1;

c:integer:=1;

ret_value:=0;

while (not(f==(Cant_filas tab)-1 and c==(Cant_columnas tab)-1)) do

if (Es_centro_cruz tab (f+1) (c+1)) then

ret_value:=ret_value+1;

else

skip;

fi;

f:=sigFil tab f c;

c:=sigCol tab c;

od;

endfunction

//Funcion auxiliar Es_centro_cruz

Ei � {tab=tab₀ � f=f₀ � c=c₀ � Cant_filas tab₀�3 � Cant_columnas tab₀�3 �

� 2≤f₀≤((f_cant_filas tab₀)-1) � 2≤c₀≤((f_cant_columnas tab₀)-1)}

Ef � {(f_Color tab₀ f₀ c₀ == Negro) � (f_Color tab₀ f₀-1 c₀ == Negro) �

� (f_Color tab₀ f₀ c₀-1 == Negro) � (f_Color tab₀ f₀ c₀+1 == Negro) �

� (f_Color tab₀ f₀+1 c₀ == Negro)}

function Es_centro_cruz(tab:tablero,f:integer,c:integer):bool

if ((Color tab f c == Negro) � (Color tab f-1 c == Negro) �

(Color tab f c-1 == Negro) � (Color tab f c+1 == Negro) �

(Color tab f+1 c == Negro)) then

ret_value:=True;

else

ret_value:=False;

fi;

endfunction

Ejercicio práctica)

Tengo dos arreglos de enteros A y B, con dim(A)>dim(B), y quiero devolver un arreglo con la dimensión de A y que cumpla que:

1)hasta la posicion (dim(B)-1) sumar los elementos de A con los de B

Ei � {dim(A)>dim(B)}

Eic1 � {i=0}

Efc1 � {i=dim(B) � ("j)((0≤j<dim(B)) => (ret_value[i]=A[j]+B[j]))}

B1 � {i<dim(B)}

I1 � {(0≤i≤dim(B)) � ("j)((0≤j<i) => (ret_value[i]=A[j]+B[j]))}

Fv1 = dim(B)-i

Eic2 � Efc1

Efc2 � {i=dim(A) � ("j)((dim(B)≤j<dim(A)) => (ret_value[j]=A[j])) �

� ("k)((0≤k<dim(B)) => (ret_value[k]=A[k]+B[k]))}

B2 � {i<dim(A)}

I2 � {(dim(B)≤i≤dim(A)) � ("j)((dim(B)≤j<i) => (ret_value[j]=A[j])) �

� ("k)((0≤k<dim(B)) => (ret_value[k]=A[k]+B[k]))}

Fv2 = dim(A)-i

Ef � Efc2

function Sumarreglos(A:arreglo de int,B:arreglo de int):arreglo[0..dim(A)-1] de int

var

i:integer:=0;

while (i<dim(B)) do

ret_value[i]:=A[i]+B[i];

i:=i+1;

od;

while (i<dim(A)) do

ret_value[i]:=A[i];

i:=i+1;

od;

endfunction

//Otra forma (con un solo ciclo en vez de dos)

Ei � {dim(A)>dim(B)}

Eic � {i=0}

Efc � {i=dim(A) � ("j)((dim(B)≤j<dim(A)) => (ret_value[j]=A[j])) �

� ("k)((0≤k<dim(B)) => (ret_value[k]=A[k]+B[k]))}

B � {i<dim(A)}

I � {(0≤i≤dim(A)) � ("j)((dim(B)≤j<i) => (ret_value[j]=A[j])) �

� ("k)((0≤k<min(i,dim(B))) => (ret_value[k]=A[k]+B[k]))}

Fv = dim(A)-i

Ef � Efc

function Sumarreglos1(A:arreglo de int,B:arreglo de int):arreglo[0..dim(A)-1] de int

var

i:integer:=0;

while (i<dim(A)) do

if (i<dim(B)) then

ret_value[i]:=A[i]+B[i];

else

ret_value[i]:=A[i];

fi;

i:=i+1;

od;

endfunction

Ejercicio práctica)

Ei � {A=A₀}

Ef � Efc

Eic � {i=0}

Efc � {i=dim(A) � ("j)((0≤j<dim(A)) => (ret_value[j]:=2*A[j]))}

B � {i<dim(A)}

I � {(0≤i≤dim(A)) � ("j)((0≤j<i) => (ret_value[j]:=2*A[j]) �

� ("k)((i≤k<dim(A)) => (A[k]=B[k]))}

Fv = dim(A)-i

function Multpor2(A:arreglo de integer):arreglo[0..dim(A)-1] de integer

var

i:integer:=0;

while (i<dim(A)) do

ret_value[i]:=2*A[i];

i:=i+1;

od;

endfunction

Ejercicio de la Practica)

Ei � {A=A₀ � (0≤n<dim(A)) � (0≤m<dim(A))}

Ef � {A[n]=A₀[m] � A[m]=A₀[n] � ("i)(((0≤i<dim(A)) � i�n � i�m) => (A[i]=A₀[i])}

Procedure Swap(inout:A:arreglo de integer,in:n:integer,in:m:integer)

var

aux:integer:=A[n];

A[n]:=A[m];

A[m]:=aux;

endprocedure