Losowanie bez powtórzeń

[lekcja] Rozdział 21. Losowanie liczb całkowitych bez powtórzeń.

Kolejnym zagadnieniem, którym się zajmiemy w niniejszym kursie C++ jest losowanie liczb całkowitych bez powtórzeń. Często zdarza się bowiem, że właśnie takiej funkcjonalności w naszym programie potrzebujemy, a skoro tak to warto ją omówić i przy okazji utrwalić sobie materiał z poprzednich rozdziałów niniejszego kursu.

Standardowe narzędzia do losowania liczb bez powtórzeń

Pierwszą rzeczą o której należy powiedzieć zabierając się za niniejszy temat jest fakt, że standardowych narzędzi do losowania bez powtórzeń po prostu nie ma. Powodów dlaczego nie ma takiej funkcji w bibliotece C bądź C++ można znaleźć co najmniej kilka, np.:

programista z przeciętną wiedzą o programowaniu powinien umieć sobie ją napisać;
losowanie może odbywać się z określonego zbioru przypadkowych liczb bądź z określonego przedziału;
pula liczb pozostałych do wylosowania może być przechowywana lub nie.

Być może nie jesteś jeszcze tego świadom, ale z obecną wiedzą powinieneś być już w stanie napisać program losujący liczby bez powtórzeń.

Formułujemy problem

Na początek sformułujmy nasz problem: Program ma nam wylosować 5 liczb bez powtórzeń. Liczby wylosowane mają być z przedziału od 1 do 10.

Analiza problemu losowania liczb bez powtórzeń

Bazą wyjściową dla każdego problemu programistycznego powinna być jego analiza. Analiza ta ma prowadzić do rozbicia problemu na czynniki pierwsze, tj. powinno nastąpić sformułowanie literalnie co program krok po kroku ma robić. Stwierdzenie pt. 'Losowanie liczb bez powtórzeń' dla programisty jest tylko tytułem opisującym ogólnie rozwiązywany problem. Dla programisty ważne jest zastanowienie się co się kryje pod każdym ze słów rozpatrywanego zagadnienia. Tak więc przejdźmy do analizy:

Losowanie liczb - ok, losuję liczbę, ale z czego? Z przedziału? Ze zbioru dostępnych liczb? Zbiór ten się będzie zmniejszał czy nie?
bez powtórzeń - Liczby się nie mają powtarzać. Skąd komputer ma wiedzieć, czy liczba już nie została wcześniej wylosowana? On przecież nie tego nie pamięta... będzie potrzebna tablica do przechowywania wylosowanych wyników.

Powyższe punkty pokazują serię pytań, które doświadczony programista zada sobie podchodząc do problemu - Ty się będziesz musiał tego nauczyć i to jest podstawowy element, który tworzy przepaść między programistą, który zaczyna swoją przygodę, a tym który radośnie siada do swojego komputera i się zastanawia: 'co by tu dzisiaj fajnego napisać...'. Nie bój się eksperymentować, nie bój się myśleć i nie bój się podążać samodzielnie przez napotykane problemy - każdy programista jest samodzielny bo miał silną wolę by stanąć na własne nogi. Bądź więc ambitny!

Formułujemy działanie programu

Skoro ustaliliśmy sobie mniej więcej co nasz program powinien robić to poukładajmy teraz ten zlepek chaotycznych myśli w jakiś konkretniejszy plan działania.

1. Losuję liczbę z przedziału od 1 do 10;
2. Sprawdzam, czy wylosowana liczba przypadkiem wcześniej już nie padła;
3. Jeżeli wylosowana liczba nie padła zapisuję ją do puli liczb wylosowanych i zwiększam liczbę wylosowanych liczb.
4. Jeżeli wylosowana liczba padła wracam do kroku 1.
5. Sprawdzam, czy wylosowałem już 5 liczb. Jeżeli nie - przechodzę do punktu 1.

W tym momencie mamy opisany już słowami problem. Teraz krok po kroku uzupełniamy nasz program i jeżeli jest taka możliwość sprawdzamy po każdym kroku czy program aby na pewno zachowuje się do danego momentu prawidłowo. Czasami nie jest możliwe stopniowe sprawdzanie poprawności działania programu i dopiero po złożeniu wszystkich naszych myśli w całość zaczyna program funkcjonować zgodnie z naszymi założeniami.

Program rozwiązujący zadanie

Zanim zaczniesz uważnie analizować rozwiązanie zadania polecam podjąć samodzielną walkę z problemem. Pośpiech w programowaniu jest zawsze zgubny.

#include <iostream>
#include <cstdlib>
#include <ctime>

bool czyBylaWylosowana( int iLiczba, int tab[], int ile )
{
if( ile <= 0 )
return false;

int i = 0;
do
{
if( tab[ i ] == iLiczba )
return true;

i++;
} while( i < ile );

return false;
}

int wylosuj()
{
return( rand() % 10 ) + 1;
}

int main()
{
srand( time( 0 ) );
int wylosowane[ 5 ];
int wylosowanych = 0;
do
{
int liczba = wylosuj();
if( czyBylaWylosowana( liczba, wylosowane, wylosowanych ) == false )
{
wylosowane[ wylosowanych ] = liczba;
wylosowanych++;
} //if
} while( wylosowanych < 5 );

wylosowanych = 0;
do
{
std::cout << wylosowane[ wylosowanych ] << std::endl;
wylosowanych++;
} while( wylosowanych < 5 );

return 0;
}

Zadanie domowe

1. Napisz program, który wczyta 3 liczby podane przez użytkownika do tablicy, a następnie wylosuje 2 z nich bez powtórzeń. Wynik wypisz na ekran. Postaraj się napisać ten program w oparciu o funkcje.

Uwaga!
Treść niniejszego rozdziału nie zawiera rozwiązania problemu lecz wskazówki - zadanie wymaga przede wszystkim zastanowienia się i przeprowadzenia szczegółowej analizy problemu do konkretnego przypadku przedstawionego w zadaniu. Zadanie nie wymaga większej wiedzy z zakresu programowania niż ta, która została przedstawiona do tej pory.

2. Zmodyfikuj program z pierwszego zadania tak, aby użytkownik musiał podać 10 liczb, a 8 z nich będzie losowanych bez powtórzeń. Sprawdź czy wyniki są poprawne.

Poprzedni dokument	Następny dokument
Funkcje, a słowo kluczowe return	Pętla for

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.