Seria algorytmów poświęconych grze liczbowej LOTTO.
Oczywiście ani komputer, ani program ELI nie pomoże nam wygrać w Lotto. Prezentowane algorytmy mogą jedynie pomóc w analizie gry i ocenie szans wygranej. Zarazem jest tu pole do obrazowego przejścia od prostych zagadnień, takich jak losowanie liczb do bardziej skomplikowanych - takich jak porządkowanie ciągu wylosowanych liczb, statystyka wyników, czy obliczanie prawdopodobieństwa wygranej.
Pierwszy algorytm - losowanie pojedynczej liczby z zakresu od 1 do 49.
Jest to prosty algorytm liniowy o następujących krokach:
1. początek algorytmu,
2. wylosowanie liczby - zmiennej traf przypisujemy wartość 1 + random(49),
3. wyprowadzenie wyniku - wartości zmiennej traf,
4. zakończenie algorytmu.
Algorytm ułożony z klocków widoczny jest na rysunku obok.
Jest on zapisany w projekcie LOTTO1.LIP
Ślad tego algorytmu wyeksportowany z programu przedstawia się następująco:
Plansza Poziom Wynik Opis
------------------------------------------------------------------
lotto1 1 Lotto1: Losowanie liczby
lotto1 1 31 traf:=1+random(49)
lotto1 1 31 Wylosowana:
lotto1 1 Koniec.
Proponuję proste ćwiczenie: skrócić przedstawiony algorytm (wskazówka: wykorzystać możliwości klocka wyprowadzenia wyniku).
Drugi algorytm - losowanie n liczb.
Ponieważ na kuponie Lotto należy skreślić co najmniej 6 liczb następny algorytm przedstawia losowanie n liczb.
Jego kroki są następujące:
2. wprowadzenie danej - ile (Ile liczb losować?),
3. nadanie zmiennej numerującej liczby (i) wartości 1,
4. sprawdzenie, czy i <= ile czyli czy należy kontynuować losowania,
5. jeśli TAK, to:
6. wyprowadzenie wyniku - wartości 1 + random(49),
7. zwiększenie zmiennej i o 1,
8. powrót do punktu 4,
9. jeśli NIE, to:
10. zakończenie algorytmu.
Algorytm ułożony z klocków przedstawia rysunek obok.
Jest on zapisany w projekcie LOTTO2.LIP.
A oto ślad realizacji tego algorytmu:
lotto2 1 Lotto2: Losowanie N liczb
lotto2 1 6 Ile liczb losować?
lotto2 1 1 i:=1
lotto2 1 Prawda i<=ile
lotto2 1 48 Wylosowana:
lotto2 1 2 i:=i+1
lotto2 1 18 Wylosowana:
lotto2 1 3 i:=i+1
lotto2 1 26 Wylosowana:
lotto2 1 4 i:=i+1
lotto2 1 49 Wylosowana:
lotto2 1 5 i:=i+1
lotto2 1 43 Wylosowana:
lotto2 1 6 i:=i+1
lotto2 1 4 Wylosowana:
lotto2 1 7 i:=i+1
lotto2 1 Fałsz i<=ile
lotto2 1 Koniec losowań.
Prezentowany algorytm nie jest wygodny dla użytkownika, ponieważ losowane liczby nie są nigdzie zapisywane.
Trzeci algorytm - losowanie n liczb z zapisem na taśmie
Jako następne ćwiczenie proponuję przerobienie poprzedniego algorytmu na algorytm wykorzystujący taśmę do zapisywania wylosowanych liczb. Budowa algorytmu jest identyczna, wystarczy więc zamienić klocek Wyprowadzenie wyniku na klocek Zapis na taśmie. Jedynym koniecznym dodatkiem jest klocek przewinięcia taśmy na początek wstawiony przed pętlą kolejnych losowań. Oczywiście do projektu należy włączyć okno taśmy, które będzie zawierać wylosowane liczby.
Algorytm losowania N liczb z zapisem na taśmie przedstawiony na rysunku obok jest zapisany w projekcie LOTTO3.LIP. W skład projektu wchodzi plansza LOTTO3.LIS i taśma LOTTO3.LIT.
Zauważmy jeszcze, że nasz poprzedni algorytm dość szczęśliwie wylosował 6 różnych liczb, choć wcale tak być nie musiało. Również trzeci algorytm może kilkakrotnie wylosować i zapisać na taśmie tę samą liczbę. Jak powinien wyglądać algorytm, który będzie zawsze losował n różnych liczb?
Czwarty algorytm - losowanie n liczb bez powtórzeń.
Tym razem zadanie jest trudniejsze. Aby uniknąć powtórzeń należy przy każdym kolejnym losowaniu sprawdzać czy wylosowana liczba jest już zapisana na taśmie i jeśli tak jest, to powtarzać losowanie. Najlepszym rozwiązaniem jest dodanie do algorytmu procedury, która będzie wykonywała losowania i sprawdzania. Najpierw jednak zmodyfikujemy główny algorytm:
Przede wszystkim pierwsza wylosowana liczba nie musi być sprawdzana, można ją wylosować i zapisać na taśmie przed pętlą kolejnych losowań. W pętli natomiast będziemy:
- losować i sprawdzać (procedura LosujNowa),
- zapisywać wylosowaną liczbę na taśmie,
- zwiększać o 1 licznik wylosowanych liczb.
Algorytm główny przedstawiony na rysunku obok jest zapisany w projekcie LOTTO4.LIP na planszy LOTTO41.LIS. W skład projektu wchodzą jeszcze: taśma LOTTO4.LIT i plansza z procedurą LOTTO42.LIS.
Procedura LosujNowa zbudowana na oddzielnej planszy ma dwa parametry: zakres - jaka ma być największa liczba, którą można wylosować, nr - numer losowanej liczby. Składa się ona z następujących kroków:
- wylosowanie kolejnej liczby (los),
- ustawienie indeksu k na zero,
- przewinięcie taśmy na początek,
- w pętli: dopóki k<nr
odczytanie kolejnej liczby z taśmy,
porównanie jej z wylosowaną: sprawdzenie, czy są różne,
jeśli TAK, to zwiększenie indeksu k o 1,
jeśli NIE, to skok na początek procedury.
Procedura ta jest funkcją - zwraca do głównego algorytmu wartość zmiennej los. W tym celu wypełnione zostało okienko Wyrażenie w klocku Koniec procedury oraz okienko Nazwa zmiennej w klocku Wywołanie procedury w głównym algorytmie.
Oto przykładowe wyniki działania
algorytmu trzeciego algorytmu czwartego
Taśma: c:\eli2\lotto\lotto3.lit
0 47
1 39
2 19
3 29
4 47
5 20
Taśma: c:\eli2\lotto\lotto4.lit
0 42
1 4
2 17
3 11
4 33
5 12
Piąty algorytm - porządkowanie wylosowanych liczb.
Nie możemy chyba zadowolić się takim wynikiem - wylosowane liczby nie są uporządkowane rosnąco. Na szczęście ten problem został już rozwiązany. Mamy do wyboru:
· algorytm sortowania bąbelkowego - Lekcja 17 Pomocy, projekt: AZ7SORT.LIP,
· algorytm sortowania przez scalanie - Lekcja 29 Pomocy, projekt: AR9QSORT.LIP (trzeba jedynie przepisać wyniki losowania z taśmy do tablicy),
· algorytm porządkowania bąbelkowego - M. Sysło Algorytmy: par. 6.1, projekt BABELKI.LIP,
· algorytm porządkowania przez wybór - M. Sysło Algorytmy: par. 6.2, projekt WYBOR.LIP,
· algorytm porządkowania przez umieszczanie - M. Sysło Algorytmy: par. 10.1, projekt UMIESZCZ.LIP,
· algorytm porządkowania przez scalanie - M. Sysło Algorytmy: par.10.2.2, projekt SCALSORT.LIP.
Tutaj przedstawiam algorytm porządkowania przez wybór (wybieranie proste) zapożyczony z książki: Sysło M.M.: Algorytmy WSiP, Warszawa, 1997 (skopiowany z dołączonej do książki dyskietki z algorytmami w ELI i programami w Pascalu i trochę przerobiony).
Algorytm składa się z następujących kroków:
1) Dla i = 1,2, ..., n -1 wykonaj kroki 2 i 3,
2) ZnajdŸ k takie, że xk jest najmniejszym elementem podciągu xi, ..., xn,
3) Zamień miejscami elementy xi oraz xk.
Podprogram MinInd znajduje indeks najmniejszego elementu w podciągu zaczynającym się od i-tej komórki ciągu. Zamiana elementów miejscami jest wykonywana w programie głównym.
Algorytm główny jest zapisany w projekcie LOTTO5S.LIP na planszy LOTTO51S.LIS. W skład projektu wchodzą jeszcze: plansza z procedurą LOTTO52S.LIS, tablica LOTTO5S.LIA, taśma LOTTO4.LIT.
główny algorytm (LOTTO51S.LIS) procedura MinInd (LOTTO52S.LIS)
Teraz kiedy już wiemy jak wylosować i uporządkować liczby możemy przystąpić do wypełniania całego kuponu Lotto.
Szósty algorytm - losowanie całego kuponu.
Przypomnijmy, że algorytm czwarty losował i umieszczał na taśmie ciąg n liczb bez powtórzeń. Algorytm piąty przepisywał wylosowane liczby do tablicy i porządkował je. Oba główne algorytmy przerobimy obecnie na procedury
procedura losuj z algorytmu czwartego procedura sortuj z algorytmu piątego
procedura losuj procedura sortuj
ma dwa parametry: ma dwa parametry:
ile - ile liczb n - ile liczb składa się
ma być losowanych, na jeden zakład,
(np. 6) (np. 6)
zakres - jaki jest zakres nrkol - do której kolumny
losowanych liczb wpisywać liczby po
(np. 49) uporządkowaniu.
Teraz wystarczy dopisać główny algorytm, w którym:
· wczytujemy ile ma być liczb (ile) oraz ile losowań (ileLos),
· ustalamy zakres losowanych liczb (zakres := 49),
· w pętli dla i = 1 do ileLos
wywołujemy procedurę losuj z parametrami: ile, zakres,
wywołujemy procedurę sortuj z parametrami: ile, i.
Wyniki działania algorytmu oglądamy w tablicy (LOTTO6.LIA).
Algorytm główny jest zapisany w projekcie LOTTO6.LIP na planszy LOTTO61.LIS. W skład projektu wchodzą jeszcze plansze:
z procedurą losuj - LOTTO62.LIS i pomocniczą procedurą LosuNowa - LOTTO63.LIS,
z procedurą sortuj - LOTTO64.LIS i pomocniczą procedurą MinInd - LOTTO65.LIS,
tablica LOTTO6.LIA, taśma LOTTO6.LIT.
Tablica po wypełnieniu (dla 6 liczb i 5 losowań) może wyglądać następująco:
Tablica: c:\programy\eli201\lotto\lotto6.lia
0 1 2 3 4 5
0 6
1 10 4 1 1 5
2 12 20 23 2 7
3 17 21 27 12 11
4...
Halbart.Liber