Strona główna » Algorytmy » Teoria Liczb » Liczby Wielokątne
 

Liczby Wielokątne

https://mattomatti.com/a0046

Definicja

Liczby Wielokątne to takie liczby, które można przedstawić w postaci foremnych figur geometrycznych. Liczby Wielokątne to uogólnienie na dowolną figurę o n ścianach. Kolejne liczby opisują ile należy dołożyć równomiernie rozłożonych punktów do aktualnej figury, a by powstała kolejna identyczna o większym rozmiarze.

Przykłady

Przykład 1

Najprostszym przykładem liczb Wielokątnych są liczby Trójkątne. W tym szczególne przypadku ciag opisuje ile należy kolejno dołączać punktów, aby powstawały coraz większe trójkąty. Poniżej znajduje się interpretacja graficzna:

Liczby Trójkątne

Początkowo mamy zdegenorowaną figurę w postaci punktu, więc a1 = 1. Następnie dokładamy dwa kolejne punkty, aby utworzyć kolejne, większy trójkąt. Jak można zauważyć powstaje ciąg liczb 1, 2, 3, 4, 5, 6... W tym przypadku wzór na ilość punktów do dołożenia w n-tym ruchu jest następujący an = n.

Przykład 2

Innym przykładem są liczby Kwadratowe. Jest to utożsamienie operacji potęgowanie do kwadratu tj. x2 z figurą geometryczną kwadrat. W tym przypadku powstawanie kolejnych takich liczb jest następujący:

Liczby Kwadratowe

Ponownie na początku jest tylko punkt, ale następnie dokładamu 3, 5, 7, .. punktów, aby uzyskać coraz to większy kwadrat. W tym przypadku an = n2.

Opis matematyczny

Na podstawie podanych przykładów można podać ogólną metodę na wyznaczenie n-tego wyrazu o k bokach. Oznaczmy to poprzez ak, n. Rekurenycjny wzór jest następujący:

ak, 1 = 1
ak, n = ak, n - 1 + (k - 2) dla n > 1

Jednak najszybszą metodą obliczenia wyrazu będzie ak, n = nk / k!

Implementacja

Rekurencja

Poniżej została przedstawiona wersja rekurencyjna programu do obliczania ak, n.

  1. int liczbWielokatna(int n, int k = 3) {
  2.   if (n == 1)
  3.     return 1;
  4.   return liczbWielokatna(n - 1, k) + k - 2;
  5. }

Tego typu implementacja pozwoli na wyliczenia dowolnego wyrazu dla liczby o dowolnym stopniu złożności k. Jednak tego typu metoda nie jest zbyt efektywna w przypadku, gdy trzeba wypisać ciąg liczb Wielokątnych określonego stopnia.

Testowanie funkcji

Napisaną funkcję można przetestować przy pomocy poniższego fragmentu kodu:

  1. int main () {
  2.   int k, n;
  3.   cout << "Podaj stopien k liczby\nk = ";
  4.   cin >> k;
  5.   cout << "Podaj, ktory wyraz wypisac\nn = ";
  6.   cin >> n;
  7.   cout << "a(" << n << ", " << k << ") = ";
  8.   cout << liczbWielokatna(n, k);
  9.   system("pause");
  10.   return 0;
  11. }

Wypisywanie kolejnych wyrazów

Najbardziej efektywnym sposobem wypisania kolejnych liczb Wielokątnych dowolnego stopnia będzie zastosowania iteracji. Zamiast ponownie wyliczać wyraz to będzie on wyliczany na podstawie poprzedniego wiersza. Uprości to potrzebne operacje do minimum.

  1. void wypiszLiczbyWielokatne(int ile, int k = 3) {
  2.   int n = 1;
  3.   int a = 1;
  4.   do {
  5.     cout << "a" << n << " = " << a << endl;
  6.     a += k - 2;
  7.   } while (++n <= ile);
  8. }

Na początku funkcji wypiszLiczbyWielokatne() ustalamy, (2.) który wyraz wypisujemy oraz (3.) jego wartość.

Testowanie funkcji

Napisaną funkcję można przetestować przy pomocy poniższego fragmentu kodu:

  1. int main() {
  2.   int k, ile;
  3.   cout << "Podaj stopien k liczby\nk = ";
  4.   cin >> k;
  5.   cout << "Podaj ile poczatkowych wyrazow wypisac\nn = ";
  6.   cin >> ile;
  7.   wypiszLiczbyWielokatne(ile, k);
  8.   system("pause");
  9.   return 0;
  10. }

Zadania

Zadanie 1

Napisz program, który będzie wypisywać ile liczb począwszy od pewnego indeksu i. Wskazówka: Skorzystaj z funkcji wypiszLiczbyWielokatne() oraz liczbaWielokatna(). Przykładowo, gdy ile = 4 to kolejne liczby wielokątne dla k = 4 począwszy od = 3 to:

  1. 5 7 9 11

Zadanie 2

Napisz program, który będzie sumować wszystkie wyrazy o indeksach z zakresu [a, b] podanych przez użytkownika. Przykładowo dla k = 3 i zakresu [a = 2, b = 4] program ma zwrócić 9 (= 2 + 3 + 4).