833. Dwumiany [BINOMS]

vojtass · Jan '16

Dzięki wielkie za odpowiedzi!

Tak sądziłem, że ten typ double coś kręci, już mi ktoś kiedyś napomknął o tym przybliżaniu gdzieś tam za przecinkiem. Od dłuższego czasu próbuję więc ominąć duże liczby, staram się współpracować z mniejszymi, i do tej pory wykombinowałem coś takiego: http://ideone.com/LTJL6b82 (tak, w kodzie jest funkcja newton_triangle, pomyliłem się, ten trójkąt w istocie nazywa się trójkątem Pascala oczywiście)

Program opiera się na zależności trójkąta Pascala, gdzie każdy wyraz poza skrajnymi powstaje przez dodanie do siebie dwóch bezpośrednio nad nim, oraz z zależności, że dla k > n/2 --> k = n - k; liczy na samych intach, więc przybliżenie wyeliminowane, rozmiar kodu i programu też zmniejszony, ale doszedł mi teraz problem z czasem wykonania programu (za duży)... macie jakieś wskazówki może, jak jeszcze inaczej to wykonać? Jak tu ukrócić ten czas?

narbej · Jan '16

Funkcje rekurencyjne mają to do siebie, że są łatwiejsze do napisania, ale często taki algorytm jest dużo wolniejszy od iteracjyjnego. Tutaj dochodzi do wielokrotnego liczenia tych samych wartości. Np popatrz:
(20, 10) = (19, 9) + (19, 10)
(19 , 9) = (18, 8) + (18, 9); (19, 10) = (18, 9) + (18, 10)
(18, 8) = (17, 7) + (17, 8); (18, 9) = (17, 8) + (17, 9); drugi raz (18, 9) = (17, 8) + (17, 9); (18, 10) = (17, 9) + (17, 10)
.........itd
Czy pomysł z trójkątem jest w takim razie zły? Nie, pod warunkiem, że wcześniej obliczysz wartości i zapiszesz w tablicy dwuwymiarowej [preprocesing]. Potem już od razy będziesz mógł odczytywać wartości (n, k) bezpośrednio z tablicy. Jakie wymiary tej tablicy? Z treści zadania wynika, że wierszy musi być n <= 1000, ale czy kolumn też aż tyle?

Druga metoda, to liczenie dwumianu iteracyjnie i aby nie przekroczyć zakresu na zmianę odpowiednio mnożyć i dzielić. Odpowiednio, bo musimy dzielić całkowicie [bez reszty]. Dzięki temu uda się "utrzymać" w zakresie long long - przy założeniach z zadania. [Algorytm np na wikipedi]

PS
Nazwy zmiennych zwyczajowo coś znaczą. Np i, j - zmienne pętli, indeksy tablic. x, y, z --> układ kartezjański i wartości na osiach. itd Dlatego twoją funkcję jeżeli już, to napisałbym raczej jakoś tak, chociaż i tak to nie zmienia faktu - nadal jest tle.
i

int PascalTriangle (int n, int k){
    if (n == k || k == 0) return 1;
    if(k > (n >> 1)) k = n - k;
    if ( k == 1) return n;
        return PascalTriangle (n-1, k-1) +  PascalTriangle

(n-1, k);
}

vojtass · Jan '16

Dzięki znów za odpowiedź, to mi dużo da, zaraz siadam do pracy i pokombinuje w tym kierunku!

A co do tych zmiennych, gdzieś słyszałem, że bezpieczniej jest inaczej nazwać zmienne, które wykorzystuje funkcja na potrzeby własne, nie do końca jestem w stanie teraz podać sensowne powody tego założenia, więc nie będę się kłócić, ale podejrzewam, że wiesz na ten temat co nieco, mógłbyś jakoś się odnieść do tego? Z góry dziękuje! ^^

vojtass · Jan '16

Skorzystałem z liczenia iteracyjnego, program po raz kolejny wykonuje obliczenia dokładnie, szybko, tym razem jednak mam błędną odpowiedź. Poważnie, nie wiem czy ja nie jestem czasem za głupi na to zadanie nie mogę się doszukać błędu.

Wstawiam kod: http://ideone.com/jJCNaF117

narbej · Jan '16

Sorry, że cytuję sam siebie, ale proszę sprawdź, czy rzeczywiście tak napisałem No może wcześniej nie pogrubiłem i nie wystarczająco uwypukliłem, więc się tym nie przejmuj. I chodzi tylko o jedną zmienną tego typu, w, reszta jest ok. Po prostu, w tym algorytmie, mimo naprzemiennego mnożenia i dzielenia jednak czasami wychylamy się troszkę ponad inta, dla danych takich jak w zadaniu.

PS
Co do nazewnictwa. Funkcja, lokalnie używa swoich zmiennych lokalnych, więc może chyba
sobie je lokalnie nazywać jak chce? Po prostu nie wierz [albo wież] bezgranicznie we wszystko co gdzieś usłyszysz czy przeczytasz, póki sam osobiście tego nie sprawdzisz. Więc mi oczywiście też nie

vojtass · Jan '16

Może nie jest tak, że bezgranicznie wierzę, po prostu ufam lepszym od siebie, skoro są w stanie wyjaśnić mi multum zagadnień, czemu w tym mają się mylić prawda jest taka, że i tak większość rzeczy człowiek i tak uczy się na błędach, jak ja w tej chwili ^^ z drugiej strony jednak, czemu w takim razie kompilator nie wyrzuca mi błędu u mnie na komputerze, ale sędzia doskonale wie, że w którejś tam iteracji zmienna wypada poza zakres? Myślałem, że dla niego liczy się tylko poprawność wyjścia

PS. Kod przeszedł (dzięki long long) bez problemu, dzięki wielkie!

PSS. Dobra, mój błąd, po prostu nie dobrałem takiego wejścia żeby pojawił się problem który opisałeś - dla niektórych dwumianów faktycznie wynik jest błędny mimo tego, że prawidłowy końcowy wynik zawiera się w przedziale podanym przez autora.

sig · Jan '16

Podejrzewam że chodzi o to, że zmienna lokalna "przykryje" globalną, i przy 2 zmiennych o tej samej nazwie (lokalnej i globalnej) nie będziesz miał z tej funkcji dostępu do globalnej. Będziesz też musiał zastanawiać się czy w danym miejscu ta zmienna jest globalna czy też lokalna. Generalnie zalecam nazywanie zmiennych zgodnie z tym co w nich przechowujesz, wtedy nie powinno być tego typu problemów, a kompilator i tak zamieni je na adresy pamięci więc długość nazw nie ma najmniejszego wpływu na działanie programu.

eriq2207 · Mar '16

Witam.

Przejrzałem wszystkie tematy związane z zadaniem, próbowałem różnych zestawów danych jednak mój program cały czas wyrzuca "błąd wykonania".
Jeżeli ktoś miałby czas spojrzeć na kod i stwierdzić co w nim jest nie tak to byłbym wdzięczny.

Link do kodu: https://ideone.com/TmxyVB74

Z góry dzięki

karol1ch · Sep '16

Witam. Ponownie muszę zwrócić się do Was z prośbą o pomoc choć tym razem nie do końca dotyczącą kodu.
Sędzia wyrzuca mi błąd SIGFPE czyli coś złego dzieje się z działaniami, a ja nie mam pojęcia co i będę wdzięczny za pomoc.
Na wszelki wypadek dołączam też mój kod
ideone28

vojtass · Sep '16

Problem wynika ze sposobu liczenia. Zobacz - sposób jest dobry, ale weź pod uwagę, że gdy do funkcji silnia() jako argument wstawisz 1000 to nie wiem czy long long będzie w stanie uciągnąć taką liczbę. dodatkowo posługując się tak ogromnymi liczbami, wykonując potem operacje dzielenia narażasz się na błąd przybliżenia wynikający ze sposobu zapisu liczb w programowaniu

prynio · Feb '17

Stworzyłem do tego zadania bardzo prosty kod, z czego byłem bardzo dumny. W code::blocks działa niezawodnie, sprawdzałem dla wielu przykładów ręcznie. Ale sędzia tego nie uznaje. Jakieś uwagi co poszło nie tak?

Kod:
https://ideone.com/pfwLJe71

etheral6661 · Feb '17

In

1
25 15

Poprawny out

3268760

prynio · Feb '17

Ale w zadaniu jest założenie "Dla liczb całkowitych n i k, 0 <= k <= n <= 1000", a w Twoim drugim przykładzie k>n i jeśli się nie mylę, to nie da się wyznaczyć takiego dwumianu.

krystian01 · Feb '17

W tym zadaniu kombinatoryka się kłania Poczytaj o symbolu Newtona(kombinacje bez powtórzen). Sam wzór niestety nie wystarczy. Będziesz musiał coś wykminić.

etheral6661 · Feb '17

@prynio
Racja, mój błąd. Zatem:
In

1
25 25

Poprawny out

1

prynio · Feb '17

Dla 25 25 działał dobrze, ale Twój poprzedni przykład pokazał słabość kodu. Nie wiem czemu, ale dla n=0 wykonywał pętle for (int j=n; j>(n-k); j--) x*=j; chociaż tak na logikę powinien zerwać ją przed pierwszym wykonaniem. W każdym razie dodałem "ręcznie" wyjątek w postaci if (n==0)cout<<x<<endl; i już mi zaliczyło.

Także bardzo dziękuję za pomoc!

narbej · Feb '17

No, nono, w takim razie wielki szacunek I za dodanie wyjątku i za zrobienie tego ręcznie, jestem pełen podziwu i uznania

A na ideone.com, można i należy wkleić nie tylko kod programu, ale i testy, abyś i Ty mógł sobie potestować i aby inni też widzieli, że testowałeś: https://ideone.com/9DN2Ui37 <-- tu niestety twoja stara wersja kodu, bez wstawionego ręcznie wyjątku.

PS
Tak na marginesie, dwumian (1000 3) == dwumian (1000 997), o czym przeczytałbyś i w opisie dwumian'a i w tym wątku, gdybyś czytał.

prynio · Feb '17

Dzięki, nie zauważyłem że można tam dodawać testy. Na pewno skorzystam

To akurat wiem, ale nie bardzo rozumiem jak się ma do tematu. Mogłem zamienić (0 x) na (x x), jeśli to masz na myśli, ale w sumie wyszłoby na to samo co dodanie automatycznego wyniku "1" dla każdego n=0.

narbej · Feb '17

A no taki, że np dla 1000 2 podajesz prawidłowy wynik, ale dla 1000 998 już nie, a oba testy spełniają warunki zadania.
Także np taki test:
40 10 ==> http://www.wolframalpha.com/input/?i=binomial(40,10)56

etheral6661 · Feb '17

Wersja, którą wkleiłeś na ideone wypisywała 0, czyli raczej źle.

Swoją drogą przykład "0 1" był niepoprawny, natomiast "25 15" już tak. Wybaczcie małe zamieszanie.

share a link to this topic