Problemilla interesante

[DjSonyk]

Por cierto el libro en cuestion se llama The Pattern on the Stone.
en el capitulo trata del tema

En el capítulo 2, Hillis nos muestra como con las puertas lógicas Y, O y NO, un conjunto de construcción universal, puede implementarse cualquier secuencia de reglas. Cualquier función representable como una tabla entrada-salida de ceros y unos puede implementarse a través de este reducido conjunto de operadores lógicos. El autor diserta sobre números binarios, código ASCII, coma flotante y unidades aritméticas. A través de las máquinas de estado finito nos introduce a las memorias, a los bloques lógicos denominados registros. Para acabar hablando de la velocidad de reloj, los límites de las "máquinas de estado finito y el problema del pelotón de fusilamiento que le propuso su mentor Marvin Minsky al que dedica el libro".

[SplinterGU]

Por cierto el libro en cuestion se llama The Pattern on the Stone.
en el capitulo trata del tema

En el capítulo 2, Hillis nos muestra como con las puertas lógicas Y, O y NO, un conjunto de construcción universal, puede implementarse cualquier secuencia de reglas. Cualquier función representable como una tabla entrada-salida de ceros y unos puede implementarse a través de este reducido conjunto de operadores lógicos. El autor diserta sobre números binarios, código ASCII, coma flotante y unidades aritméticas. A través de las máquinas de estado finito nos introduce a las memorias, a los bloques lógicos denominados registros. Para acabar hablando de la velocidad de reloj, los límites de las "máquinas de estado finito y el problema del pelotón de fusilamiento que le propuso su mentor Marvin Minsky al que dedica el libro".

eso si tiene buena pinta, lastima que no encuentro mas textos que el que enuncias... a ver si aparece algo en ingles...

[DCelso]

Yo creo que queda claro que el enunciado debe decir algo como que los soldados no conocen a priori el número de soldados que son, es decir no vale usar n como variable que todos conocen, esto es la forma de independizar el sistema del número de soldados, (pero sí que la pueden calcular preguntándose).

Además veo un poco contradictorio que no puedan calcular el número de soldados y que sí puedan pasarse infinitas entradas ( ya que dice el enunciado que pueden reducirse a una), pues entonces mandamos tantas entradas como necesitemos para enviar n una vez calculada por el último soldado ¿no?

De todas formas si no pueden contar, la otra solución es la de mandarse los ids que deben ser únicos y para ello este id debe de ser capaz como mínimo de alvergar N (número de soldados) ids diferentes así que dependencia con N por narizes debe de haber directa o indirectamente.

Así mismo el contar la mitad, ya vuelve a hacer el sistema dependiente de N, N/2 es relación directa con N. Veo un tanto en cuanto raro que seamos capaces de guardar N/2 y no N, es decir, N puede ser lo grande que quieras así que si produces overflow con N el doble de éste porducirá con N/2 el overflow. Hablando con números si n = 10, y no puedes guardarlo entonces que pasa si n = 20, n/2 es 10 y no puedes guardarlo.

En cuanto a la solución de splinter, no entendí el truco de los frames, a ver un sistema real de biestables síncronos, contadores, y demás cosas, dependen de un reloj en golpes ascendentes, es decir, tienen una patilla por la que le llega una señal cuadrada y cuando pasa del valor más bajo al mas alto, se produce el cambio en estos, es justo el momento en el que hacen lo que tienen que hacer, leer entradas, calcular cosas que consuman un tiempo y cambiar datos. Así que eso es justo lo que es un frame, no veo el porqué tener que hacer un sistema en que cada frame solo responda uno, en la realidad todos los soldados son independientes y deben de hacer lo que deban justo cuando se los dice el reloj así que esto debe ser ejecución en paralelo, además sino a ver como haces que disparen todos a la vez en el mismo frame si cada uno va respondiendo frame a frame. Irian al final todos los disparos desfasados en un frame, de ahí el tener que hacer un "raro"(por no decir otra cosa más fea :D) bucle de sincronización que salta las reglas del enunciado :)

[DjSonyk]

aqui podemos sacar algo en conclusion sobre todo quien sepa bastante de ingles http://portal.acm.org/citation.cfm?id=568278

el problema:

In this paper we improve the bounds on the complexity of solutions to the firing squad problem, also known as the firing synchronization problem. In the firing synchronization problem we consider a one-dimensional array of n identical finite automata. Initially all automata are in the same state except for one automaton designated as the initiator for the synchronization. Our results hold for the original problem, where the initiator may be located at either endpoint, and for the variant where any one of the automata may be the initiator, called the generalized problem. In both cases, the goal is to define the set of states and transition rules for the automata so that all machines enter a special fire state simultaneously and for the first time during the final round of the computation. In our work we improve the construction for the best known minimal-time solution to the generalized problem by reducing the number of states needed and give non-minimal-time solutions to the original and generalized problem that use fewer states than the corresponding minimal-time solutions.

[SplinterGU]

el frame representa un instante... varios soldados no pueden recibir la orden en 1 unico instante (o ciclo de reloj), por eso es que es 1 por frame... esto es como que en cada ciclo de reloj se ejecuta la operacion de comunicar a 1 soldado, pensa que le esta diciendo al oido uno a otro "dispara"... esto es solo en el caso de transmitir el mensaje, en todo otro caso, no hay esta limitacion... sin esta limitacion, la señal se transmitiria en 1 solo ciclo a todos los soldados y todos dispararian en el primer turno, y no seria necesario ningun tipo de sincronizacion... adjunto ejemplo (nota adicional, se agrega prioridad, para indicar el orden de ejecucion de los soldados, ya que segun como bennu ordena en memoria los procesos no seria posible hacer una comunicacion en fila).

Code Select Expand


import "mod_say";

#define N 150

global
int turno;
soldado soldado_actual;
soldado soldado_anterior;
soldado soldado_primero;
int i;
int soldados_que_dispararon = 0;
   comunicacion_para_este_turno_consumida = 0;
end

#define STATE_WAIT_ORDER      0
#define STATE_WAIT_CONFIRM    1
#define STATE_COUNTDOWN       2
#define STATE_FIRE            3

process soldado(int num)
public
   fire;
   soldado snext;
   soldado sprev;

private
   state = STATE_WAIT_ORDER;
   counter = 0;
   ready_to_fire = 0;

begin

   priority = ( N + 1 ) - i ;

while(!ready_to_fire)
   switch ( state )
           case    STATE_WAIT_ORDER:
//            if ( !comunicacion_para_este_turno_consumida )
                   if ( fire )
                       if ( snext )
                           snext.fire = 1;
                           state = STATE_WAIT_CONFIRM;
                       else
                           sprev.fire = 1;
                           state = STATE_COUNTDOWN; /* Me autoconfirmo, soy el ultimo */
                       end
                       counter = turno;
                       fire = 0;
                       comunicacion_para_este_turno_consumida = 1;
                   state = STATE_FIRE;
                   end
//                end
           end
       case    STATE_WAIT_CONFIRM:
           if ( !comunicacion_para_este_turno_consumida )
               if ( fire )
                       if ( sprev )
                           sprev.fire = 1;
                       end
                       fire = 0;
                       state = STATE_COUNTDOWN;
                       comunicacion_para_este_turno_consumida = 1;
                   end
               end
           end
           case    STATE_COUNTDOWN:
           counter--;
           if ( counter < 0 )
                   state = STATE_FIRE;
           end
           end
       case    STATE_FIRE:
           ready_to_fire = 1;
           end
       end
       frame;
   end

   say ( "turno: " + turno + " soldado "+ num + " fire!");
   soldados_que_dispararon++;

end

begin

//Crear los soldados
soldado_anterior = 0;

// crea soldados y los linkea
for(i = 0; i < N; i++)
soldado_actual = soldado(i);
if ( soldado_primero == 0 )
   soldado_primero = soldado_actual;
end

   soldado_actual.sprev = soldado_anterior;
   soldado_actual.snext = 0;

if ( soldado_anterior )
   soldado_anterior.snext = soldado_actual;
end

soldado_anterior = soldado_actual;

end

   // doy la orden de disparar
   soldado_primero.fire = 1;

// espero que todos hayan completado, solo por mantener el contador de turnos
while( soldados_que_dispararon < N )
       comunicacion_para_este_turno_consumida = 0;
   turno++;
frame;
end

   say( "total de soldados en la fila = " + N );
   say( "total de soldados que dispararon = " +  soldados_que_dispararon );

end


prestar atencion en que en este caso cuando recibe la señal de fuego, se pasa directo al estado disparar, y todos los soldados lo hacen sincronizados en el mismo ciclo, esto se debe a que no tiene la limitacion de 1 mensaje por ciclo de reloj/instante de tiempo.

Saludos.

agrego que en este ejemplo, no se conoce la cantidad de soldados.

[DjSonyk]

Aqui podeis bajaros el libro en ingles y PDF,yo en este ordenador no me deja intalar el acroba reader por no tener el pack2 ya me contareis se supone que esta en el capitulo 2

www.cs.rutgers.edu/~mdstone/class/503/readings/hillis-pattern.pdf

[SplinterGU]

aca va la solucion real... hay que leer, esta en ingles, y pesado...

http://facweb.cs.depaul.edu/asettle/research/papers/sirocco02.pdf

aca menciona 2 soluciones, una es dividiendo el array por 2, en sucesivas llamadas, pero parece que aca se conoce la cantidad de elementos en el anillo, igual hay que leerlo bien... es un poco largo, si alguien lo lee, y da una explicacion esta interesante...

saludos.

otra cosa, hay varios iniciadores, 2 por lo menos...

[SplinterGU]

bien, empezamos a aclarar la cuestion...

los papers aclaran un poco mas el problema y dan los datos que faltaban... paso a comentar:

1) no es una fila, es un anillo... esto quiere decir, que el primero se enlaza con el ultimo y a la inversa
2) se arranca con 2 señales que van circulando 1 para un lado y otra para el otro y ahi es como al colicionar se detectan medios... pero nada que ver con pares e impares.

si es necesario, luego hare un ejemplo...

por otro lado, hay otro metodo que no es nada optimo que trabaja sobre el peloton en forma de array, y va dividiendo al mismo de 2 en 2, de forma recursiva... en este caso se arranca con un solo iniciador que debe ser ubicado al final del array (para saber la cantidad de automatas o soldados)... por ende, se cuentan...

hay otro caso donde el iniciador empieza en 1, y va sumandose (se cuenta tambien)... bueno, hay varios, lo lei un poco por arriba los ultimos... la primera me parece la mejor... un anillo con 2 señales iniciales que luego se van incrementando a medida que colisionan...


gracias DjSonyk por la informacion!

[HaCkZJuaNN]

disculpa pero la solucion no puede ser... y creo que ya te estaras dando cuenta que todos te estamos diciendo que la solucion es genial para que no te lo tomes a personal... lo mismo me suena a tu profesor, ya he escuchado a muchos que por no entender algo y no quedar mal te dicen "si, es una buena opcion, pero no la mejor...", asi que si tu profesor no te dio la solucion a tu pregunta, no cuenta...

Nono, mi profesor conocía este problema de antes, y si la solución oficial se conoce(está demostrado que existe, pero como ya expliqué puede ser que aunque exista, no se conozca), seguramente él la conozca. El lunes le pregunto.

1) como sabes cual es la mitad, si los soldados no cuenta? (como puedes decir que los soldados cuentan en un caso y en otro no? cuentan o no cuenta...)
2) por otro lado, como obtienes un centro cuando la cantidad de soldados es par? si es impar ok... en 3 el centro es el del medio, pero en 4 soldados?
3) partiendo de que el primer soldado envia una señal inicial, en que momento la señal en circulacion pasa de ser 1 señal a ser 2? y cuando pasa a ser mas de 2?

saludos.

Así es más fácil de explicar ;) Gracias por plantearlo así.

Voy a empezar respondiendo a la pregunta 3, porque afecta a las otras 2.

3) Te voy a demostrar que si los soldados se pueden comunicar de manera finita y predeterminada(NO DEPENDIENTE DEL NÚMERO DE SOLDADOS), es exactamente lo mismo decir que pueden enviarse 1 señal a que pueden enviarse 2 a que pueden enviarse todas las que quieran, siempre y cuando el número de señales que manden no dependa del número de soldados.

Supongamos que sólo pueden enviarse 1 señal de uno a otro. Pues bien, si yo quiero hacer que se manden 2 señales, que supongamos tienen 20 posibles valores cada una(0..19 por ejemplo), lo único que tengo que hacer es combinarlas en una sola, de forma que el valor de la señal que mandan es 20*s1+s2. Así, para cada valor que le llega, el soldado lo vuelve a descomponer, tomando la división entera por 20 y el resto por 20 como las 2 señales que el otro soldado intentaba mandarle.

Lo que quiero decir es que si me puedo comunicar, te puedo comunicar cualquier número de cosas como una sola. Qué más me da a mi decirte: "hola" y después "splinter" que decirte "hola splinter" todo seguido. Si los dos conocemos el modo de codificarlo y la codificación es exacta(cada señal única está asociada a una pareja de señales única), entonces no hay problema.

Por tanto, da igual si hay una señal o varias, porque son equivalentes, siempre que no dependa del número de soldados. Por tanto, pienso con varias señales y si después el hardware me exige hacerlo con 1 sola, pues la codifico. Conceptualmente son equivalentes

1) Esa es la gracia del algoritmo y donde está toda la chicha. El tema es que, ya habiéndote explicado que varias señales son equivalentes a una sola, vamos a pensarlo con varias señales(es mucho más fácil de entender), y ya luego lo codificaríamos como fuera.

El primer soldado manda 2 señales.

La primera señal funciona así:

Tiene 2 valores: 1 y -1(y 0 que significa que no hay señal, si esa entrada es 0 el soldado no hace nada).

El primer soldado manda un 1 al siguiente para empezar el algoritmo.

Cada soldado, si NO es UN último(voy asignando varios soldados como últimos a lo largo del algoritmo, para dividir los subgrupos), si recibe un 1 del anterior, manda un 1 al siguiente al siguiente turno. Básicamente, la señal va avanzando un soldado cada turno. Además, si recibe un -1 del siguiente, manda un -1 al anterior. Los soldados de en medio solamente van retransmitiendo lo que les llega cada turno

Si el soldado ES un último, entonces si le llega un 1 del anterior, como no tiene siguiente, "REBOTA" la señal y manda un -1 al anterior.

De este modo(dibújaroslo en un papel si queréis), la señal va avanzando un soldado cada turno hasta que llega al último y rebota, retrocediendo un soldado cada turno también.

La segunda señal funciona así:

Tiene 3 valores: 1, -1 y 2(y 0 que significa que no hay señal, los soldados no hacen caso de esta)

El primer soldado manda un 1 al siguiente para empezar el algoritmo.

Cada turno, si el soldado NO es UN último, hace esto:
-Si le llega un 1 del anterior, al siguiente turno manda un -1 a ese mismo anterior.
-Si le llega un -1 del siguiente, manda un 2 a ese mismo siguiente.
-Si le llega un 2 del anterior, manda un 1 al siguiente.

De esta forma, la señal va avanzando 2 y retrocediendo 1, de media avanzando 1 cada 3 turnos.

Esta señal nunca llega hasta un último. Luego veréis por qué. No es que yo lo defina, es que en la manera en que funciona el algoritmo es imposible que llegue hasta un último. Por tanto siempre va hacia la derecha además.

Ahora, por supuesto, el primero en el segundo turno ya no manda nada por la primera señal(manda un 0), ni por la segunda(otro 0). Así que, a menos que les halla llegado una señal en el turno anterior, ellos no mandarán nada en el turno que corresponde. Lo cual quiere decir que en principio hay tantas señales "activas" como se hallan iniciado en esta "ronda". La primera ronda es 2 porque el primero manda 2 señales, en la segunda serán 4 porque el de/los de en medio mandan 2 para cada lado. En la tercera 8, etc...

Pues bien, probad a ir ejecutando las 2 señales al mismo tiempo en un papel(dibujaros cajitas conectadas en fila e ir haciéndolo, veréis cómo funciona), cada soldado, en cada turno, ve lo que le ha llegado, y decide lo que va a hacer en el siguiente, entonces lo mandan todos a la vez, y se pasa al siguiente turno.

El resultado es(SE VE EN EL PAPEL, HACEDLO EN EL PAPEL PARA VERLO), que si son impares, el punto en el que la primera señal "de vuelta" entra por la derecha en un soldado al que al mismo tiempo le llega por la izquierda un 1 ó un 2 de la segunda señal(que siempre ocurre en alguno), es justamente el soldado de en medio. ADEMÁS(de nuevo, se ve en el papel), la señal que le entra por la izquierda a éste es un 2.

Si son pares, el punto en el que ocurre esto mismo es, de los 2 que están en medio, el de la derecha(se ve en el papel). Además, a este la señal que le llega por la izquierda es un 1(se ve en el papel).

Entonces, si a un soldado le entra un 2 por la izquierda al mismo tiempo que le entra un -1 por la derecha, significa que es el de en medio y que son impares, luego lo que hace es asignarse a si mismo la propiedad de último Y de primero, y a continuación manda, AL MISMO TIEMPO, el mismo para de señales hacia la derecha, y el mismo par de señales hacia la izquierda, SIMÉTRICAS(lo cual quiere decir, hacemos 2 nuevas señales que funcionan igual que las anteriores pero donde pone siguiente lo cambias por anterior y donde pone último lo cambias por primero).

Si a un soldado le entra un 1 por la izquierda(por la segunda señal, 1 en la primera señal es distinto que 1 en la segunda) al mismo tiempo que le entra un -1 por la derecha, sabe que son pares y que es el de la derecha de los 2 de en medio, así que lo que hace es asignarse a si mismo una variable auxiliar: me_hago_primero y mandarle a su anterior una señal especial que significa "hazte_ultimo"(por una entrada nueva, que tiene 2 posibles valores: 0(no hagas nada), y 1(hazte ultimo). En cada turno, cada soldado revisa su propia variable me_hago_primero, ANTES DE LA PARTE PRINCIPAL DEL ALGORITMO, y si le dice que se haga primero, se hace primero y pone su variable me_hago_primero a 1. Así mismo, cada soldado, revisa su entrada "hazte_ultimo" que le viene del de la derecha, y si le dice 1 pues se hace último. De este modo consigo que estos 2 soldados se hagan uno primero y el otro último a la vez(el de la derecha consigue simular un retraso utilizando una variable auxiliar que setea más tarde en el algoritmo de lo que la comprueba, con lo que hasta el siguiente turno no la comprueba, y logra un retraso). A continuación, el de la derecha manda el par de señales hacia la derecha de nuevo y el de la izquierda manda el par de señales simétricas hacia la izquierda. Y repetir.

De este modo, si son impares los divido en 2 grupos iguales donde el primero de 1 es el último del otro(pero siguen siendo grupos en los que sus señales no se van a mezclar), y si son pares los divido en 2 grupos iguales y separados.

Hacedlo en el papel que es donde se ve bien. Probad con números de soldados distintos y veréis que siempre funciona.

Recordad que la condición de disparo es que él, su anterior(si no es el primero del todo), y su último(si no es el último del todo), sean o bien primeros o bien últimos o las 2 a la vez, posiblemente unos diferentes de otros, pero todos son al menos una, y esto siempre se produce en todos los soldados al mismo tiempo. Para saber esto cada turno se mandan señales hacia los dos lados con su valor de primero y de último. Así que en realidad disparan al turno siguiente a que ya son todos primeros o últimos, pero en cualquier caso es en todos a la vez.

La 2) ya la he respondido aquí. Lo mejor es que dibujéis la ristra de soldados en un papel y lo comprobéis.

[HaCkZJuaNN]

                        counter = turno;                       

Ese es el problema de ese algoritmo. Que no sabes cuántos turnos va a haber, y por lo tanto eso podría dar overflow. Yo no utilizo la variable turno como parte del PROPIO algoritmo, sino meramente para indicar los resultados, pero los soldados no la conocen, la conozco yo que soy el que está probando el algoritmo.

[HaCkZJuaNN]

Yo creo que queda claro que el enunciado debe decir algo como que los soldados no conocen a priori el número de soldados que son, es decir no vale usar n como variable que todos conocen, esto es la forma de independizar el sistema del número de soldados,

Exactamente. El algoritmo es fijo, y da igual cuantos soldados pongas juntos, sigue funcionando.

Además veo un poco contradictorio que no puedan calcular el número de soldados y que sí puedan pasarse infinitas entradas ( ya que dice el enunciado que pueden reducirse a una), pues entonces mandamos tantas entradas como necesitemos para enviar n una vez calculada por el último soldado ¿no?

No, perdon si no me expliqué bien. No se pueden hacer infinitas entradas. Tampoco se pueden hacer finitas entradas pero que el número de entradas sea dependiente del número de soldados. Si el número de entradas es fijo y funciona para cualquier número de soldados, entonces se pueden condificar como una sola. Obviamente lo que tú dices es así, eso sería hacer trampas, pero si el número de entradas es un número predeterminado(por ejemplo, 14), sí que vale y sí que se puede codificar en 1 sola.

De todas formas si no pueden contar, la otra solución es la de mandarse los ids que deben ser únicos y para ello este id debe de ser capaz como mínimo de alvergar N (número de soldados) ids diferentes así que dependencia con N por narizes debe de haber directa o indirectamente.

Así mismo el contar la mitad, ya vuelve a hacer el sistema dependiente de N, N/2 es relación directa con N. Veo un tanto en cuanto raro que seamos capaces de guardar N/2 y no N, es decir, N puede ser lo grande que quieras así que si produces overflow con N el doble de éste porducirá con N/2 el overflow. Hablando con números si n = 10, y no puedes guardarlo entonces que pasa si n = 20, n/2 es 10 y no puedes guardarlo.

Nono, yo no sé cuántos hay en la mitad, yo sé QUÉ SOLDADO ES EL DE EN MEDIO. Hay una diferencia. Saber que un soldado es el de en medio es simplemente ponerle un booleano a 1 a ese soldado. Saber cuántos hay en la mitad queda fuera de las reglas del enunciado.

[HaCkZJuaNN]

aqui podemos sacar algo en conclusion sobre todo quien sepa bastante de ingles http://portal.acm.org/citation.cfm?id=568278

el problema:

In this paper we improve the bounds on the complexity of solutions to the firing squad problem, also known as the firing synchronization problem. In the firing synchronization problem we consider a one-dimensional array of n identical finite automata. Initially all automata are in the same state except for one automaton designated as the initiator for the synchronization. Our results hold for the original problem, where the initiator may be located at either endpoint, and for the variant where any one of the automata may be the initiator, called the generalized problem. In both cases, the goal is to define the set of states and transition rules for the automata so that all machines enter a special fire state simultaneously and for the first time during the final round of the computation. In our work we improve the construction for the best known minimal-time solution to the generalized problem by reducing the number of states needed and give non-minimal-time solutions to the original and generalized problem that use fewer states than the corresponding minimal-time solutions.

Ese es. Aunque en mi caso siempre la señal se le da al primero. Si se le puede dar a cualquiera(lo que llama ahí generalized problem), mi algoritmo obviamente no funciona :(

[HaCkZJuaNN]

bien, empezamos a aclarar la cuestion...

los papers aclaran un poco mas el problema y dan los datos que faltaban... paso a comentar:

1) no es una fila, es un anillo... esto quiere decir, que el primero se enlaza con el ultimo y a la inversa

No, ese es otro tercer problema distinto. En ese, mi algoritmo funciona y además es de orden 2n-2, y se puede iniciar sobre cualquier soldado. Con una fila también se puede solucionar, y de hecho el mio lo soluciona. Es básicamente lo mismo pero más fácil :P

por otro lado, hay otro metodo que no es nada optimo que trabaja sobre el peloton en forma de array, y va dividiendo al mismo de 2 en 2, de forma recursiva... en este caso se arranca con un solo iniciador que debe ser ubicado al final del array (para saber la cantidad de automatas o soldados)... por ende, se cuentan...

Creo que esa es la solución mia, pero o bien no lo es o la has entendido mal como la mía :P porque en la mía no se cuenta. Pero la mía se basa en ir dividiendo la fila por la mitad sucesivas veces.

Por favor, me encantaría que entendierais mi solución a parte de las "oficiales". Además estoy seguro de que la mía es una de las oficiales, aunque no la mejor.

[DCelso]

Ostras tu, que revelador el ejemplo extraido de su autor y es exactamente este,

http://en.wikipedia.org/wiki/Firing_squad_synchronization_problem

Pues sí, he leído varias veces tu solución y creo que es una implementación de la solución que llaman General  (de orden 3n). En la wiki se entiende muy bien es cuestion de mandar dos señales una la mitad mas lenta que la otra (asi que algo de temporización hace, aqui está el truco :D ) por lo que vas encontrando la mitad y volviendo a plantear el problema para las dos mitades creadas, aunque dice que se resuelve con 15 estados, (cosa que en tu ejemplo no veo).
Esta creo que se podría programar facilmente y verla visualmente :D.

En cuanto a la solución óptima en tiempo (orden 2n-2), no pillo ni papa, aparecen "i" señales y pone que van distintas velocidades a cada una, es como la general pero intentando encontrar en vez de mitades , i particiones, por lo que llegas a acotar antes y portanto disparar antes. Por cierto, No se lo que vale i ni de qué depende :D.

He leido que también hay optimizaciones de este código propuestas por estudiantes pero todas consisten en cambiar el enunciado :D, haciendo el anillo del que habla splinter, o haciendo conexiones en cubo o noseque historias :), vamos ahí guarreando un poco las reglas.

[DjSonyk]

Si Dcelso yo al igual que tu ,he visto unas cuantas formulas para lo mismo que no quieren decir que sean mas optimas ,anillos ,arrays dimensionales,... un ect hasta esquaciones....bueno yo creo que ya mas no me voy a comer el tarro,hasta una solucion final eso si me quedo con la mia xD.... De todas formas si huviera por ejemplo 1000 soldados no podria una maquina enviar la sentencia de todas a la vez,ya que las maquinas no son multitareas y abria un espacio de tiempo entre 1 disparo y otro vamos como en la vida real ,el jefe de formación dice "Fuego!!" y segun el tiempo de reaccion de cada soldado dispara antes que otros... en fin por cierto por mas que mire en la wiki ni vi nada de eso DCelso ,buen descubrimiento.