Dwumian Newtona SPOJ

0
 #include <iostream>

using namespace std;

long long Binomial(int n, int k)
{
	double wynik = 1;
	for (int i = 1; i <= k; i++)
		wynik = wynik * (n-i+1)/i;
	return wynik;
}

int main()
{
	int t; cin >> t;
	for (int i = 1; i <= t;i++)
	{
		int n, k; cin >> n >> k;
		cout << Binomial(n, k) << endl;
	}
	
	return 0;
}

http://pl.spoj.com/problems/BINOMS/

Napisałem tu prosty program liczący dwumian Newtona. Sprawdzałem wszystkie wejścia, nawet np. (1000 998) i wszystko program liczy dobrze. SPOJ pokazuje jednak "błędna odpowiedź". W czym może być problem?

2

Twoimi problemami są:

  1. Bezsensowne użycie liczb zmiennoprzecinkowych do tego problemu. U mnie wyniki dla 1000 998 i 1000 2 są różne,user image
  2. Dziwny algorytm, 1000 998 nie powinien wykonywać 998 iteracji, kiedy może dwie.
1
  1. Spróbuj nie używać double
  2. Wygeneruj rożne dane testowe i sprawdź co może nie działać: http://ideone.com/NbWaQu http://www.wolframalpha.com/input/?i=combinations%2833,+16%29
  3. if (2*k<n) k = n - k; if (2*k>n) k = n - k;
0
#include <iostream>

using namespace std;

int Binomial(int n, int k)
{
	if (k * 2 > n)
		k = n - k;
	double wynik = 1;
	for (int i = 1; i <= k; i++)
		wynik = wynik * (n-i+1)/i;
	return wynik;
}

int main()
{
	int t; cin >> t;
	for (int i = 1; i <= t;i++)
	{
		int n, k; cin >> n >> k;
		cout << Binomial(n, k) << endl;
	}
	return 0;
} 

Dalej SPOJ pokazuje, że błędna odpowiedź. Chyba będzie trzeba faktycznie szukać co raz to kolejnych inputow dla których output się nie zgadza. Jak na razie nie udało mi się znaleźć takiego.

2

Zamieniłeś long long na int, a double zostawiłeś. Nie o to nam chodziło gdy pisaliśmy, abyś nie używał double/liczb zmiennoprzecinkowych.

Ok, popatrzyłem na moje przeszłe rozwiązania na spoju oraz na to co się zgadza spoj teraz:

  1. naiwne rozwiązanie na liczbach 64-bitowych to za mało. Wynik nie przekroczy 1e9, ale najwyraźniej licznik (ew. mianownik) ułamka nie muszą mieścić się w 64 bitowych zmiennych. Tutaj jest moje rozwiązanie w D, raczej Cię nie natchnie, bo po przejściu z BigInt do ulong (64 bity w D), rozwiązanie jest odrzucane: https://github.com/KrzaQ/mySPOJ/blob/master/BINOMS%20-%20Dwumiany/main.d
  2. w C++ podliczam sobie za pomocą Trójkąta Pascala wszystkie wyniki i potem z nich serwuje odpowiedzi. W ten sposób nigdy nie przekraczam górnego zakresu wartości obsługiwanych przez typ danych.
0

Jak zmieniłem wszystko na long long to weszło

#include <iostream>

using namespace std;

long long Binomial(long long n, long long k)
{
	if (2* k > n)
		k = n - k;
	long long wynik = 1;
	for (int i = 1; i <= k; i++)
		wynik = wynik * (n-i+1)/i;
	return wynik;
}

int main()
{
	int t; cin >> t;
	for (int i = 1; i <= t;i++)
	{
		long long n, k; cin >> n >> k;
		cout << Binomial(n, k) << endl;
	}

	//system("pause");
	return 0;
} 

PS: Tak wiem, że intelektualnie to się nie napracowałem :)

0

Już było, dawno temu: http://4programmers.net/Forum/1223938

1

W sumie to się zastanawiam, czemu z double nie przechodzi. double ma 52 bity mantysy na x86 więc nie powinno być utraty dokładności przy takim zakresie danych wejściowych.

1 użytkowników online, w tym zalogowanych: 0, gości: 1