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:

  1. void CiagGould(int k) {
  2.   vector<int> lista;
  3.   while (k-- > 0) {
  4.     int ile = lista.size() > 0 ? 2 : 1;
  5.     for (int i = lista.size() - 1; i > 0; i--) {
  6.       lista[i] = lista[i] + lista[i - 1];
  7.       if (lista[i] % 2 == 1) {
  8.         ile++;
  9.       }
  10.     }
  11.     lista.push_back(1);
  12.     cout << ile << " ";
  13.   }
  14. }

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:

  1. void CiagGould(int k) {
  2.   for (int i = 0; i < k; i++) {
  3.     int ile = 0;
  4.     int tmp = i;
  5.     while (tmp > 0) {
  6.       ile += tmp & 1;
  7.       tmp >>= 1;
  8.     }
  9.     ile = pow(2, ile);
  10.     cout << ile << " ";
  11.   }
  12. }

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:

  1. int main () {
  2.   int k;
  3.   cout << "Ile wyrazow wypisac?\n k = ";
  4.   cin >> k;
  5.   CiagGould(k);
  6.   system("pause");
  7.   return 0;
  8. }