remplissage d'un tableau avec le nombre aléatoire

Je suis en train de remplir un tableau de 20 entiers avec des nombres de 1 à 20 dans un ordre aléatoire.
voici mon code:

 int lookup[20]={0}; 
 int array[20]={0};
 srand(time(NULL));
 for(int i=0;i<20;++i){ 
    bool done=false;
    while(!done){
      int n=rand()%20;
      if(lookup[n]==0){
          array[i]=n;
          lookup[n]=1;
          done=true;
      }
    }
 }

J'ai créé une liste de choix de la matrice de vérifier si le nombre aléatoire est pas encore choisi, et de les stocker dans un tableau. Comme vous pouvez le voir, j'ai créé 2 boucles, une pour la traversée tableau et le tout pour choisir le nombre aléatoire. Dans chaque boucle while itération, le nombre peut réapparaître et causant une autre boucle while. Est-il plus rapide façon de le faire?

appliquer de nombres aléatoires-générateur de balise
Voir aussi: stackoverflow.com/questions/1218155/..., stackoverflow.com/questions/1816534/random-playlist-algorithm, stackoverflow.com/questions/417831/..., stackoverflow.com/questions/813935/...

OriginalL'auteur James | 2010-03-03

c c++random

19

Vous pouvez remplir le tableau dans l'ordre et ensuite mélanger. Qui permettrait d'éviter d'avoir à toujours faire plus que 20 nombre aléatoire générations.

Shuffle de Fisher-Yates: peut se faire en O(n) fois.

De wikipedia:

Correctement mis en œuvre, le shuffle de Fisher–Yates est impartiale, de sorte que chaque permutation est tout aussi probable. La version moderne de l'algorithme est aussi plutôt efficace, nécessitant seulement un temps proportionnel au nombre d'éléments mélangés et pas d'espace de stockage supplémentaire.

+1 en effet! Knuth Shuffle.
Si votre utilisation de C++ spécifiquement et non C puis graham.roseaux suggestion d'utiliser std:random_shuffle permettra de vous rendre où vous voulez aller sans risque de faire une erreur de mise en œuvre de l'algorithme de shuffle. Si vous êtes à l'aide de C, alors il existe un code de mise en œuvre sur la page de Wikipédia (et probablement ailleurs sur le web) que vous pouvez copier.
Oui! Je suis à l'aide de C++ pour cela. std::random_shuffle est bon d'y aller, mais je pense que je vais essayer de la mise en œuvre de l'algorithme de shuffle. Merci pour la réponse.
Rappelez-vous juste que de réinventer la roue laisse également place à réinventer une grande variété d'insectes, à la fois évidente et subtile.

OriginalL'auteur sfg
15

Regarder std::random_shuffle et std::vector.

Oui! L'utilisation d'un algorithme standard; Fisher-Yates est très facile de se tromper.
Je me suis toujours demandé pourquoi il est appelé random_shuffle. Genre de implique qu'il existe un nonrandom_shuffle.
+1 pour la STL. les tableaux permettent RA Itérateurs. Pas besoin de std::vector.
Si vous allez utiliser le C++, alors vous pourriez aussi bien profiter de tout ce que la STL peut offrir.

OriginalL'auteur graham.reeds

vous pouvez remplir un tableau avec des nombres de 1 à 20 et de l'utilisation std::random_shuffle

remarque vous n'avez pas besoin d'un vecteur est un tableau simple fera.

exemple :

#include <iostream>
#include <algorithm>

using namespace std;

int main( void )
{
        int array[] = { 0, 1, 2, 3, 4 };

        srand( unsigned( time(NULL) ) );

        random_shuffle(array, array+5);

        for(int i=0; i<5; i++)
                cout << array[i] << endl;

        return 0;
}

OriginalL'auteur f4.

1

Il y a la possibilité dans votre code d'une très longue course de la boucle. Si vous êtes à l'intérieur du while(!fait) en boucle il n'y a aucune garantie que vous aurez jamais fini. Évidemment, avec un tableau de 20 éléments, ce ne sera pas dans la pratique à un problème, mais il pourrait causer des problèmes si vous l'appliquer à grande échelle de plusieurs milliers d'éléments.

Plus fiable, la solution serait de remplir le tableau de façon séquentielle et ensuite mélanger par la suite.

"il n'y a aucune garantie que vous aurez jamais fini" - la boucle se termine avec la probabilité 1 si le nombre aléatoire de fonction est assez bon, mais vous êtes tout à fait à droite qui attend d'exécution est médiocre. Dans le cas où la longueur du tableau est plus grand que RAND_MAX, vous avez visiblement un problème, mais c'est effectivement à voir avec le douteux façon que le code tente d'obtenir un nombre aléatoire à partir de 0 .. N-1 avec une distribution uniforme. De Fisher-Yates qui ne rand()%N serait également faible pour un grand N.
Vous avez raison, si je échelle-à-dire 1 million d'éléments, il va sûrement y aura des problèmes de performances.

OriginalL'auteur Dolbz
0

Je l'avais mis les 20 nombres aléatoires dans un tableau, puis la copier à un autre de 20 élément de tableau, trier un tableau, et pour chaque nombre dans le tableau trié, trouver le nombre correspondant dans le tableau non trié, et de placer l'index de la sorte.

ses O(n*n) droit?

OriginalL'auteur Arthur Kalliokoski
0

Si vous pouvez utiliser des récipients, que je venais de remplir un std::set avec les nombres de 1 à 20.

Ensuite, vous pouvez tirer un nombre aléatoire à partir de votre jeu et de l'insérer dans le tableau.

OriginalL'auteur Christian Severin

D'autre voie possible

int array[20]={0};
int values[20];
for(int i = 0; i < 20; i++)
    values[i] = i;
int left = 20;
for(int i = 0; i < 20; i++)
{
    int n = rand() % left;
    array[i] = values[n];
    left--;
    values[n] = values[left];
}

PS rempli avec des chiffres de 0 à 19 ans et pas de 1 à 20. Le même que l'original

n'utilisez pas de rand() % left - voir par exemple members.cox.net/srice1/random/crandom.html

OriginalL'auteur drlazy

Exemple de Code pour de Fisher-Yates:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void shuffle(int array[], size_t size)
{
    if(size) while(--size)
    {
        size_t current = (size_t)(rand() / (1.0 + RAND_MAX) * (size + 1));
        int tmp = array[current];
        array[current] = array[size];
        array[size] = tmp;
    }
}

int main(void)
{
    srand((int)time(NULL));
    rand(); //throw away first value: necessary for some implementations

    int array[] = { 1, 2, 3, 4, 5 };
    shuffle(array, sizeof array / sizeof *array);

    size_t i = 0;
    for(; i < sizeof array / sizeof *array; ++i)
        printf("%i\n", array[i]);

    return 0;
}

OriginalL'auteur Christoph

J'espère que ça aidera:

std::generate(array, array + sizeof(array)/sizeof(int), ::rand);

Vous trouverez ci-dessous le code complet:

#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<iterator>

int main()
{
    int array[] = {1, 2, 3, 4};
    const unsigned SIZE = sizeof(array)/sizeof(int);

    cout << "Array before: ";
    std::copy(array, array+SIZE, std::ostream_iterator<int>(cout, ", "));

    std::generate(array, array+SIZE, ::rand); //answer for your question

    cout << "\nArray arter:  ";
    std::copy(array, array+SIZE, std::ostream_iterator<int>(cout, ", "));
}

Si vous souhaitez avoir de plus petits numéros que vous pouvez faire après la génération:

std::transform(array, array+SIZE, array, std::bind2nd(std::modulus<int>(), 255));

OriginalL'auteur Grzegorz Bazior

quelque chose comme cela?

int n = 20; //total element of array
int random = 0, temp=0, start=1;

for(int i=0; i < n; ++i,++start)
{
    array[i] = start;
}

for(int i=0; i<n ; ++i) 
{
    random=rand()%(n-i)+i;
    //swapping, you can make it as a function
    temp = array[i];
    array[i] = array [random];
    array[random] = temp; 

}

OriginalL'auteur mhd

Vous devez vous connecter pour publier un commentaire.