Pomoce:

Instalacja Code Blocks i tworzenie projektu aplikacji konsoli.
Wprowadzenie do języka C++, strumienie i zmienne
Komputer podejmuje decyzje
Pętle warunkowe
Pętla iteracyjna
Generacja liczb pseudolosowych

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 nm (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
 

Krok 1: licznik ← 0 ; zerujemy licznik wygenerowanych liczb pseudolosowych
Krok 2: p ← liczba pseudolosowa ; generujemy liczbę pseudolosową
Krok 3: i ← 0  
Krok 4: Jeśli i = licznik, to idź do kroku 8  
Krok 5: Jeśli T[i] = p, to idź do kroku 2 ; sprawdzamy, czy w tablicy już jest liczba p. Jeśli tak, generujemy nową liczbę p
Krok 6: ii + 1 ; adresujemy kolejny element tablicy
Krok 7: Idź do kroku 4 ; kontynuujemy przeglądanie tablicy
Krok 8: T[licznik] ← p ; dopisujemy liczbę p do tablicy
Krok 9: liczniklicznik + 1 ; zwiększamy licznik
Krok 10: Jeśli licznik < n, idź do kroku 2 ; jeśli nie wygenerowaliśmy jeszcze n liczb, kontynuujemy pętlę
Krok 11: Zakończ  

 

 

// 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:

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

Krok 1: i ← 10 × m  
Krok 2: Jeśli i = 0, to zakończ  
Krok 3: i1 ← liczba pseudolosowa od 0 do m - 1 ; losujemy dwa indeksy elementów
Krok 4: i2 ← liczba pseudolosowa od 0 do m - 1  
Krok 5: xT[i1] ; elementy zamieniamy miejscami
Krok 6: T[i1] ← T[i2]  
Krok 7: T[i2] ← x  
Krok 8: ii - 1  
Krok 8: Idź do kroku 2  

 

// 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.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

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