Strona główna » Algorytmy » Teoria Liczb » Liczby Sześciokątne
 

Liczby Sześciokątne

https://mattomatti.com/a0121

Definicja

Liczby Sześciokątne to liczby naturalne, które opisują schemat złożony z coraz większych sześciokątów. Wyraz można obliczyć ze wzoru Hn = 3n(n - 1) + 1 co odpowiada sumowaniu wszystkich wierzchołków sześciokątów oddzielnie. Poniżej została przedstawiona graficzna ilustracja liczb Hn:

Schemat 0, H = 1
Schemat 1, H = 7
Schamet 2, H = 19

Jak można zauważyć na ilustracjach w n-tym schemacie będzie n sześciokątów i każdy kolejny jest "większy" o sześć wierzchołków od poprzedniego.

Ciąg liczb

Liczby można ustawić w następujący ciąg: 1, 7, 19, 37, 61, 91, 127, 169, 217, 271, 331, 397, ..

Implementacja

Napisz funkcję liczbaSzesciokatna(), która dla podanego argumentu n zwróci liczbę sześciokątną Hn. Przyjmujemy, że H0 = 1 itd. Przetestuj działanie funkcji.

Iteracja

Podstawowa wersja kodu polega na napisaniu funkcji, która będzie obliczać ile ma i-ty sześciokąt i doda jego liczbę wierzchołków do ogólnej sumy. W celu zwiększenia wydajności liczba wierzchołków następnego sześciokąta jest wyliczana na podstawie liczby wierzchołków poprzedniego poprzez dodanie 6. Algorytm ten ma złożoność liniową O(n) i kod wygląda następująco:

  1. int liczbaSzesciokatna(int n) {
  2.   int suma = 1;
  3.   int wierzcholkow = 0;
  4.   for (int i = 1; i < n; i++) {
  5.     wierzcholkow += 6;
  6.     suma += wierzcholkow;
  7.   }
  8.   return suma;
  9. }

(2.) Początkowo suma to 1 (dla pierwszego wyrazu) oraz (3.) liczba wierzchołków w największym sześciokącie to 0. Następnie (4.) W pętli: (5.) wylicz ile wierzchołków ma aktualna figura i (6.) dodaj do sumy. Na koniec (8.) zwróć zsumowaną liczbę wierzchołków.

Wzór

Jednak dla takich przypadków obliczania możliwe jest uzyskanie wzoru. Wtedy algorytm działania nie liniowo O(n), a w czasie stałym O(1). Poniżej zostaje przedstawiona funkcja, która oblicza żądany wyraz prosto ze wzoru.

  1. int liczbaSzesciokatna(int n) {
  2.   return 3 * n*(n - 1) + 1;
  3. }

Testowanie funkcji

W celu przetestowania działania napisanej funkcji można skorzystać z poniższego fragmentu kodu:

  1. int main () {
  2.   int k;
  3.   cout << "Ile pierwszych liczb szesciokatnych wypisac?\n k = ";
  4.   cin >> k;
  5.   for (int i = 1; i <= k; i++)
  6.     cout << liczbaSzesciokatna(i) << " ";
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Zauważmy, że w każdym kolejnym schemacie sześciokątów jest dokładnie o 6n wierzchołków więcej. Oznacza to, że liczbę Sześciokątną można wyliczyć poprzez sumowanie liczb od 1 do n (dla n = 0 suma wynosi 0), pomnożeniu przez 6 i dodaniu jeden. Przykładowo w celu wyliczenia H3 = 6·(1 + 2 + 3) + 1 = 37.

Napisz funkcję liczbaSzesciokatna(), która dla podanego argumentu n i przedstawionego rozumowania zwróci n-tą liczbę sześciokątną.