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

Liczby Sześciokątne

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:

C++C#
Python
  1. def liczbaSzesciokatna(n):
  2.   suma = 1
  3.   wierzcholkow = 0
  4.   for i in range(1, n):
  5.     wierzcholkow = wierzcholkow + 6
  6.     suma = suma + wierzcholkow
  7.   return suma

(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 (7.) 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.

C++C#
Python
  1. def liczbaSzesciokatna(n):
  2.   return 3 * n * (n - 1) + 1

Testowanie funkcji

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

C++C#
Python
  1. k = int(input("Ile pierwszych liczb sześciokątnych wypisać?\n k = "))
  2. for i in range(1, k + 1):
  3.   print(liczbaSzesciokatna(i), end=" ")

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ą.