Zadanie 1. Kod Graya

Kod Graya jest to kod dwubitowy niepozycyjnykod niepozycyjnyniepozycyjny, charakteryzujący się tym, że każde dwa kolejne jego słowa różnią się dokładnie jednym bitem. Pierwsze i ostatnie słowa również spełniają tę zasadę.

W 1‑bitowym kodzie Graya występują jedynie dwa słowa: 0 oraz 1.

W 2‑bitowym kodzie Graya występują następujące słowa: 00, 01, 11 i 10.

Jeżeli chcemy rozszerzyć kod Graya o 1 bit, posługujemy się następującym algorytmem:

1. Do istniejących słów w kodzie Graya dopisz te same słowa, lecz w odwrotnej kolejności (jak w odbiciu lustrzanym).

2. Na początku pierwszej połowy słów zapisz 0, natomiast na początku drugiej: 1.

00 -> 00 -> 000
01	  01	001
11	  11	011
10	  10	010
	  10	110
      11	111
      01	101
      00	100

Treść polecenia

Zapisz w wybranej przez siebie notacji (w postaci pseudokodu lub w wybranym języku programowania) algorytm, który wygeneruje n-bitowy kod Graya.

Specyfikacja problemu:

Dane:

• n – liczba naturalna

Wynik:

• kod[] – tablica napisów zawierająca słowa n-bitowego kodu Graya

Możesz skorzystać z funkcji tablica.dopisz(x), która zwiększa rozmiar tablicy tablica o 1 i w dodanym miejscu umieszcza napis x, oraz funkcji pot(x,y) zwracającej operację podnoszenia liczby x do potęgi y.

Możesz przeprowadzać konkatenację (łączenie) napisów za pomocą wyrażenia +. Przykładowo zapis 0 + 1 będzie oznaczał połączenie tych dwóch napisów i zwróci wartość 01.

Rozwiązanie

Do wygenerowania kodu używamy algorytmu zawartego w treści zadania. Stosujemy jedynie dozwolone operacje. Rozwiązanie zapisane za pomocą pseudokodu prezentuje się następująco:

funkcja wygenerujKod(n):
	jeżeli n <= 0:
    	zwróć pustą tablicę
	
    kody ← zainicjuj pustą tablicę
    
    kody.dopisz("0")
    kody.dopisz("1")
    
    i ← 2
    
    dopóki prawda wykonuj:
    	jeżeli i >= pot(2, n):
        	przerwij pętlę
        
        dla j = i-1, i-2, ..., 0 wykonuj:
        	kody.dopisz(kody[j])
        
        dla j = 0, 1, ..., i-1 wykonuj:
        	kody[j] ← "0" + kody[j]
            
        dla j = i, i+1, ..., (2*i)-1 wykonuj:
        	kody[j] ← "1" + kody[j]
            
        i ← i*2
        
    zwróć kody

Na początku inicjujemy tablicę kody wartościami 0 oraz 1. Następnie, dopóki nie osiągniemy oczekiwanego rozmiaru kodu Graya, tworzymy kolejne słowa wedle algorytmu. Ponieważ nie uwzględniono w treści zadania żadnych wymagań dotyczących złożoności obliczeniowej, nie bierzemy jej pod uwagę.

Słownik