Strona 1

[lekcja] Losowanie bez powtórzeń | Kurs C++ » Poziom 2

2011-11-12 17:13:45

http://cpp0x.pl/kursy/Kurs-C++/Poziom-2/Losowanie-bez-powtorzen/293

Darmowe kursy Online

»

Kurs C++

»

Poziom 2

Autor: Piotr Szawdyński

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.

Standardowenarzę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łujemyproblem

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łujemydziałanieprogramu

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ącyzadanie

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

jest zawsze zgubny.

Strona 2

[lekcja] Losowanie bez powtórzeń | Kurs C++ » Poziom 2

2011-11-12 17:13:45

http://cpp0x.pl/kursy/Kurs-C++/Poziom-2/Losowanie-bez-powtorzen/293

Architektserwisu: Piotr Szawdyński

© Wszelkieprawa zastrzeżone2005-2011

C/C++

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

Wszystkieteksty są chronioneprawami autorskimi. Kopiowanielub rozpowszechnianietreści poza niniejszymserwisem jest

zabronione.

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