Preguntas escritas sobre programación de entrevistas para los principales fabricantes

64 caballos, 8 pistas, encuentra los 4 primeros, ¿cuánto es el número mínimo de carreras?

¡Bien, es hora de poner a prueba tus habilidades de pensamiento lógico con preguntas de algoritmos lógicos! !

Análisis de situación 1: Contrarreloj

Basándonos en el tema, rápidamente descubrimos que este tema es en realidad "divergente" y no tiene un montón de "reglas y regulaciones".

¡Bien, seamos "más inteligentes" y supongamos que es una "contrarreloj"!

Muy bien, 64 caballos, 8 pistas, así que según el tiempo, los 4 caballos más rápidos solo necesitan 8 carreras ~

Obviamente, es imposible para los grandes fabricantes de Tencent. Tan tonto, ¿bien? ! Por tanto, sin descartar esta situación, debemos considerar la lógica de solución de la "prueba no cronometrada", que se ajusta más a la "temperatura de una gran fábrica" ​​~

Análisis de situación 1: Prueba no cronometrada

Si no es una contrarreloj, obviamente es complicado, pero cuanto más complicado es, más inteligentes nos volvemos, ¿verdad? !

Primero, utilizamos la idea de "divide y vencerás" comúnmente utilizada en los algoritmos para dividir los 64 buenos caballos en 8 grupos, a saber, A, B, C, D, E, F, G y h.

Cada grupo tiene 8 caballos, numerados en secuencia: A1, A2, A3, etc.~

Luego, una vez completados los preparativos, comenzamos a dejar correr a los caballos.

64 caballos, 8 grupos, 8 pistas.

El primer paso (* * *Ejecutar 8 veces): 8 grupos corren cada uno una vez, retienen los 4 mejores de cada grupo (área amarilla) y luego eliminan los 4 últimos de cada grupo (área azul) .

Pregunta:

¿Por qué eliminaron a los últimos cuatro de cada uno de los ocho grupos?

Respuesta:

Presta atención a la pregunta Sólo necesitamos a los cuatro primeros corredores más rápidos, por lo que los cuatro últimos serán eliminados de cada grupo, porque los cuatro primeros nunca aparecerán. azul ¡Sobre los caballos de la zona!

El segundo paso (* * * corrió 1 vez): toma 1 de cada grupo para una carrera y luego elimina todos los caballos de los últimos 4 grupos.

Pregunta:

¿Por qué el primer corredor de cada grupo corrió una vez y el cuarto corredor fue eliminado y seguía en el grupo?

Respuesta:

Como sabemos, después del primer paso de las carreras de caballos, tenemos la clasificación de ocho grupos.

Pero entre los 8 grupos, ¿cuál grupo es más poderoso?

No lo sabemos, por lo que necesitamos que 1 de cada grupo corra una vez para obtener la clasificación fuera del grupo de 8 grupos.

Supongamos que el primer corredor de ocho grupos termina la carrera y que los cuatro primeros corredores son A1, B1, C1 y D1. Entonces, de acuerdo con los requisitos, encuentre los cuatro caballos más rápidos, y deben estar en A, B, C y D. Es absolutamente imposible que aparezcan en E, porque los caballos más rápidos entre E, F, G y H son E1. , F1, G1 y H1 no están entre los 4 primeros, ¡y el resto es aún menos probable!

El tercer paso (análisis lógico, no es necesario correr): ¡Después de los dos primeros pasos de la competencia, A1 puede avanzar! ¡Porque ya es el más rápido entre 64 caballos! !

¡Solo necesitamos encontrar los tres caballos más rápidos restantes! Elegimos el caballo A1 (azul) y lo ignoramos.

¡Los seis caballos de la zona gris se pueden eliminar directamente! ! !

¿Por qué?

¡Escúchame atentamente!

Sospecha:

¿Por qué eliminar directamente a los seis caballos en el área gris? ¿Qué hicieron mal?

Respuesta:

Recuerda, la pregunta requiere que encontremos los cuatro caballos más rápidos. Después de los primeros dos pasos (* * * nueve carreras), sabemos que A1, B1, C1 y D1 son los cuatro primeros "clasificados externos" de los ocho grupos.

Al mismo tiempo, A65438,!

¡Sin embargo, los caballos 2, 3 y 4 más rápidos entre los 64 caballos faltan temporalmente!

Analizando una ola:

¿En qué rango es probable que esté el segundo lugar más rápido?

¡Obviamente, sólo en A2, o B1! ! !

¿Por qué no A3 o B2 o C1?

¡Estás bien!

¡Porque las clasificaciones más rápidas (los cuatro primeros) del grupo son A1, A2, A3 y A4, y las clasificaciones más rápidas (los cuatro primeros) fuera del grupo son A1, B1, C1 y D1!

¡Así que el segundo puesto más rápido sólo se puede elegir entre A2 y B1! ¡No hay otra opción! !

Según esta lógica, podemos seguir analizando el segundo y cuarto lugar, y podemos saber que los cuatro primeros más rápidos no se pueden distribuir en el área gris, por lo que eliminamos los seis caballos en el área gris. !

Paso 4 (Discusión sobre la clasificación): Debido a que A1 es el primer lugar más rápido, ¡lo elegimos! La siguiente cuestión es encontrar los tres caballos más rápidos entre A2, A3, A4, B1, B2, B3, C1, C2 y D1.

La cuestión es: ¡porque sólo hay 8 pistas y tenemos 9 caballos!

* *¡Entonces, nos quedamos con cualquiera de los nueve caballos! **

Nota: Los caballos que dejamos se pueden dividir en dos categorías para su procesamiento:

Uno: ¡el caballo tiene un caballo que obviamente es más lento que él!

Categoría 2: ¡Este caballo no es obviamente lento!

Situación 1: ¡Deja el caballo "superior"!

¡Supongamos que dejamos B1! (C1, B2 son obviamente más lentos que él)

¡Los ocho caballos restantes salen corriendo!

Escenario 1 (correr una vez):

Después de que los 8 caballos restantes terminaron de correr, descubrimos que B2 o C1 corrieron entre los 3 primeros. ¡En este punto, B1 a la izquierda es definitivamente el top 3 más rápido! ¡Porque B1 es más rápido que B2 y C1! !

Así que encontramos con éxito los 4 caballos más rápidos entre los 64 caballos.

Escenario 2 (correr dos veces):

Después de que los 8 caballos restantes terminaron de correr, descubrimos que B2 o C1 no terminaron entre los 3 primeros.

¡En este momento, solo podemos dejar que B1, A2, A3 y A4 vuelvan a correr y tomar los tres primeros! !

Duda: ¿Por qué B1, A2, A3 y A4 volvieron a huir? ¿Nada más?

Respuesta:

Entonces B1 se ejecuta con A2, A3 y A4 (nota, ¿por qué no ejecutar con C1? Porque B1 es más rápido que C1, por lo que no es necesario ejecutarlo. )

Y B1 es más rápido que B2 y B3 y no necesita ejecutarse, por lo que B1 usa A2, A3 y A4 para ejecutarse.

Situación 1: ¡Deja el caballo de "segunda clase"!

¡Supongamos que dejamos A4! Ningún caballo fue significativamente más lento.

Los 8 caballos restantes correrán una vez para obtener una clasificación, luego se elegirá el primer lugar y el resto correrá en A4.

¡De esta manera podremos conseguir los cuatro primeros más rápidos! !

Análisis

Se puede ver que si mantenemos un tipo de caballo, puede haber un resultado "óptimo", es decir, el resultado se puede obtener corriendo solo una vez.

Y si dejas el segundo tipo de caballo, ¡tardarás dos veces en obtener el resultado! !

Resultados

A través del análisis anterior, veamos los requisitos de la pregunta Necesitamos obtener "¿el número mínimo de juegos?".

El primero. El paso es 8 veces.

El segundo paso: 1 vez

El tercer paso es 0 veces

El cuarto paso: 1 o 2 veces

Luego al menos 8 1 1 = 10 veces.

Un problema aparentemente simple, pero hay una lógica tan compleja escondida detrás de él. No hay duda sobre el "estilo de gran fábrica" ​​~

¿Ustedes, amigos inteligentes, tienen una mejor solución? ?

¡Bienvenido a compartir~~!