algoritmos

1) Algoritmo de Euclides
Sean a1 y a2 dos numeros enteros positivos. Queremos hallar el maximo comun divisor (mcd). Suponemos que contamos con la funcion binaria a2|a1 que nos da el resto dedividir a1 por a2. El algoritmo de Euclides halla el mcd de la siguiente manera:
a3=a2|a1 si a3=0 entonces a2 es el mcd, si no
a4=a3|a2 si a4=0 entonces a3 es el mcd, si no
...
aN=aN-1|aN-2 si aN=0entonces aN-1 es el mcd

Programa
mcd( a1, a2)
a3=1
while a30 do
a3= a2| a1
if a3>0 then
a1=a2
a2=a3
else
return a2
end
end

2) Criba de Eratostenes
Sea N un numero natural mayor que2. Se trata de hallar todos los numeros primos menores o iguales a N. Supongamos que contamos con la funcion binaria A MENOS B que resulta en los elementos de A que no estan en B donde A y B son doslistas de numeros. El metodo de Eratostenes nos da dichos primos de la siguiente manera

Sea L=2,3,....,N
Sustraer de L todos los multiplos de 2 resultando L1
Guardar 2 en la lista P
Sustraer de L1todos los numeros multiplos del primer numero en L1
Guardar el primer numero de L1 en la lista P
Continuar hasta que Ln es vacia.

Programa
Erato (L)
M=P=
while L do
p= L[1]
for i=1,long (L) do
M=M,ip
end
L=L MENOS M
M=Æ
P=P, p
end
return P

Ejercicio Hacer un programa para A MENOS B
Ejercicio Hacer un programa para long (L)= cantidad de numeros en la lista L

3)Ordenar una sucesion de numeros.
Sea L= a1, a2,..., aN una lista de N numeros. Queremos ordenarlos de menor a mayor. Procedemos de la siguiente manera:

Comparamos a1 y a2 y los intercambiamos delugar si a2L[i+1] then
t=L[i]
L[i]=L[i+1]
L[i+1]=t
end
end
end

4) Multiplicar dos matrices
Sean A y B dos matrices de n por n. Se trata de hallar la matriz C tal que

Programa
Amult B
C= matriz de nxn
for i=1 to n do
for j=1 to n do
c=0
for k=1 to n do
c=c+a[i,k]b[k,j]
end
c[i,j]=c
end
end

5) Algoritmo search
Sea G=(V,E) un grafo y sV un vertice....