Algoritmos
Páginas: 3 (703 palabras)
Publicado: 16 de mayo de 2015
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 de dividira1 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=0 entoncesaN-1 es el mcd
Programa
mcd( a1, a2)
a3=1
while a30 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 que 2. Se trata de hallartodos 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 dos listas de numeros. Elmetodo 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 L1 todos los numerosmultiplos 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 MM=Æ
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 de lugar si a2
Como resultado obtenemos una lista L2 donde el maximo numero de L ocupa el ultimo lugar deL2.
Repetimos el mismo procedimiento y obtenemos una lista L3 donde los dos ultimos dos numeros son los dos mayores numeros de L. Repetimos el procedimiento N – 1 veces.
Programa
ordenar (L)
N= long...
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 de dividira1 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=0 entoncesaN-1 es el mcd
Programa
mcd( a1, a2)
a3=1
while a30 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 que 2. Se trata de hallartodos 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 dos listas de numeros. Elmetodo 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 L1 todos los numerosmultiplos 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 MM=Æ
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 de lugar si a2
Como resultado obtenemos una lista L2 donde el maximo numero de L ocupa el ultimo lugar deL2.
Repetimos el mismo procedimiento y obtenemos una lista L3 donde los dos ultimos dos numeros son los dos mayores numeros de L. Repetimos el procedimiento N – 1 veces.
Programa
ordenar (L)
N= long...
Leer documento completo
Regístrate para leer el documento completo.