Wątek zablokowany 2015-09-27 19:01 przez msm .
@tłusty łysy byk
To rozwiązanie dalej jest złe, a przynajmniej klasę gorsze od tego przedstawionego wcześniej (tak, dobre rozwiązanie było podane wcześniej). Będziesz miał overflow na l oraz m dużo, dużo wcześniej (i SPOJ to wyłapie), bo liczysz silnie a dopiero później dzielisz. Wszystkie Twoje rozwiązania są dokładnie rozwiązaniami które SPOJ odsiewa - może spróbuj najpierw sam zaliczyć to zadanie na SPOJu a później nazywać innych "głupkami" i "amatorami"?
msm napisał(a):
@tłusty łysy byk
To rozwiązanie dalej jest złe, a przynajmniej klasę gorsze od tego przedstawionego wcześniej (tak, dobre rozwiązanie było podane wcześniej). Będziesz miał overflow na l oraz m dużo, dużo wcześniej (i SPOJ to wyłapie), bo liczysz silnie a dopiero później dzielisz. Wszystkie Twoje rozwiązania są dokładnie rozwiązaniami które SPOJ odsiewa - może spróbuj najpierw sam zaliczyć to zadanie na SPOJu a później nazywać innych "głupkami" i "amatorami"?
Sini to nie liczy, no ale na int zasięg byłby faktycznie marny...
skrajny przypadek to k = n/2, i wtedy obliczamy:
(2k)!/k!^2
co po tym skróceniu dałoby chyba:
l = (k+1)(k+2)...n
m = 23k... *k;
...
optymalna metoda byłaby, tak z marszu, prawdopodobnie taka:
ln (n po k) = ln [n!/k!(n-k)!] = ln(n!) - ln(k!) - ln(n-k)! = ....
co obliczamy dość łatwo na double... i ze stirlinga, oczywista, a nie na piechtę. :)
znaczy wedle wzoru:
ln(N!) = 0.5ln(2Pi) + (N+0.5)lnN - N + 1/12N - 1/360N3 + 1/1260N5 - 1/1680*N^7 ...
@tłusty łysy byk: zarejestruj się na SPOJ i zalicz to zadanie swoją metodą i daj linka udowadniającego, że zaliczyłeś zadanie.
Autor pytania zaliczył zadanie na SPOJ korzystając z naszych rad, a jak puszczał twój kod to nie był w stanie zaliczyć zadania.
Masz pojęcie czym jest wzór Stirlinga i kiedy można go stosować? Zdajesz sobie z czegoś takiego jak precyzja liczb zmiennoprzecinkowych? Twoje mądrości wykazują, że nie za bardzo.
MarekR22 napisał(a):
@tłusty łysy byk: zarejestruj się na SPOJ i zalicz to zadanie swoją metodą i daj linka udowadniającego, że zaliczyłeś zadanie.
Autor pytania zaliczył zadanie na SPOJ korzystając z naszych rad, a jak puszczał twój kod to nie był w stanie zaliczyć zadania.
Masz pojęcie czym jest wzór Stirlinga i kiedy można go stosować? Zdajesz sobie z czegoś takiego jak precyzja liczb zmiennoprzecinkowych? Twoje mądrości wykazują, że nie za bardzo.
Precyzja wzorów tego typu jest wręcz... zbyt dobra! :)
Sytuacja podobna do wzorów na Fibonacciego, gdzie wystarczy tak obliczać:
F(n) = [Phi^n/sqrt5]; gdzie: [x] = round(x);
np.: F12 = 144, i Phi^2/sqrt5 = 144.00138...
zatem mamy od razu, np. : F100 = 354224848179261915075, zamiast sumować te setki numerków.
@tłusty łysy byk brawo, potrafisz skopiować wzór z wikipedii, szkoda że bez poprawnych oznaczeń. Fibonacci z tym pierwiastkiem z 5 to jest zupełnie inna bajka niż wzór Stirlinga. To jest po prostu analityczne (więc dokładne!) rozwiązanie jednorodnego równania rekurencyjnego dla liczb Fibonacciego (wyprowadzałem je chyba nawet kiedyś na forum).
Shalom napisał(a):
@tłusty łysy byk brawo, potrafisz skopiować wzór z wikipedii, szkoda że bez poprawnych oznaczeń. Fibonacci z tym pierwiastkiem z 5 to jest zupełnie inna bajka niż wzór Stirlinga. To jest po prostu analityczne (więc dokładne!) rozwiązanie jednorodnego równania rekurencyjnego dla liczb Fibonacciego (wyprowadzałem je chyba nawet kiedyś na forum).
dokładny wzór na Fiby jest nieco inny... a jego wyprowadzenie to pikuś.
Phi^n / sqrt5;
daje przybliżenie z błędem rzędu phi^n,
gdzie: phi = 1/Phi, co jest równe Phi -1, oczywista.
Zatem dla dużych n błąd znika wykładniczo...
20: Phi^20 / sqrt5 = 6765.00002956
21: Phi^21 / sqrt5 = 10945.99998
błąd rzędu 0.00001;
F50: 12586269025.000000000015890332521
F75: 4721424167835364.0000000000000002
błąd znika szybko do zera...
No to może inaczej. 30 po 15 = 565 722 720
http://www.wolframalpha.com/input/?i=combination%2832%2C+15%29
Twój algorytm oblicza na double: 32!/15! a to w zapisie binarnym http://www.wolframalpha.com/input/?i=32!%2F15!+bin
101010100111000010111011010110001011101010001101010010000100000000000000000000
78 bitów po zignorowaniu końcowych zer zostaje 58 bitow znaczących.
Double ma 53 bity znaczące (52 są zapamiętywane), czyli tracisz w tym przypadku 5 bitów, które mogą mieć wpływ na wynik końcowy.
Używając Wzór Stirlinga liczysz pełna silnię, więc sytuacja jest jeszcze gorsza.
Zamiast z nami wojować zalicz zadanie.
Zapewne twój kod da się doprowadzić do sytuacji, w której będzie zwracać prawidłowe wyniki, ale po co się z tym męczyć, skoro na liczbach całkowitych działa i to na pewno dużo szybciej.
MarekR22 napisał(a):
No to może inaczej. 30 po 15 = 565 722 720
http://www.wolframalpha.com/input/?i=combination%2832%2C+15%29
Twój algorytm oblicza na double: 32!/15! a to w zapisie binarnym http://www.wolframalpha.com/input/?i=32!%2F15!+bin
101010100111000010111011010110001011101010001101010010000100000000000000000000
78 bitów po zignorowaniu końcowych zer zostaje 58 bitow znaczących.
Double ma 53 bity znaczące (52 są zapamiętywane), czyli tracisz w tym przypadku 5 bitów, które mogą mieć wpływ na wynik końcowy.
Używając Wzór Stirlinga liczysz pełna silnię, więc sytuacja jest jeszcze gorsza.Zamiast z nami wojować zalicz zadanie.
Zapewne twój kod da się doprowadzić do sytuacji, w której będzie zwracać prawidłowe wyniki, ale po co się z tym męczyć, skoro na liczbach całkowitych działa i to na pewno dużo szybciej.
Co takiego?
dzielenie na int trwa tyle samo co na floatach... albo i gorzej.
Natomiast dodawanie i mnożenie trwa: 1-2 cykli procesora, czyli tyle co nic.
Dlatego też w moim kodzie jest tylko jedno dzielenie, zamiast aż n/4 (średnio).
Zatem szybkość mojego kodu jest średnio n/4 razy większa - przynajmniej!
A w wersji z double zakres też jest tu szerszy od int32, a i pewnie nawet od int64.
100 po 50 = 100891344545564193334812497256
int64 tego nie zmieści - choćbyś się zesrał, no a double be problemu!
Zatem komuś się tu coś nieźle musiało pojebać...
ty nadal rozumiesz, że największy problemem jest to, że wpadłeś na forum i zacząłeś swoją karierę od obrażania ludzi.
Twoje rozwiązanie z liczbami doble zadziała, ale dopiero po rozwiązaniu problemów z precyzją liczb zmiennoprzecinkowych. A pomysł ze wzorem Stirlinga to kompletny niewypał, dowód testami (może będziesz umiał je uruchomić):
#include <QString>
#include <QtTest>
#include <cmath>
uint NewtonInts(uint n, uint k)
{
if (2*k<n) {
k = n - k;
}
register quint64 r = 1;
for (uint i=1; i<=k; ++i, --n)
r = r * n / i;
return r;
}
uint NewtonDoubles(uint n, uint k)
{
if (2*k<n) {
k = n - k;
}
double a = 1, b = 1;
for (uint i=n; i>n-k; --i) {
a *= i;
}
for (uint i=2; i<=k; ++i) {
b *= i;
}
return a/b + 0.5;
}
double Stirling(double n)
{
return sqrt(2*M_PI*n)*std::pow(n / M_E, n);
}
uint NewtonStirling(uint n, uint k)
{
return Stirling(n)/(Stirling(k)*Stirling(n-k)) + 0.5;
}
class NewtonRozneMetodyTest : public QObject
{
Q_OBJECT
public:
NewtonRozneMetodyTest();
private Q_SLOTS:
void testNewtonInts();
void testNewtonDoubles();
void testNewtonStirling();
};
NewtonRozneMetodyTest::NewtonRozneMetodyTest()
{
}
void NewtonRozneMetodyTest::testNewtonInts()
{
uint a,b,c,d;
QBENCHMARK {
a = NewtonInts(32, 15);
b = NewtonInts(33, 15);
c = NewtonInts(34, 14);
d = NewtonInts(35, 13);
}
QCOMPARE(a, 565722720u);
QCOMPARE(b, 1037158320u);
QCOMPARE(c, 1391975640u);
QCOMPARE(d, 1476337800u);
}
void NewtonRozneMetodyTest::testNewtonDoubles()
{
uint a,b,c,d;
QBENCHMARK {
a = NewtonDoubles(32, 15);
b = NewtonDoubles(33, 15);
c = NewtonDoubles(34, 14);
d = NewtonDoubles(35, 13);
}
QCOMPARE(a, 565722720u);
QCOMPARE(b, 1037158320u);
QCOMPARE(c, 1391975640u);
QCOMPARE(d, 1476337800u);
}
void NewtonRozneMetodyTest::testNewtonStirling()
{
uint a,b,c,d;
QBENCHMARK {
a = NewtonStirling(32, 15);
b = NewtonStirling(33, 15);
c = NewtonStirling(34, 14);
d = NewtonStirling(35, 13);
}
QCOMPARE(a, 565722720u);
QCOMPARE(b, 1037158320u);
QCOMPARE(c, 1391975640u);
QCOMPARE(d, 1476337800u);
}
#include "tst_newtonroznemetodytest.moc"
Wynik na mobilnym procku 1,6 GHz Intel Core i5
********* Start testing of NewtonRozneMetodyTest *********
Config: Using QtTest library 5.5.0, Qt 5.5.0 (x86_64-little_endian-lp64 shared (dynamic) release build; by Clang 6.0 (clang-600.0.56) (Apple))
PASS : NewtonRozneMetodyTest::initTestCase()
PASS : NewtonRozneMetodyTest::testNewtonInts()
RESULT : NewtonRozneMetodyTest::testNewtonInts():
0.0000084 msecs per iteration (total: 71, iterations: 8388608)
PASS : NewtonRozneMetodyTest::testNewtonDoubles()
RESULT : NewtonRozneMetodyTest::testNewtonDoubles():
0.0000078 msecs per iteration (total: 66, iterations: 8388608)
FAIL! : NewtonRozneMetodyTest::testNewtonStirling() Compared values are not the same
Actual (a) : 570182287
Expected (565722720u): 565722720
Loc: [../NewtonRozneMetody/tst_newtonroznemetodytest.cpp(99)]
PASS : NewtonRozneMetodyTest::cleanupTestCase()
Totals: 4 passed, 1 failed, 0 skipped, 0 blacklisted
********* Finished testing of NewtonRozneMetodyTest *********
To dowodzi, że wersja zmiennoprzecinkowa jest nieznacznie szybsza niż wersja na liczbach całkowitych (przy mniejszych wartościach jest na odwrót).
A pomysł ze wzorem Stirlinga jest kretyński (wzór Stirlinga jest efektywny dla dużych wartości, 40 to dużo za mało), na dodatek wolniejszy niż wersja int.
Przeiterowałem wszystkie dane wejściowe dla n od 1 do 50 i wszystkie możliwe k, wyniki są te same (nawet te same błędy) dla wersji z uint i double.
Dla twojej informacji: jest jeszcze szybsze cwane rozwiązanie, które bije na głowę wszystkie powyższe.
A ja będe złym trollem i wrzuce odpowiedź na spoja.
#include <iostream>
using namespace std;
double factorial(int x){
long long result = 1;
for (int i=1; i<=x; i++){
result=result*i;
}
return result;
}
double binomial(int n, int k){
if (k == 0) return 1;
if (n == k) return 1;
if (n == 0) return 0;
double up = 1;
double down =0;
if ( k > n/2) {
for (int i=k+1; i <= n; i++){
up = up * i;
}
down = factorial(n - k);
}
else {
for (int i=n-k+1; i <= n; i++){
up = up * i;
}
down = factorial(k);
}
return up/down;
}
int main() {
int tests;
int k;
int n;
cin >> tests;
for (int i=0; i< tests; i++){
cin >> n;
cin >> k;
cout << (int)binomial(n,k) <<endl;
}
return 0;
}
MarekR22 napisał(a):
ty nadal rozumiesz, że największy problemem jest to, że wpadłeś na forum i zacząłeś swoją karierę od obrażania ludzi.
tłusty łysy byk napisał(a):
Użyj poprawnych wzorów, głupku.
tłusty łysy byk napisał(a):
Sam jesteś przybliżeniem...gibbona. :)
Jak tak dalej pójdzie, to będzie się musiało skończyć banem na IP.