Strona główna » Algorytmy » Artykuły » Ciąg Goulda
 

Ciąg Goulda

https://mattomatti.com/a0232

Definicja

Kolejne wyrazy ciągu Goulda określają ile liczb nieparzystych znajduje się w kolejnych wierszach trójkąta Pascala. Najprostszym sposobem jest wypisanie trójkąta Pascala, a następnie policzeniu liczb nieparzystych w każdym wierszu:

Pierwsze wyrazy takiego ciągu to: 1, 2, 2, 4, 2, 4, 4, 8, 2, 4, 4, 8, 4, 8, 8, 16, 2, 4, 4, 8, ..

Implementacja

Wyznaczanie Trójkąta

Algorytm dynamiczny to najefektywniejszy sposób wyznaczania kolejnych wierszy trójkąta Pascala. Podczas wyznaczania kolejnych elementów należy zliczać ile nieparzystych elementów wystąpiło. Dodatkowo należy pamiętać, że w pierszym wierszu jest tylko jedna wartość 1, a pozostałych są dokładnie dwie takie wartości. Oto przykładowy kod:

C++C#
Python
  1. def CiagGould(k):
  2.   lista = []
  3.   while (k > 0):
  4.     ile = 2 if len(lista) > 0 else 1
  5.     for i in range(len(lista) - 1, 0, -1):
  6.       lista[i] = lista[i] + lista[i - 1]
  7.       if (lista[i] % 2 == 1):
  8.         ile+=1
  9.     lista.append(1)
  10.     print(ile, end=" ")
  11.     k -= 1

Przedstawiony algorytm wyznacza k pierwszych liczb ciągu Goulda i wypisuje na standardowy strumień kolejne wartości licznika ile. Warto zauważyć, że w pętli są wyznaczane jedynie elementy pomiędzy jedynkami stojących na granicy każdego wiersza, dlatego początkowo licznik przyjmuje ich ilość w danym wierszu.

Bez Trójkąta

Mogłoby się wydawać, że nie istnieje lepsza metoda na wyznaczenie ciągu. Istnieje jednak pewna zależność między binarną reprezentacją numeru wiersza, a ilością nieparzystych elementów w i-tym wierszu. W tym celu należy zliczyć ile jest bitów 1 w zapisie binarnym, a następnie podnosimy 2 do potęgi do znalezionej wartości. Oto kod:

C++C#
Python
  1. def CiagGould(k):
  2.   for i in range(k):
  3.     ile = 0
  4.     tmp = i
  5.     while (tmp > 0):
  6.       ile += tmp & 1
  7.       tmp >>= 1
  8.     ile = pow(2, ile)
  9.     print(ile, end=" ")

Dla k wierszy inicjujemy licznik na zero oraz kopiujemy aktualny numer wiersza. Następnie w pętli przechodzimy po kolejnych bitach tak długo, aż wyzerujemy wartość. Za każdym razem dodajemy najstarszy bit liczby. Na koniec obliczamy 2ile i wypisujemy wynik.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programau:

C++C#
Python
  1. k = int(input("Ile wyrazów wypisać?\n k = "))
  2. CiagGould(k)