Cruce de río con barco

Question

Alan, proyecto de Ley, Charly, Decano y Edgar se va a cruzar un río para llegar a la opuesta orilla del río mediante el uso de un pequeño barco. Las reglas son muy estrictas porque el río es profundo y peligroso: Para que el barco no se hunda, el 5 amigos deben estar sentados uno detrás de otro, empezando desde el más ligero, en orden de peso. Todos los amigos son de diferente peso! Todo lo que tienen con ellos es una balanza. Dado que su tiempo es limitado, se debe determinar el orden por el menor número de ponderaciones. Usted puede ayudar a ellos?

Comenzando con a+B determinamos AB. Dicen que tenemos $A>B$. A continuación, añadimos C y el peso en contra de, digamos, el más ligero. $B+C$. Si tenemos $C<B$$C<B<A$. Pero no podemos seguir con un enfoque simplista. Debe haber algo inteligente que me estoy perdiendo.

Answer 1

Juan M. el enfoque de la Clasificación de las Redes es el lugar para ir cuando usted desea ordenar una pequeña lista con el menor número de comparaciones. La selección de N=5 le da a esta lista de nueve pesajes a realizar:

SWAP(0, 1);
SWAP(3, 4);
SWAP(2, 4);
SWAP(2, 3);
SWAP(0, 3);
SWAP(0, 2);
SWAP(1, 4);
SWAP(1, 3);
SWAP(1, 2);

Aquí, el espacio de INTERCAMBIO(x,y) significa "Intercambiar x e y, si x pesa más de y".

Tenga en cuenta que usted no puede simplemente reemplazar $0$ con $A$, $1$ con $B$, etc, porque los números se refieren a las posiciones en la lista, no a la gente. Así que lo que tienes que hacer es esto: Hacer cinco tarjetas de memoria flash, con los números de $0,1,2,3,4$ escrito en ellos. Dar a todos una tarjeta. Entonces INTERCAMBIAR(x,y) significa:

Poner a los titulares de tarjetas de memoria flash x y y en la balanza. Si el titular de la tarjeta flash x pesa más que el titular de la tarjeta flash y, de tenerlos de intercambio de tarjetas.

Después de los nueve pesajes en la lista, tienen ellos de la línea en el orden de las cartas que tienen.