El algoritmo barato es un problema aleatorio común que encontramos cuando jugamos y clasificamos al azar. Se puede abstraer así: obtenga una matriz de pedidos aleatorios de todos los números naturales dentro de M.
Buscando el "Algoritmo de reorganización" en Baidu, el primer resultado fue la "Biblioteca Baidu - Algoritmo de reorganización". Después de escanear el contenido, muchos de los contenidos son fáciles de incrustar a otros por mal camino, incluido el uso de listas vinculadas para reemplazar las matrices al final, que es solo una optimización limitada (las listas de enlaces también introducen la pérdida de eficiencia de lectura).
El primer método en este artículo se puede describir simplemente como: dibujar al azar y ponerlas en otro grupo; Dibujarlos nuevamente, dibujarlos repetidamente cuando dibuje las cartas vacías.
"Dibuja las cartas después de dibujarlas nuevamente" conducirá a la creciente posibilidad de dibujar las cartas más tarde, lo que obviamente no es razonable.
Se puede optimizar un paso: después de dibujar las cartas, las cartas originales se vuelven menos. (en lugar de dejar tarjetas vacías)
El código es el siguiente:
La copia del código es la siguiente:
función shuffle_pick_1 (m) // shush // método de dibujo de tarjeta
{
// generar tarjetas m
var arr = new Array (m);
para (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Dibuja una carta a la vez y colóquela en otra pila. Debido a que necesita extraer elementos de la matriz y sacar todos los elementos posteriores hacia adelante uno por uno, lleva mucho tiempo.
var arr2 = new Array ();
para (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (rnd, 1);
}
regresar arr2;
}
Esto también es obviamente problemático, porque si la matriz es grande, eliminar un cierto elemento en el medio hará que la cola diga un paso adelante, lo cual es una acción que requiere mucho tiempo.
Recuerde el propósito de "¿Por qué eliminamos ese elemento?" es evitar tarjetas vacías.
Además de eliminar ese elemento, ¿tenemos otras formas de eliminar las tarjetas vacías?
---- Sí, solo necesitamos poner la última tarjeta no pagada en la posición de sorteo.
Entonces, podemos optimizar esta idea de la siguiente manera:
La copia del código es la siguiente:
función shuffle_pick (m) // sear // método de dibujo de tarjeta para optimizar la tarjeta
{
// generar tarjetas m
var arr = new Array (m);
para (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Dibuja una carta a la vez y colóquela en otra pila. Ponga la última tarjeta no dibujada en el asiento abierto.
var arr2 = new Array ();
para (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
regresar arr2;
}
Además de la idea de las tarjetas de dibujo, también podemos usar la idea de cambiar las tarjetas.
"Algoritmo de Baidu Wenku-Shut" menciona una idea de cambio de tarjeta: "Cambie dos posiciones al azar e intercambie n veces en total. Cuanto más grande sea, más cerca estará al azar".
Este enfoque es incorrecto. Incluso si N es muy grande (por ejemplo, 10 tarjetas, 10 interruptores), todavía existe una alta posibilidad de que "algunas cartas no cambien posiciones en absoluto".
Siga esta idea y haga un pequeño ajuste: cambie la tarjeta i-th con cualquier tarjeta y simplemente cámbiela para una ronda.
El código es el siguiente:
La copia del código es la siguiente:
función shuffle_swap (m) // shush // método de cambio de tarjeta
{
// generar tarjetas m
var arr = new Array (m);
para (var i = 0; i <m; i ++) {
arr [i] = i;
}
// La tarjeta i-th se usa para cambiar los asientos y puede cambiarla para una ronda
para (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
regresar arr;
}
Además de la idea de dibujar y cambiar las tarjetas, también podemos usar la idea de insertar tarjetas: primero hay una tarjeta, la segunda tarjeta tiene dos posiciones para insertarse al azar (antes o detrás de la primera carta), la tercera tarjeta tiene tres posiciones para insertarse aleatoriamente (colocadas o insertadas en la primera posición, o insertarse en la segunda posición), y así sucesivamente
El código es el siguiente:
La copia del código es la siguiente:
función shuffle_insert_1 (m) // shunt // método de inserción de la tarjeta
{
// Cada vez, la tarjeta más grande se genera e se inserta frente a una tarjeta aleatoria. Debido a que necesita insertar elementos en la matriz y exprimir todos los elementos posteriores uno por uno, lleva mucho tiempo.
var arr = [0];
para (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
}
regresar arr;
}
El código anterior también tendrá algunos problemas: a medida que aumenta el número de tarjetas, se vuelve cada vez más difícil insertar tarjetas, porque insertar tarjetas conducirá a muchas de las tarjetas que siguen un paso atrás.
Por supuesto, también podemos optimizar adecuadamente: primero hay una tarjeta N-1, la tarjeta N-Th se coloca al final y luego intercambia posiciones con cualquier tarjeta.
El código es el siguiente:
La copia del código es la siguiente:
FUNCIÓN SHUFLE_INSERT (M) // SHUSH // La versión optimizada del método de inserción de la tarjeta puede demostrarse mediante la inducción matemática de que este Shuffle es uniforme.
{
// Cada vez genera la tarjeta más grande e intercambia posiciones con una tarjeta aleatoria
var arr = new Array (m);
arr [0] = 0;
para (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
regresar arr;
}
Ok, todos los códigos son los siguientes. Los estudiantes interesados pueden probarlos en su propia máquina para ver si su eficiencia de ejecución respectiva y si el resultado final es teóricamente aleatorio.
La copia del código es la siguiente:
<html>
<Evista>
<meta http-oquiv = "content-type" content = "text/html; charset = gb2312">
<title> jk: javascript algoritmo de baraja </title>
</ablo>
<Body>
<script type = "text/javaScript">
función shuffle_pick_1 (m) // shush // método de dibujo de tarjeta
{
// generar tarjetas m
var arr = new Array (m);
para (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Dibuja una carta a la vez y colóquela en otra pila. Debido a que necesita extraer elementos de la matriz y sacar todos los elementos posteriores hacia adelante uno por uno, lleva mucho tiempo.
var arr2 = new Array ();
para (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (rnd, 1);
}
regresar arr2;
}
función shuffle_pick (m) // sear // método de dibujo de tarjeta para optimizar la tarjeta
{
// generar tarjetas m
var arr = new Array (m);
para (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Dibuja una carta a la vez y colóquela en otra pila. Ponga la última tarjeta no dibujada en el asiento abierto.
var arr2 = new Array ();
para (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
regresar arr2;
}
función shuffle_swap (m) // shush // método de cambio de tarjeta
{
// generar tarjetas m
var arr = new Array (m);
para (var i = 0; i <m; i ++) {
arr [i] = i;
}
// La tarjeta i-th se usa para cambiar los asientos y puede cambiarla para una ronda
para (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
regresar arr;
}
función shuffle_insert_1 (m) // shunt // método de inserción de la tarjeta
{
// Cada vez, la tarjeta más grande se genera e se inserta frente a una tarjeta aleatoria. Debido a que necesita insertar elementos en la matriz y exprimir todos los elementos posteriores uno por uno, lleva mucho tiempo.
var arr = [0];
para (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
}
regresar arr;
}
FUNCIÓN SHUFLE_INSERT (M) // SHUSH // La versión optimizada del método de inserción de la tarjeta puede demostrarse mediante la inducción matemática de que este Shuffle es uniforme.
{
// Cada vez genera la tarjeta más grande e intercambia posiciones con una tarjeta aleatoria
var arr = new Array (m);
arr [0] = 0;
para (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
regresar arr;
}
// alerta (shuffle_pick (10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
Funcnames = ["Dibujar Tarjeta", "Optimización de la tarjeta de dibujo", "Cambio de tarjeta", "Inserción de tarjeta", "Optimización de inserción de tarjeta"]
M = 10000,
tiempos = [];
para (var i = 0; i <funcs.length; i ++) {
var d0 = nueva fecha ();
funcs [i] (m);
Funcnames [i] = (new Date () - D0) + '/t' + Funcnames [i];
}
alerta (funcnames.Join ('/n'));
</script>
</body>
</html>