Decir que hemos $N$ [$3 \le N \le 100,000$] esferas indexados como $1,2,3,\cdots N$,todos ellos tienen idéntico peso, aparte de uno.Tenemos que determinar que la esfera es (índice) mediante el uso de sólo el par de escalas.
Podemos resolver este problema mediante el pesaje en repetidas ocasiones,pero obviamente estoy interesado con un peso de tan mínimo como sea posible así que mi pregunta es ¿cuál podría ser el algoritmo óptimo para esta tarea?
Para un tratamiento completo, tenemos que considerar todas las combinaciones con algunos parámetros de variante. El problema de base: dado $n$ bolas, siendo uno de ellos "desviadas" (no es el mismo peso que el $n-1$ otros), cómo encontrar el desviada de la bola en la mayoría de los $w$ pesa ? O, del mismo modo, ¿cuál es el máximo número de $n$ de bolas para que la desviación de la bola siempre puede ser identificado en la mayoría de los $w$ pesa ?
La variante de parámetros son los siguientes:
Las bolas pueden ser "marcada". Una bola que está marcado el "pesado" puede ser desviada por ser pesada, pero no más claro. Podemos considerar una variante de el problema en el que todas las pelotas son señaladas individualmente, pesado o ligero (de forma independiente el uno del otro). El problema en el que conocer un priori que la desviación de la bola es más pesado es un subcase de la "marcada pelotas" problema (es decir, el "marcado bolas" problema donde todas las pelotas están marcados "pesado").
Se le puede pedir a identificar la desviación de la bola y para dar su la desviación de la dirección (es decir, usted también debe averiguar si el desviada de la bola es más pesado o más ligero).
Posiblemente, un extra de "estándar" de la bola se da garantizada no desviada.
Vamos a ver en primer lugar la "marcada bolas" problema porque es esencial el paso de la totalidad de su tratamiento.
En primer lugar, algunas notas importantes:
Con marcado bolas, la identificación de la desviación de la bola implica la identificación de la desviación, de forma automática.
Si sólo tiene un marcado bola, entonces el problema se soluciona con no pesan en absoluto: si sólo hay un sospechoso, entonces es el culpable.
Si usted tiene dos marcada bolas y asumir distintas marcas (una es marcado pesado, el otro está marcado luz), entonces el problema es irresolubles -- a menos que usted tiene un estándar de pelota, en el que caso de que usted sólo tiene que hacer una pesan entre esa bola estándar y uno de la potencialmente desviadas de bolas.
Cada uno pesa, se puede producir sólo 3 resultados diferentes, así que con $w$ pesa puede llegar a la mayoría de las $3^w$ distintas conclusiones. Por lo tanto, el problema no puede ser resuelto (fiable) si $n \gt 3^w$.
Lo que ocurre es que la "marcada bolas" problema puede ser resuelto por todos los $n$ hasta ese $3^w$ límite (suponiendo que la presencia de una bola estándar si $n = 2$). Esto se demuestra con la siguiente periodicidad:
Con $w = 0$ (no pesa nada), de hecho puede resolver el problema con $n = 3^0 = 1$ marcado pelota.
Con $w = 1$ y marcó dos bolas con la misma marca, sólo pesan un en contra de la otra; si tienen distintas marcas, el uso de la extra bola estándar, según se explicó anteriormente.
Si $w = 1$ y tres marcado bolas, a continuación, dos de ellos (al menos) han la misma marca. Pesa uno contra el otro; esto produce el resultado.
Si $w \gt 1$$3^{w-1} \lt n \leq 3^w$, entonces usted puede montar dos juegos de bolas de tamaño $\lceil n/3 \rceil$, teniendo cuidado de poner la misma número de "pesado" marcas en ambos conjuntos (lo que implica que también puso el mismo número de "luz" marcas en ambos grupos). A continuación, pesa un conjunto de en contra de la otra. Si la balanza se inclina a la izquierda, a continuación, el desviado la pelota es uno de los "pesados" bolas de la escala de la izquierda o de uno de los "luz" bolas de la escala de la derecha. Si el pesaje resultado es equilibrado, a continuación, la desviación de la bola está en el conjunto de bolas que se ponga en ninguno de los dos conjunto. De cualquier manera, en la mayoría de las $3^{w-1}$ sospecha de bolas, $w-1$ pesa, y al menos una bola que definitivamente no desviada, es decir, una "bola estándar". La recurrencia se aplica.
Considere la posibilidad de $n$ sin marcas de bolas. Su primer pesan dará como resultado una resultado equilibrado, o un desequilibrio en el resultado. Si el resultado es equilibrado, entonces el problema se reduce a la de $w-1$ permitido pesa con todos los las bolas que hizo no tomar parte en la primera pesan, y las bolas se utiliza en la primera pesan ahora se sabe que todos la norma de "bolas". Si el el resultado es un desequilibrio, luego de que todas las pelotas que participan en el pesaje se sospecha pero todos pueden ser marcados, así que esto nos lleva de nuevo al problema de marcado bolas (y las bolas que se no se utiliza en la primera pesan ahora conocido por ser el estándar).
Vamos a llamar a $f(w)$ el número máximo de sin marcar bolas que pueden ser procesado en $w$ pesa, suponiendo que un extra de bola estándar es disponible. Por ahora, vamos a suponer que queremos identificar el balón y su desviación.
$f(1) = 1$. De hecho, con sólo un peso, se obtiene sólo tres conclusiones, así que usted no puede procesar dos bolas, porque dos bolas de decir cuatro las posibles conclusiones (primera bola es pesada, la primera bola es la luz, la segunda la pelota es pesado, segunda bola de luz). Con una pelota, sólo pesan en contra de la extra de bola estándar.
Si $w \gt 1$ e tiene $n \gt f(w-1)$ bolas, a continuación, aislar $f(w-1)$ pelotas, y dividir el resto en dos subconjuntos de igual tamaño (si existen es un número impar de bolas restantes, agregar la bola estándar). Hacer un pesaje entre estos dos subconjuntos. Si un resultado equilibrado, la recurrencia se aplica (ha $f(w-1)$ sin marcas de bolas y $w-1$ pesa). Si un desequilibrio en el resultado se obtiene, entonces todas las pelotas que participan en el primera pesan ahora están "marcados" (excepto, por supuesto, el extra de bola estándar, si se agregó). Esto nos lleva a la siguiente relación: $f(w) = f(w-1) + 3^{w-1}$.
Por lo tanto, $f(w) = (3^w - 1)/2$ (usted puede verificar que se cumple la recurrencia relación y el punto de partida $f(1) = 1$).
¿Qué pasa si usted no tiene un extra de bola estándar, para empezar ? Entonces usted no será capaz de hacer la primera sopesar con $3^{w-1}$ bolas, ya que eso es un entero impar, y un peso implica un número par de pelotas. Así usted tiene que usar sólo la $3^{w-1}-1$ bolas. Sin embargo, después de este primer pesaje, tiene uno o varios "estándar bolas", para que pueda volver a la anterior problema. Por lo tanto, la falta de disponibilidad de un extra de bola estándar significa que sólo disminuir el número máximo de procesable por bolas.
¿Qué pasa si usted no está interesado en identificar la verdadera desviación la dirección, pero sólo en la búsqueda de que la pelota es desviada ? A continuación, todos los de el anterior aún se mantiene, excepto para el punto de partida. Si usted llama a $g(w)$ el número máximo de sin marcar las bolas que se pueden procesar en estas condiciones, a continuación,$g(1) = 2$: con dos bolas, apenas pesan en contra de la extra bola estándar; con tres bolas, usted tiene que incluir dos sospechosos pelotas en la primera, el peso, pero usted no sabe cual es el culpable ya que están sin marcar. De ello se desprende que $g(w) = f(w) + 1$ todos los $w$.
Si se le permite a $w$ pesa, entonces usted puede encontrar la desviación de la bola y su desviación entre un máximo de $(3^w-3)/2$ bolas. Si no interesado en la desviación de la dirección, pero sólo en la identificación de la desviación bola, a continuación, usted podrá procesar una bola extra. Si un "estándar" extra pelota es disponible, entonces usted puede procesar una bola extra. Estos dos "uno extra bola de" incrementos son acumulativos; por lo tanto, con 3 pesa, puede que el proceso de a los 12, 13 o 14 de bolas, dependiendo de si usted tiene un extra de estándar bola, y si usted está interesado en la dirección de la desviación.
Condiciones adicionales: si no "estándar" bola extra, la el problema es irresoluble si:
hay una o dos bolas y desea que la desviación de la dirección;
hay exactamente dos bolas y usted no está interesado en la la desviación de la dirección.
Aparte de estos dos casos extremos, todo el número de bolas no mayor que el de máximo puede ser procesada (no hay un "agujero").
Esto se ve como una generalización de los clásicos $12$ bola problema.
Usted debe ser capaz de modificar Jack Wert es maravilloso algoritmo, (el cual fue diseñado para el caso, cuando se $N= \dfrac{3^m - 3}{2}$) para trabajar para cualquier $N$. Creo que me había hecho (incompleta) intento cuando alguien le preguntó a este en stackoverflow.
Tenga en cuenta que los números de $\dfrac{3^m - 3}{2}$ son especiales, en el sentido de que son los puntos de inflexión.
En la variante del problema en el que también están obligados a saber si la extraña esfera es más pesado o más ligero, para $\dfrac{3^m -3}{2} \lt N \le \dfrac{3^{m+1}-1}{2}$, el número óptimo de pesajes puede ser demostrado ser $m+1$.
Si usted sólo necesita encontrar la extraña esfera y no necesariamente de averiguar si es más pesada o más ligera, los puntos de inflexión se $\dfrac{3^m -3}{2} + 1$.
Si $N = 3^n$ es una potencia de tres, entonces que podemos hacer es $n+1$ pesajes:
En primer lugar, asumir que la extraña bola es más pesado que el de los demás (esto es sólo para simplificar la exposición, vamos a volver a este). Ahora la etiqueta de todas las bolas de$0$$N-1$, en el ternario de la notación. Para cada ternario posición de dígito, sopesar todas las bolas con $0$ en esa posición en contra de todas las bolas con $2$ en esa posición, dejando fuera el resto de las bolas (con 1 en esa posición). El resultado le dice a usted (suponiendo que la extraña bola es más pesado) el ternario dígitos de la extraña bola en esa posición: $0$ si $0$'s superan a las $2$'s; $2$ si $2$'s superan a las $0$'s; e $1$ si son iguales.
Así que ahora usted tiene el ternario de expansión de la extraña bola, suponiendo que es pesado. Si esa suposición es errónea, y la extraña bola es luz, entonces el número de la extraña bola se obtiene cambiando todos los $0$'s $2$ y viceversa. Para averiguar cuál de los dos candidatos es la extraña bola, sólo pesan uno de ellos contra una pelota que es conocido por no ser impar.
Esto no funciona si $N$ no es una potencia de tres, debido a que en general el número de bolas de con $0$ en una posición dada no es el mismo que el número de bolas de con $2$ en esa posición. Así que no se puede pesar en contra de uno al otro. Pero podemos arreglar esto por el simple dispositivo de dividir las bolas en los dos igual montones, la numeración de un montón arriba de $0$ y la otra del montón de abajo de $3^n-1$ donde $3^n$ es la más pequeña de energía de los tres que se $\ge N$. (Si el número de bolas es impar, la etiqueta de la izquierda sobre la pelota con $11...11$.)
Mi conjetura es que este procedimiento es óptima cuando $N$ es una potencia de tres, pero de lo contrario, a veces podemos hacer mejor; por ejemplo, si $N=4$, sólo necesitamos dos pesajes para identificar la extraña bola (pero no siempre sabemos si es más pesada o más ligera).
Editar Esta solución se muestra cómo resolver el problema en $n$ pesajes para cualquier $N \le 3^n$ cuando sabemos que si la extraña bola es más pesado o más ligero. Ahora podemos poner esto junto con Morón de la solución propuesta (vinculado en Morón de la respuesta) para obtener una solución completa en $n$ pesajes cuando $N \le (3^n-3)/2$. (Esta solución también nos dice si la extraña bola es más pesado o más ligero.)
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
