skip to Main Content

Generatory ciągów

Ostatnio mnie wzięło na stworzenie własnej biblioteki w języku C++, która to biblioteka będzie zawierała różne rzeczy. Pierwszy generator ciągów już pozaliście w czasie czytania bloga. Otóż jest funkcja tworząca tablicę z zapisu "a-zA-Z". Ta funkcja pochodzi z K&R ANSI C,…

Czytaj resztę...

Losowanie liczb bez powtórzeń. Dwa podejścia, dwa języki (C/C++)

Podzieliłem posta na dwie części, dla języka C oraz C++
Dwa pojęcia pomocnicze, aby było wiadomo co przez te słowa rozumiem:

  • zakres losowanych liczb – To jest przedział liczb naturalnych (od 0 do nieskończoności), z których będziemy wybierali liczby
  • ilość losowanych liczb – Liczba elementów będących w tablicy które się nie powtarzają wewnątrz tablicy

Język C

Pierwsze podejście jest intuicyjne sprawdzające się do takiego algorytmu:

  1. Wylosuj liczbę ‚n’
  2. Sprawdź czy istnieje liczba ‚n’ w tablicy ‚tab’
  3. Jeśli TAK to przejdź do kroku 1
  4. Jeśli NIE to dodaj n do tablicy ‚tab’
  5. Jeśli potrzeba więcej liczb przejdź do kroku 1
Jednak przy losowaniu z małego zakresu liczb o dużej ilości (np. zakres 1..15, ilość liczb 10) może spowodować częsty przypadek gdy wylosowana zmienna n znajduje się już w tablicy. Gdybyśmy chcieli wyliczyć złożoność obliczeniową powyższego algorytmu, to wynik były O(0). Oznacza algorytm który mógł się wcale nie wykonać (np. gdyby zawsze byłaby losowana wartość już istniejąca w tablicy.
Czytaj resztę...
Back To Top