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
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);
}
0
argv napisał(a)
... chciałbym policzyć PIERWSZĄ cyfrę liczby n! (n od użytkownika) BEZ liczenia silni i brania pierwszej cyfry ...
A więc Panie Marku Pan też się myli :) A brutforsy też są banalnie proste.
0
napisałem "skazany", poza tym jest tam małe usprawnienie, by zmieścić większy wynik w standardowym typie. Ja po prostu nie widzę by można było zrobić to sprytniej. Wszystko przez to, że mnożenie powoduje pojawianie cyfry "przeniesienia" dodawanej do wyniku mnożenia starszej cyfry (jak "cary bit") i nie można zapominać o tych niezerowych cyfrach bo mają wpływ na pierwszą cyfrę (przykład silnia z 12).
0
No w tym long longu to się co najwyżej 15! zmieści. Google nie daje żadnych informacji na temat, więc zapewne trzeba użyć wzoru Stirlinga. Zapewne coś w stylu:
global double wynik;
wynik = exp((ln(n) - 1) * n) * sqrt(2 * pi * n) * (1 + 1 / (12 * n)
dziel(1 / 10); // dzieli aż do uzyskania liczby jednocyfrowej
dziel(double a) {
if (wynik * a >= 1)
dziel(a * a);
if (wynik * a >= 1)
wynik *= a;
}
0
Styrling nie daje ci gwarancji poprawności wyniku.
Jeśli już stosować Stirlinga to tak, ale trzeba się modlić, aby nie było pechowego przypadku, który w tym kodzie żuci wyjątek:
int najstarszaCyfraSilni(int n)
{
if(n<StalaDobrana) // stała określa miejsce od którego styrling zapewnia dokładność, rzędu 100
return najstarszaCyfraSilniAnalitycznie(n);
double silnia = StirlingSilnia(n);
int pos = log10(silnia);
int trzyNajstarszeCyfry = silnia / pow(10,pos-3);
int najstarszaCyfra = trzyNajstarszeCyfry ;
while(najstarszaCyfra /10!=0)
najstarszaCyfra /=10;
switch(trzyNajstarszeCyfry%100) {
case 00:
case 99:
throw KurdeNieMamPewnosciWyniku(najstarszaCyfra);
default:
return najstarszaCyfra;
}
}
Kod na pewno ma błędy, ale pokazuje filozofie jak można użyć Styrlinga na siłę.
0
Policzyłem przybliżona wartość silni na dwa sposoby: wzór Stirlinga, zwykłe mnożenie ale na typie double.
Stirling daje złą wartość pierwszej cyfry dla n=1,2 oraz 3. Dla n>170 oba sposoby zawodzą, następuje przekroczenie zakresu dla typu double.
0
A dokładnie jaki wzór stosujesz?
Na wiki jest ten uproszczony. Istnieje dokładny wzór Stirlinga na silnie, który ma pewien parametr dostrojenia mający wartość w przedziale [0,1] (dla każdego argumentu dobiera się osobno ten parametr).
Przeanalizowanie tego wzoru mogłoby być kluczem do znalezienia dobrego rozwiązania.
Niestety nie mam ze sobą notatek ze studiów, a google wypluwa wyłącznie ten prostszy wzór
0
function pierwsza_cyfra(n:integer):char;
function pt(w:real;n:integer):real;
begin
if n=1 then
begin
result:=w;
exit;
end;
result:=sqr(pt(w,n div 2));
if (n mod 2=1) then result:=result*w;
while result>10 do result:=result/10;
end;
begin
result:=floattostr(sqrt(2*pi*n)*pt(n/exp(1),n)*exp(1/12/n))[1];
end;
0
Korzystałem z wzoru przybliżonego
"dokładny" wzór jest taki
, gdzie
Wykorzystałem też wbudowane w Javę i Pythona) "nieskończone" typy całkowite, by utworzyć zbiory zawierające pierwsze cyfry silni. Zdecydowanie najbardziej czasochłonną operacją jest konwersja obliczanych silni na stringi. Utworzenie zbioru zawierającego 6 tys. początkowych pierwszych cyfr trwało ok 5 minut w Javie, i około 5,5 minuty w Pythonie.
0
bogdans napisał(a)
No to robisz tak:
Gdzie log z oznacza logarytm dziesiętny. Wyciągasz z tego cześć ułamkową (trzymasz dwie wersja dla theta=0 i theta=1). Podnosisz 10 do potęgi tego ułamka i sprawdzasz czy niezależnie od theta otrzymasz ten sam wynik (po zaokrągleniu w dół). Jeśli masz ten sam wynik to jest Ok, jeśli nie no to trudno (niby to samo co poprzednio, ale będziesz mógł policzyć dla znacznie większych wartości).
Pamiętaj, też jak się porównuje liczby zmiennoprzecinkowe!
@RFabianski potrafisz wyjaśnić czemu niby to ma działać, względnie podać skąd to masz?
0
@RFabianski potrafisz wyjaśnić czemu niby to ma działać, względnie podać skąd to masz?
Taka mniejwięcej implementacja rozwiązania problemu używająca wzoru stirlinga. Co ciakawe pierwsza cyfra jest ok dla wszystkich n którewprowadzimy (choć wiemy że wzór jest mało dokładny dla małych n). W zasadzie pisałem to w pośpiechu i dlatego też zrobiłem to tak niedożecznie głupio, bo przeciez mozna obliczyć wpierw ln n! i dopiero z tego wyprowadzic pierwsza cyfre n!.
0
Coś strasznie namieszałeś niby wygląd to jak wzór Stirlinga, ale co to jest to: n div 2 albo if (n mod 2=1) then result:=result*w;. W tym momencie drapie się w głowę i po prostu nie wiem o co chodzi.
0
Część główna funkci to po prosu przedstawinie wzoru stirlinga. Funkcja pt zwraca w^n podzielone przez 10 tyle razy aby wynik był < 10. Kiedy z funkcji pt wyrzucisz tę linię z while to jest to standardowa funkcja służąca potęgowaniu. W każym razie funkcja powinna wygladać tak:
function pierwsza_cyfra(n:integer):integer;
var x:real;
begin
x:=n*ln(n)-n+ln(n*pi*2)/2+1/(12*n);
result:=trunc(exp(x-ln(10)*trunc(x/ln(10))));
end;
0
http://www.research.att.com/~njas/sequences/A008905
Jest podany wzór w Mathematice (brutalny). Może nie ma innego pewnego sposobu.
0
Korzystając z powyższego linka napisałem testy dla kodu poniżej. Działa bez zarzutu i szybko (przynajmniej do wartości 98 włącznie):
#include <math.h>
int oldestFractionalDigitAnalitical(int n) {
register unsigned long long int i;
register int five;
i = 1;
five = n%5+1;
while(n>0) {
i*=n--;
if(--five==0) { // optymalizacja by nie dzielić za często
five = 5;
if(i%10==0)
i/=10; // kasuj tylne zera
}
};
//pierwsza cyfra:
while(i>=10) {
i/=10;
}
return static_cast<int>(i);
}
const long double HalfLogTwoPi = 0.3990899341790575247825035915077;
const long double Log10_e = 0.43429448190325182765112891891661;
int oldestFractionalDigit(int n) {
if(n<9) // dla mniejszej wartości nie dział porwanie, więc to jest rozsądna granica
return oldestFractionalDigitAnalitical(n);
long double result = HalfLogTwoPi - n * Log10_e + (0.5+n)*log10((long double)n);
long double doubt;
result = modf(result, &doubt); // część ułamkowa
doubt = Log10_e/(12*n);
int lower,upper;
lower = pow(10,result);
upper = pow(10,result+doubt);
if(lower!=upper)
return -lower*10 - upper - 1000; // brak pewności co do wyniku! zwracaj dziwną wartość.
return lower;
}
0
//mnożenie
double s=1.0d;
String s2="";
for(int i=1;i<=n;i++)
{
s=s*i;
s2=(""+s).substring(0,1);
}
//wzór Stirlinga
for(int i=1;i<=n;i++)
{
s=Math.exp((Math.log(i) - 1) * i) * Math.sqrt(2 * Math.PI * i) * Math.exp(1.0/(12 * i));
s2=(""+s).substring(0,1);
}
Przy wyznaczaniu pierwszej cyfry konwertuję na String i wycinam pierwszą cyfrę (kolejne dzielenie przez 10 może chyba powodować błąd). Czas wykonania:
dla n=170 (ostatnie n dla którego wynik jest poprawny, potem następuje przekroczenie zakresu) około 2 ms., mnożenie jest odrobinę szybsze
dla n=1000000 około 300 milisekund
Parominutowe czasy konwersji z typu numerycznego na String występowały gdy liczyłem silnię dokładnie na "nieskończonych" typach całkowitych i otrzymywane liczby miały kilkadziesiąt tysięcy cyfr