O algoritmo de embaralhamento é um problema aleatório comum que encontramos ao jogar e classificar aleatoriamente. Pode ser abstraído assim: Obtenha uma matriz de pedidos aleatórios de todos os números naturais dentro de M.
Pesquisando o "algoritmo de remodelação" no Baidu, o primeiro resultado foi "Biblioteca Baidu - algoritmo de remodelação". Após a digitalização do conteúdo, muitos conteúdos são fáceis de enganar aos outros, incluindo o uso de listas vinculadas para substituir as matrizes no final, o que é apenas uma otimização limitada (listas de link também introduzem a perda de eficiência de leitura).
O primeiro método deste artigo pode ser simplesmente descrito como: desenhe aleatoriamente cartas e colocá -las em outro grupo; Desenhe -os novamente, desenhe -os repetidamente quando desenhar as cartas vazias.
"Desenhe as cartas depois de desenhá -las novamente" levará à crescente chance de desenhar as cartas mais tarde, o que é obviamente irracional.
Um passo pode ser otimizado: depois que os cartões são desenhados, os cartões originais se tornam menos. (em vez de deixar cartões vazios)
O código é o seguinte:
A cópia do código é a seguinte:
função shuffle_pick_1 (m) // shush // método de desenho de cartão
{
// Gere M Cards
var arr = nova matriz (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Desenhe uma carta de cada vez e coloque -a em outra pilha. Como você precisa extrair elementos da matriz e puxar todos os elementos subsequentes para a frente um por um, é demorado.
var Arr2 = new Array ();
for (var i = m; i> 0; i--) {
var rnd = math.floor (Math.random ()*i);
arr2.push (arr [rnd]);
Arr.Splice (Rnd, 1);
}
return arr2;
}
Isso também é obviamente problemático, porque se a matriz for grande, a exclusão de um certo elemento no meio fará com que a fila dê um passo adiante, o que é uma ação muito demorada.
Lembre -se do objetivo de "Por que excluímos esse elemento?" é para evitar cartões vazios.
Além de excluir esse elemento, temos outras maneiras de remover cartões vazios?
---- Sim, só precisamos colocar o último cartão não fundido na posição de empate.
Então, podemos otimizar essa ideia da seguinte maneira:
A cópia do código é a seguinte:
function shuffle_pick (m) // // método de desenho de cartão para otimizar o cartão
{
// Gere M Cards
var arr = nova matriz (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Desenhe uma carta de cada vez e coloque -a em outra pilha. Coloque o último cartão desconhecido no assento aberto.
var Arr2 = new Array ();
for (var i = m; i> 0;) {
var rnd = math.floor (Math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
return arr2;
}
Além da idéia de desenhar cartões, também podemos usar a idéia de mudar de cartas.
"Algoritmo Baidu Wenku-Shut" menciona uma idéia de mudança de cartão: "Mudar duas posições aleatoriamente e troque-as n vezes no total. Quanto maior o n, mais próximo é aleatório".
Essa abordagem está errada. Mesmo que N seja muito grande (por exemplo, 10 cartões, 10 interruptores), ainda há uma grande possibilidade de que "algumas cartas não mudem de posição".
Siga essa ideia e faça um pouco de ajuste: altere o I -th Card com qualquer cartão e basta alterá-lo por uma rodada.
O código é o seguinte:
A cópia do código é a seguinte:
função shuffle_swap (m) // shush // Método de mudança de cartão
{
// Gere M Cards
var arr = nova matriz (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// O cartão I -th é usado para trocar os assentos e você pode alterá-lo por uma rodada
for (var i = 0; i <m; i ++) {
var rnd = math.floor (Math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
retornar arr;
}
Além da idéia de desenhar e alterar cartões, também podemos usar a idéia de inserir cartões: primeiro há uma carta, a segunda carta tem duas posições a serem inseridas aleatoriamente (antes ou atrás da primeira carta), a terceira carta tem três posições a serem inseridas aleatoriamente (colocadas atrás, ou inseridas na primeira posição, ou inseridas na segunda posição) e assim
O código é o seguinte:
A cópia do código é a seguinte:
função shuffle_insert_1 (m) // Método de inserção de shunt //
{
// A cada vez, o maior cartão é gerado e inserido na frente de um cartão aleatório. Como você precisa inserir elementos na matriz e espremer todos os elementos subsequentes, um por um, é demorado.
var arr = [0];
for (var i = 1; i <m; i ++) {
Arr.splice (Math.floor (Math.random ()*(i+1)), 0, i);
}
retornar arr;
}
O código acima também terá alguns problemas: à medida que o número de cartões aumenta, ele se torna cada vez mais difícil inserir cartões, porque a inserção de cartões levará a muitos dos cartões que seguem um passo atrás.
Obviamente, também podemos otimizar adequadamente: primeiro há cartão N-1, o cartão N-és é colocado no final e depois trocar posições com qualquer cartão.
O código é o seguinte:
A cópia do código é a seguinte:
function shuffle_insert (m) // shush // versão otimizada do método de inserção do cartão pode ser comprovada por indução matemática de que esse shuffle é uniforme.
{
// Cada vez que gera o maior cartão e troca posições com um cartão aleatório
var arr = nova matriz (m);
arr [0] = 0;
for (var i = 1; i <m; i ++) {
var rnd = math.floor (Math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
retornar arr;
}
OK, todos os códigos são os seguintes. Os alunos interessados podem experimentá -los em sua própria máquina para ver se sua respectiva eficiência de execução e se o resultado final é teoricamente aleatório.
A cópia do código é a seguinte:
<html>
<head>
<meta http-equiv = "content-type" content = "text/html; charset = gb2312">
<title> JK: Javascript Shuffling Algorithm </ititle>
</head>
<Body>
<script type = "text/javascript">
função shuffle_pick_1 (m) // shush // método de desenho de cartão
{
// Gere M Cards
var arr = nova matriz (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Desenhe uma carta de cada vez e coloque -a em outra pilha. Como você precisa extrair elementos da matriz e puxar todos os elementos subsequentes para a frente um por um, é demorado.
var Arr2 = new Array ();
for (var i = m; i> 0; i--) {
var rnd = math.floor (Math.random ()*i);
arr2.push (arr [rnd]);
Arr.Splice (Rnd, 1);
}
return arr2;
}
function shuffle_pick (m) // // método de desenho de cartão para otimizar o cartão
{
// Gere M Cards
var arr = nova matriz (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Desenhe uma carta de cada vez e coloque -a em outra pilha. Coloque o último cartão desconhecido no assento aberto.
var Arr2 = new Array ();
for (var i = m; i> 0;) {
var rnd = math.floor (Math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
return arr2;
}
função shuffle_swap (m) // shush // Método de mudança de cartão
{
// Gere M Cards
var arr = nova matriz (m);
for (var i = 0; i <m; i ++) {
arr [i] = i;
}
// O cartão I -th é usado para trocar os assentos e você pode alterá-lo por uma rodada
for (var i = 0; i <m; i ++) {
var rnd = math.floor (Math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
retornar arr;
}
função shuffle_insert_1 (m) // Método de inserção de shunt //
{
// A cada vez, o maior cartão é gerado e inserido na frente de um cartão aleatório. Como você precisa inserir elementos na matriz e espremer todos os elementos subsequentes, um por um, é demorado.
var arr = [0];
for (var i = 1; i <m; i ++) {
Arr.splice (Math.floor (Math.random ()*(i+1)), 0, i);
}
retornar arr;
}
function shuffle_insert (m) // shush // versão otimizada do método de inserção do cartão pode ser comprovada por indução matemática de que esse shuffle é uniforme.
{
// Cada vez que gera o maior cartão e troca posições com um cartão aleatório
var arr = nova matriz (m);
arr [0] = 0;
for (var i = 1; i <m; i ++) {
var rnd = math.floor (Math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
retornar arr;
}
// alerta (shuffle_pick (10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
FUNCNAMES = ["Draw Card", "Draw Card Otimization", "Alterar cartão", "Inserção de cartão", "Otimização de inserção de cartão"]]
M = 10000,
times = [];
for (var i = 0; i <funcs.length; i ++) {
var d0 = new Date ();
funcs [i] (m);
funcnames [i] = (new Date () - d0) + '/t' + funcnames [i];
}
alerta (funcnames.join ('/n'));
</script>
</body>
</html>