Generator LFG

Opóźniony generator Fibonacciego, zwany generatorem LFG ma nazwę wynikającą z podobieństwa wzoru, który jest wykorzystywany w algorytmie LFG do definicji ciągu Fibonacciego.

Ciąg Fibonacciego:

x n   =   x n     1 + x n 2

LFG:

x n   = ( x n j   @   x n k )   m o d   m ,         0   <   j   < k

Gdzie:

  • xIndeks dolny i – kolejna wygenerowana liczba,

  • m – zakres generowanych liczb od 0 do m - 1,

  • @ – dowolne działanie np. dodawanie, odejmowanie.

Algorytm wykorzystuje do działania tablicę liczb o długości k. Wartości j i k są tak ustalone, by wynikiem generatora był najdłuższy możliwy cykl wartości.

Obliczenie kolejnej wartości xIndeks dolny i polega na dodaniu do siebie wartości z tablicy x[] o indeksach j - 1k - 1. Następnie indeks elementu tablicy przesuwany jest w lewo o jedno miejsce, a na ostatniej pozycji umieszczana jest wyliczona wartość pseudolosowa.

Dane:

  • jk – współczynniki,

  • m – zakres generowanych liczb od 0 do m - 1,

  • x[k]k - elementowa tablica,

  • n – ilość liczb do wygenerowania.

Linia 1. ile znak równości 0. Linia 2. dopóki ile otwórz nawias ostrokątny n wykonuj dwukropek. Linia 3. dla i znak równości 0 przecinek 1 przecinek 2 przecinek kropka kropka kropka przecinek k minus 1 wykonuj dwukropek. Linia 4. jeżeli x otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości znak równości 0 wykonaj dwukropek. Linia 5. wynik znak równości otwórz nawias okrągły x otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy at x otwórz nawias kwadratowy k minus 1 zamknij nawias kwadratowy zamknij nawias okrągły mod m. Linia 6. jeżeli i otwórz nawias ostrokątny k minus 1 wykonaj dwukropek. Linia 7. x otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości x otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy. Linia 8. w przeciwnym wypadku wykonaj dwukropek. Linia 9. x otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości wynik. Linia 10. wypisz wynik.
Polecenie 1

Wykorzystując algorytm LFG, wygeneruj 7 wartości pseudolosowych z przedziału od 0 do 14 dla podanej tablicy x[] oraz współczynników j oraz k.

Swój program przetestuj dla następujących wartości:

Linia 1. j znak równości 3. Linia 2. k znak równości 7. Linia 3. x otwórz nawias kwadratowy k zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 4 przecinek 2 przecinek 9 przecinek 1 przecinek 10 przecinek 7 przecinek 3 zamknij nawias klamrowy.

Specyfikacja problemu:

Dane:

  • j – liczba naturalna; pierwszy ze współczynników

  • k – liczba naturalna; drugi ze współczynników

  • x[k]k-elementowa tablica liczb naturalnych

Wynik:

Program wyświetla liczby wygenerowane za pomocą algorytmu LFG.

R1I6eBaUhlu7C
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Polecenie 2

Porównaj swoje rozwiązanie z prezentacją.

RoGAW86Uo5fyp1
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
Polecenie 3

Dodaj do swojego programu komentarze tak, żeby był zrozumiały dla osoby, która nie potrafi programować.