grafos

Universidad de Guadalajara
Centro universitario de ciencias exactas e ingenierías

Actividad 11

Materia:Algoritmia

Alumno: Toledo Nares Dario Iván

1. Dado un conjunto de puntos en el planocartesiano (x, y ) el problema es encontrar
aquellos dos puntos que se encuentran as cerca el uno del otro.
distanciaMinima(P[])
dmin = distMax
pasada = 1
mergeSort(P, 1, length(P[]))
pasada = 2mergeSort(P, 1, length(P[]))
return(p1,p2)
mergeSort(P[], izq, der)
if izq < der
med = (der+izq)/2
if pasada = 2
xMedio = P[med].x
mergeSort(P, izq, med)
mergeSort(P, med+1, der)
merge(P,izq,med,der)
if pasada =2
for i = izq to der
if | P[i].x - xMedio | < dmin
for j = i + 1 der
if | P[j].x - xMedio | < dmin
dist = distancia(P[i],P[j])
if dist < dmin
dmin = dist
p1 = P[i]
p2 = P[j]
Fin mergeSort
merge(P[],izq, med, der)
for i = izq to med
temp[i] = P[i]
for j = med to der
temp[der+med-j] = P[j++]
i = izq
for k = izq to der
if pasada = 1
p = (temp[i].x < temp[j].x)? temp[i++] : temp[j--]
else
p =(temp[i].y < temp[j].y)? temp[i++] : temp[j--]
P[k] = p
Fin merge

2. Cuenta la leyenda que en un templo hay tres varillas de diamante con 64 discos
ordenados de mayor a menor en la primera, y que unosmonjes están encargados de mover
los discos a otra varilla. Las reglas para mover los discos son que solamente se pueden
mover de uno en uno y que nunca puede haber un disco grande sobre uno maspequeño.
Según la leyenda, el mundo se acabara el dia que los monjes terminen de mover los discos.
Diseña un algoritmo para resolver el problema. Determina su eficiencia.
poste[3]
void hanoi(int n, int A, intB, int C)
if(n>1)
hanoi(n-1,A,B,C)
mueveDisco(A,B)
hanoi(n-1,A,B,C)
else
mueveDisco(A,B)
T(n) = a, n = 0
T(n) = b + 2T(n-1)
Llamadas

T(n)

1

b + 2T(n-1)

2

3b + 4T(n-2)

k

(2k-1)b + 2kT(n-k)

k=nT(n-k) = T(0) = a
T(n) = (2k – 1)b + 2ka = (a+b)2k – b
T(n)= Θ(2k )

3. Encontrar la manera de colocar ocho reinas sobre un tablero de ajedrez, de tal forma que
ninguna amenace (pueda comerse) a...