833. Dwumiany [BINOMS]

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.

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

1
25 25

Poprawny out

1

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!

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

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.

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

#include<iostream>

using namespace std;


unsigned long long Newton(int n, int k)      
{
	double Wynik = 1;      

	for (unsigned int i = 1; i <= k; i++)  
	{
		Wynik = Wynik * (n - i + 1) / i;    
	}

	return (unsigned long long) Wynik;    
}

int main()


{
	int ile;

	cin >> ile;

	int *tab1 = new int[ile];
	int *tab2 = new int[ile];
	for (int i = 0; i < ile; i++)
	{
		cin >> tab1[i] >> tab2[i];
	}
	for (int i = 1; i <= ile; i++)
	{

		if (tab2[i-1] == 0 || tab1[i-1] == tab2[i-1]) cout << "1"<<endl;
		else
			cout << Newton(tab1[i-1], tab2[i-1]) << endl;
	}
	


	system("pause");
	return 0;
}

Co jest nie tak z tym kodem? U mnie jak testuje to działa, a SPOJ pokazuje ze bledna odpowiedź

Double są za mało dokładne i niepotrzebne.
Porysuj, pobaw się, samodzielnie, na papierze, trójkątem paskala i wyciągnij wnioski. Na pewno było już o tym w tym lub innym wątku, poświęconemu temu zadaniu.

PS
Wygląda, że tablice i indeksy opanowałeś do perfekcji, ale druga pętla jest “dziwna”
No i wklejanie kodu.

PS 2
Chodziło mi raczej o trójkąt newtona, ale jak zwał tak zwał, pobaw się.

Cześć,

mam klasyczny problem “u mnie działa, a mi nie zaliczają”…

Ogólnie miałem taki pomysł, żeby policzyć dwumian Newtona lecz odpowiednio
skrócony, a by w założeniach komputer miał mniej do liczenia. Przeanalizujcie proszę
ten program i śmiało wytknijcie błędy.

problem klasyczny - więc zamiast pisać, może warto przeczytać wątek ?

powyżej znajdziesz dyskusję na temat poprawnego algorytmu, oraz przykładowe testy dla których twój program będzie dawał błędne wyniki

Dzień dobry,
mam prośbę o pomoc w zadaniu. Wykonałem korzystając z trójkąta Pascala jednak sędzia wyświetla informację “Przekroczono limit czasu” Nie mam już pomysłu jak przyspieszyć wykonywanie programu. Do tej pory próbowałem to zadanie rozwiązać używając vector’a, pojedynczej tablicy, a teraz tablicy dwuwymiarowej z tym samym jednak skutkiem.

Kod przetestowałem na ideone (poniżej):

a czego byś się spodziewał ?

dla maksymalnych danych będzie to:

10000 testów * (500000 dodawań + 1500000 dostępów do elementów tablicy)

czyli 5 mld dodawań i 15 mld dostępu do pamięci - to się zrobić szybko nie da

Racja, dzięki za sugestię. Zmniejszyłem ilość działań i zadanie przeszło. Dzięki za pomoc