833. Dwumiany [BINOMS]

Zastanawia mnie fakt, że na ideone powstaje błąd kompilacji, ale w moim kompilatorze taki błąd nie występuje(...)

Jak się robi zadania o 3:00 w nocy to czasem zapomina się o takich rzeczach jak liczba testów w pierwszej linii wejścia

Runtaim error, to jak sama nazwa wskazuje , jest błędem wykonania a nie kompilacji - tak na trzeźwo, po przespaniu się ;=)

PS
A pytanie raczej zawsze należy doklejać do istniejącego wątku, bo lepiej aby wszystko na temat jednego zadania było w jednym miejscu - w ten sposub następni pytający będą mieli ułatwione szukanie?

Nie wiem czy przy tym algo na newtona wyniki cząstkowe nie wychodzą ci za duże.

Pięknie i może, ale czy poprawnie? Policzyłeś ręcznie i sprawdziłeś
Zobacz jak to pięknie robi: http://ideone.com/GYbvnO255
Ustawienie cout << setprecision(1000); spowoduje Ci tylko wyświetlenie odpowiedniej ilości cyfer, ale wcale nie znaczy, że będą to dokładne wartości. Przy long doble, gdzieś tak 20 znaczących [o ile dobrze pamiętam[ a reszta to śmieci, a dodatkowo, przy niektórych kombinacjach danych i tak sypie wartościami po przecinku. Autor zadania zapewnia, że wynik nie będzie większy od 1 000 000 000 [typ int wystarcz] ale po drodze pewnie pojawiają się w twoim algorytmie, przekłamania [błędy zaokrągleń zmiennoprzecinkowych].
A duże wartości możesz zobaczyć i sprawdzić np tu: http://www.wolframalpha.com/input/?i=binomial+%28+1000%2C+12%2998 wpisując w pomarańczową ramkę dowolne wartości [ale pewnie bez przesady], taki sobie po[d]ręczny kalkulator.
Dwumian to liczba całkowita, a licząc na typie double, czy long double uzyskasz jakiś wynik przybliżony, dla małych wartości z bardzo małym [pomijalnym] błędem dla ogromnych z dużym. Mam na myśli ilość cyfr znaczących.

PS
Na pocieszenie, pewien bloger, autor kilku ciekawych kursów programowania, prowadzący interesujący i wartościowy blog ale nie pozbawiony błędów. Międy innymi przedstawia swój program do liczenia wielkiech liczb fibonacciego i niestety też z tym samym, co twój, błędem.

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);
}

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.

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

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

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

In

1
25 15

Poprawny out

3268760

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.

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ć.