Pierwsza cyfra n!

0

Witam!

Mam następujący problem: chciałbym policzyć PIERWSZĄ cyfrę liczby n! (n od użytkownika) BEZ liczenia silni i brania pierwszej cyfry ... jakoś sprytniej.
Ostatnią łatwo, ale na pierwszą nie mam pomysłu... może ktoś ma ;-) ?

0

mnożysz tylko pierwszą cyfre wyniku.

0

No nie wiem ... np: 5! = 120, 6! = 720, 1*6 !=7 ? :-/

0

Podejrzewam, że trzeba będzie wyznaczyć n! przynajmniej w przybliżeniu.

Tu masz wzór na przybliżenie n!:
http://hyperphysics.phy-astr.gsu.edu/Hbase/Math/stirling.html

xn można wyznaczyć stosując wzór szybkiego potęgowania (xn = x(n\2) x(n\2) dla n parzystego i xn = x(n\2) x^(n\2) * x dla nieparzystego)

0

Może wystarczy zwykłe mnożenie, ale wykonywane na typach zmiennoprzecinkowych. Wartość n! jest wtedy przyblizona.

0

Dzięki za porady, o Stirlingu myślalem, ale podejrzewam że istnieje jakieś sprytne rozwiązanie np. z Teorii Liczb którego nie mogę znaleźć .. tak czy siak dziękuje i spróbuję jakoś to oszacować ;-)

0
argv napisał(a)

Dzięki za porady, o Stirlingu myślalem, ale podejrzewam że istnieje jakieś sprytne rozwiązanie np. z Teorii Liczb którego nie mogę znaleźć .. tak czy siak dziękuje i spróbuję jakoś to oszacować ;-)
Na pewno istnieje, tyle że nikt go tu nie zna. Może spróbuj na forum matematycznym?
Mnożenie pierwszej cyfry to za mało bo trzeba pamiętać o nadmiarach z mnożenia młodszych cyfr. Tą metodą łatwo policzyć ostatnią najmłodszą cyfrę (powyżej 4! zawsze zero :) )

0
MarekR22 napisał(a)

Mnożenie pierwszej cyfry to za mało bo trzeba pamiętać o nadmiarach z mnożenia młodszych cyfr. Tą metodą łatwo policzyć ostatnią najmłodszą cyfrę (powyżej 4! zawsze zero :) )

W trudniejszych (bardziej skomplikowanych) przypadkach, wyznaczenie ostatniej cyfry polega na wykonywaniu działań mod 10. Na przykład, chcąc wyznaczyć ostatnią cyfrę 2^100000, wystarczy przyjąć w pierwszym kroku 2, a potem akumulować (wynik ostatniego kroku * 2) mod 10.

0

Jeśli chcemy policzyć ostatnią cyfrę np 7^989 to robimy to tak:

7^1 mod 10 = 7
7^2 mod 10 = 9
7^3 mod 10 = 3
7^4 mod 10 = 1
7^5 mod 10 = 7

więc widzimy że co 4 mnożenia dostajemy taką samą ostatnią cyfrę. Wobec tego możemy podzielić wykładnik modulo cztery.

989 mod 4 = 1

7989 mod 10 = 7(989 mod 4) mod 10 = 7^1 mod 10 = 7

;)

Tak więc przy wyznaczaniu ostatniej cyfry musimy obczaić co ile mnożen powtarza się nam ostatnia cyfra. Tzn musimy znaleźć n dla którego a = a^n (mod 10). Potem dzielimy modulo wykładnik przez n - 1 i już widać wynik.

0

Człowieku tu nie chodzi o ostatnią, ale o pierwszą cyfrę i nie potęgowania, ale silni (jak już wcześniej pisaliśmy znalezienie ostatniej cyfry dla silni/potęgi jest banalnie proste).

Wygląda na to, że jesteś skazany na metodę "brutal force" czyli coś takiego:

int pierwszaCyfraSilniZ(int n)
{
     register unsigned long long int i;
     register int five;
     i = 1;
     five = n%5+1;

     do {
          i*=n;

          if(--five==0) { // optymalizacja by nie dzielić za często
                five = 5;
                if(i%10==0) 
                     i/=10; // kasuj tylne zera
          }
     } while(--n>0);

     //pierwsza cyfra:
     while(i/10!=0) {
         i/=10;
     }
     return static_cast<int>(i);
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0