Informatyka dla klas II

Zadanie mieszania, tasowania (ang. shuffle) zawartości tablicy sprowadza się do wykonywania w pętli zamiany miejscami dwóch elementów tablicy o wylosowanych indeksach. Pętla musi być wykonana tyle razy, aby tasowanie objęło wszystkie elementy – w praktyce wystarcza ilość wykonań równa 3n, gdzie n  jest ilością elementów.

Algorytm mieszania pseudolosowego

Wejście

n	–	liczba elementów w tablicy, n  N
Z[ ]	–	tablica elementów, indeksy rozpoczynają się od 0

Wyjście:

Tablica Z[ ] z potasowaną zawartością

Zmienne pomocnicze

i	–	licznik obiegów pętli. i  N
x	–	przechowuje element tablicy Z[ ] przy zamianie zawartości. Typ ten sam, co elementy tablicy Z[ ].
losowa(x)	–	funkcja zwracająca liczbę pseudolosową z zakresu od 0 do x  - 1

Lista kroków:

K01:	Dla i  = 1,2,...,3n: wykonuj K02...K07	; tasowanie wykonujemy w pętli
K02:	i1 ← losowa(n)	; losujemy pierwszy indeks
K03:	i2 ← losowa(n)	; losujemy drugi indeks
K04:	x  ← Z[i1]	; zamieniamy miejscami Z[i1] i Z[i2]
K05:	Z[i1] ← Z[i2]
K06:	Z[i2] ← x
K07:	Zakończ

Losowanie bez powtórzeń

Zadanie losowania bez powtórzeń można rozwiązać na kilka różnych sposobów. Jeśli przedział <a,b> jest mały (np. zawiera 80 kolejnych liczb Multi-Lotka), to możemy go odwzorować w tablicy, następnie zawartość tej tablicy potasować poprzednio podanym algorytmem i jako wynik zwrócić pierwsze n  elementów. Tasowanie nie dubluje elementów tablicy, zatem otrzymamy n  liczb bez powtórzeń. Taki algorytm posiada klasę złożoności obliczeniowej O(n).

Jeśli przedział <a,b> jest bardzo duży, a n  stosunkowo małe, to postępujemy w sposób następujący. Przygotowujemy pustą tablicę o n  elementach. Losujemy liczbę pseudolosową. Jeśli wylosowana liczba jest już w tablicy, to losujemy ponownie dotąd, aż wylosowanej liczby nie będzie w tablicy. Liczbę dopisujemy do tablicy. Jeśli tablica jest zapełniona, kończymy. W przeciwnym razie powtarzamy losowanie. Algorytm w takiej postaci posiada optymistyczną klasę złożoności obliczeniowej O(n²).

Algorytm losowania bez powtórzeń

Wejście

n	–	liczba określająca, ile liczb pseudolosowych bez powtórzeń należy wylosować, n  N
a,b	–	liczby określające całkowity przedział losowania, b  - a  ≥ n, a,b  C

Wyjście:

n  różnych od siebie liczb pseudolosowych z przedziału <a,b>

Zmienne pomocnicze

T[ ]	–	tablica przechowująca wylosowane liczby pseudolosowe. Indeksy od 0 do n-1.
i	–	licznik wylosowanych liczb pseudolosowych. i  N
j	–	wykorzystywane do przeszukiwania tablicy T[ ].  j  N
x	–	wylosowana liczba pseudolosowa
losowa(x)	–	funkcja zwracająca liczbę pseudolosową z zakresu od 0 do x  - 1

Lista kroków:

K01:	Dla i  = 0,1,...,n-1 wykonuj K02...K06
K02:	x  ← a  + losowa(b  - a  + 1)	; losujemy liczbę pseudolosową
K03:	Dla j  = 0,1,...,i  - 1 wykonuj K04	; sprawdzamy, czy wylosowana liczba jest w T[ ]
K04:	Jeśli T[j] = x, to idź do K02	; jeśli tak, powtarzamy losowanie
K05:	T[i] ← x	; jeśli nie, zapamiętujemy w T[ ] wylosowaną liczbę
K06:	Wyprowadź x	; wyprowadzamy liczbę na wyjście
K07:	Zakończ

Ćwiczenie

Zaprojektuj symulator totolotka. Użytkownik typuje 6 liczb z zakresu od 1 do 49. Następnie program dokonuje losowania 6 liczb z 49 bez powtórzeń i wypisuje, ile liczb trafił użytkownik. Działanie programu zatrzymuje się po trafieniu 6 liczb. Program powinien wtedy wypisać całkowitą liczbę wykonanych losowań.

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