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. static void CiagGould(int k)
  2. {
  3. List<int> lista = new List<int>();
  4. while (k-- > 0)
  5. {
  6. int ile = lista.Count > 0 ? 2 : 1;
  7. for (int i = lista.Count - 1; i > 0; i--)
  8. {
  9. lista[i] = lista[i] + lista[i - 1];
  10. if (lista[i] % 2 == 1)
  11. {
  12. ile++;
  13. }
  14. }
  15. lista.Add(1);
  16. Console.Write("{0} ", ile);
  17. }
  18. }

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. static void CiagGould(int k)
  2. {
  3. for (int i = 0; i < k; i++)
  4. {
  5. int ile = 0;
  6. int tmp = i;
  7. while (tmp > 0)
  8. {
  9. ile += tmp & 1;
  10. tmp >>= 1;
  11. }
  12. ile = (int)Math.Pow(2, ile);
  13. Console.Write("{0} ", ile);
  14. }
  15. }

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. static void Main(string[] args)
  2. {
  3. Console.Write("Ile wyrazów wypisać?\n k = ");
  4. int k = Convert.ToInt32(Console.ReadLine());
  5. CiagGould(k);
  6. Console.ReadKey();
  7. }