Strona główna » Algorytmy » Artykuły » Duże silnie
n!
 

Duże silnie

https://mattomatti.com/a65

Wstęp

Silnia, w matematyce oznaczana jako n!, rośnie bardzo szybko już dla niewielkich wartości. Utrudnia to jej wyliczanie w trakcie działania aplikacji, której zmienne mają określone pojemności. Jeśli wyliczona wartość jest większa od zakresu zmiennej wyniki są nieprawidłowe.

Pojemności konkretnych zmiennych można sprawdzić przy pomocy poniższej funkcji. Jej działanie polega na wypisywaniu kolejnych wartości n!. Wykonywanie zostanie przerwane w momencie kiedy następna wartość jest mniejsza od poprzedniej. Nie jest to warunek idealny, ale kod ma dać wyobrażenie o pojemności każdej zmiennej.

  1. int main () {
  2.   unsigned long long int f = 1, lf = 0, i = 2;
  3.   cout << "0! = 1! = " << f << endl;
  4.   while(true) {
  5.     lf = f;
  6.     f *= i;
  7.     if(lf > f)
  8.       break;
  9.     cout << i << "! \t= " << f << endl;
  10.     i++;
  11.   }
  12.   system("pause");
  13.   return 0;
  14. }

W tabelce zebrane zostały niektóre informacje, które pozwalają na szybkie sprawdzenie jaką maksymalnie silnie można zapisać w określonym typie zmiennej:

Typ zmiennejMaksymalna silnia
char5!
int13!
unsigned int13!
long long int20!
unsigned long long int22!

Jak widać w przypadku wyliczania silni należy używać typu unsigned long long int. Niestety nawet tego typu zabieg pozwala na wyliczenie maksymalnie 22! co jest wystarczające tylko dla niektórych zadań. Istnieje jednak sposób, aby uniknąć wyliczania ogromnych liczb. Jeśli istnieje potrzeba wykonania obliczeń można napisać dodatkową strukturę, która pozwoli na przechowywanie n!. Ostateczny wynik będzie wyliczony dopiero po skróceniu wszystkich danych.

Zera na końcu n!

Ze względu na fakt, że silnia bardzo szybko rośnie trudno znaleźć zadań, których polecenie to Wczytaj n i wypisz na ekran n!. Jednym z zadań, które można spotkać związane z silnią polega na wyliczeniu ile zer znajduje się na końcu liczby. Jednym ze sposobów jest wyliczenie silni i sprawdzenie ile liczba ma zer. Jednak problemem jest tu pojemność zmiennych. Nie należy się jednak zniechęcać.

Poniższy wzór pozwala na wyliczenie ile zer na końcu ma n!:

silniazera(n!) =

Przykładowo jeśli n = 100, to:

silniazera(100!) =

Implementacja

Najprostszy kod obliczający wynik zgodnie ze wzorem wygląda tak:

  1. int silniazera(int n){
  2.   int suma = 0;
  3.   int e;
  4.   int five=1;
  5.   do{
  6.     five *= 5;
  7.     e = n / five;
  8.     suma += e;
  9.   } while (e > 0);
  10.   return suma;
  11. }

(1.) Funkcja przyjmuje argument n - określa, której silni wyliczamy ilość zer na końcu. Zwracaną wartością jest ilość zer. Deklarowanie zmiennych: (2.)suma - będzie przechowywać ile jest zer na końcu, (3.) e - zmienna pomocnicza pozwoli na przechowanie wyniku dzielenie oraz (4.) five - pozwoli na szybkie wyliczanie 5i. (5.) Następnie wykonane jest: (6.) wyliczenie następnej potęgi 5. (7.) Wyliczenie wartości i-tego elementu nieskończonej sumy i (8.) dopisania go do suma. (9.) Wszystko jest powtarzane w pętli dopóki e > 0, ponieważ począwszy od pierwszego zerowego elementu reszta elementów też taka będzie.

Optymalizacja wzoru i kodu

Jeśli rozpisać inaczej podany wzór można zauważyć, że powstaje tam ciąg geometryczny o q = 0.2 i początkowym wyrazie a1 = . Jednak zastosowanie wzoru na nieskończony wzór geometryczny może mieć niezamierzony efekt - wyjdzie większa suma niż powinna. Będzie to spowodowane faktem, że w sumie każdy element jest zaokrąglany w dół co nie jest uwzględnione we wzorze. Jednak fakt ten pozwoli napisać szybszy kod:

  1. int silniazera(int n){
  2.   int suma = 0;
  3.   do{
  4.     n /= 5;
  5.     suma += n;
  6.   } while (n > 0);
  7.   return suma;
  8. }

W powyższym kodzie usunięte zostały dodatkowe zmienne e i five. Wystarczy bowiem w każdym kolejnym kroku dzielić aktualne n przez 5, a funkcja jest wykonywana dopóki n > 0. Takie rozwiązanie pozwala na znaczna redukcję potrzebnych operacji arytmetycznych.

Testowanie funkcji

Poniższy kod wykorzystuje wcześniej napisaną funkcją silniazera(), aby określić ile silnia ma na końcu zer:

  1. int main () {
  2.   for(int i = 0; i < 100; i++) {
  3.     cout << "silniazera(" << i << "!)=";
  4.     cout << silniazera(i) << endl;
  5.   }
  6.   system("pause");
  7.   return 0;
  8. }

Zadania

Zadanie 1

Sprawdź ile zer ma na końcu 18446744073709551615!. Wskazówka: W napisanych funkcjach należy odpowiednio dobrać typy danych.