Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

Pomoce:

Generacja liczb pseudolosowych bez powtórzeń

W wielu zastosowaniach musimy wygenerować kilka liczb pseudolosowych, tak aby żadna z nich się nie powtarzała. Na przykład przy symulacji gry w karty żaden z graczy nie powinien dostać 5 asów w rozdaniu. Przy losowaniu Totka Lotka wylosowane liczby również nie mogą się powtarzać. Problem ten rozwiązujemy prosto wykorzystując operacje na tablicach.

Metoda 1 - składowanie liczb pseudolosowych w tablicy

Pierwsza metoda jest następująca:

Chcemy wygenerować n  z m  różnych liczb pseudolosowych, gdzie n  ≤ m  (zakres musi obejmować co najmniej n  liczb, w przeciwnym razie nie da się uzyskać n  liczb różnych). Wykorzystujemy tablicę n  elementową, w której będziemy umieszczali wygenerowane liczby.

Pierwszą liczbę pseudolosową generujemy swobodnie i wstawiamy ją do tablicy - musimy zapamiętywać, ile liczb zawiera tablica. Każdą następną liczbę pseudolosową porównujemy z liczbami wstawionymi do tablicy. Jeśli jej tam nie będzie, to dopisujemy tę liczbę do tablicy i operację powtarzamy dotąd, aż tablica się zapełni.

Sposób ten jest szczególnie efektywny, gdy n  jest małe, a m  duże.

Algorytm generacji n liczb pseudolosowych bez powtórzeń

Wejście:

      n  - ilość liczb pseudolosowych do wygenerowania
Wyjście:

      T[ ] - n  elementowa tablica z liczbami pseudolosowymi

Dane pomocnicze:

       i  - indeksy elementów
       licznik  - zlicza wygenerowane liczby pseudolosowe
       p  - liczba pseudolosowa
 

// Generacja liczb pseudolosowych bez powtórzeń
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 20; // określa ilość liczb do wygenerowania

int main()
{
    int T[N], p, i, licznik;
    bool t;

    srand(time(NULL)); // inicjujemy ziarno generatora pseudolosowego


    // generujemy N różnych liczb pseudolosowych w zakresie od 1 do 80

    licznik = 0;
    do
    {
        p = 1 + rand() % 80;

        t = true;
        for(i = 0; i < licznik; i++)
            if(T[i] == p)
            {
                t = false;
                break;
            }

        if(t) T[licznik++] = p;

    } while(licznik < N);

    // wyświetlamy wygenerowane liczby

    for(i = 0; i < N; i++) cout << T[i] << " ";

    cout << endl << endl;

    return 0;
}

Metoda 2 - mieszanie zawartości tablicy

Druga metoda jest następująca:

Chcemy wygenerować n  z m  różnych liczb pseudolosowych. Tworzymy tablicę m elementową i umieszczamy w niej wszystkie liczby pseudolosowe, które chcemy otrzymywać, Następnie w pętli wykonywanej 10 × m razy losujemy dwa indeksy tej tablicy i zamieniamy miejscami elementy wskazywane przez te indeksy. Gdy pętla zakończy swoje działanie, zawartość tablicy będzie potasowana - elementy przestaną być uporządkowane. Teraz wystarczy odczytać z tej tablicy n  pierwszych elementów.

Sposób ten jest szczególnie efektywny, gdy n  jest porównywalne z m, a m  niezbyt duże.

Algorytm pseudolosowego mieszania zawartości tablicy

Wejście:

    m  - ilość elementów tablicy.
    T[ ] - tablica m  elementowa do pomieszania. Elementy mają indeksy od 0 do m-1.
Wyjście:

    T[ ] - tablica z pomieszanymi elementami

Dane pomocnicze:

       i₁,i₂ - indeksy elementów
       i  - zlicza obiegi pętli
       x  - zmienna pomocnicza do zamiany elementów T[ ].
 

// Generacja liczb pseudolosowych bez powtórzeń
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 20; // określa ilość liczb do wygenerowania
const int M = 80; // określa rozmiar tablicy

int main()
{
    int T[M], i, i1, i2, x;

    srand(time(NULL)); // inicjujemy ziarno generatora pseudolosowego


    // Tablicę wypełniamy liczbami od 1 do M

    for(i = 0; i < M; i++) T[i] = i + 1;

    // tablicę mieszamy
    
    for(i = 10 * M; i > 0; i--)
    {
        i1 = rand() % M;
        i2 = rand() % M;

        x     = T[i1];
        T[i1] = T[i2];
        T[i2] = x;
    }

    // wyświetlamy początkowe N liczb z tablicy

    for(i = 0; i < N; i++) cout << T[i] << " ";

    cout << endl << endl;

    return 0;
}

Dla ambitnych: wykorzystując programy z lekcji zaprojektuj symulację Toto Lotka. Użytkownik typuje 10 swoich liczb. Następnie program wykonuje kolejne losowania (np. 10 losowań), sprawdza, czy wylosowano liczby użytkownika i wypisuje wyniki tego sprawdzenia - np. ilość liczb trafionych oraz wartości liczb trafionych w losowaniu. Zastanów się nad sposobem uzyskania i wyświetlania tych wyników.

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe