Witajcie, napisałem rozwiązanie do zadania o dwumianach, lecz najprawdopodobniej mój własny algorytm jest za wolny, bo SPOJ pokazuje mi błąd “Przekroczono limit czasu.” Czy macie jakieś wskazówki co do optymalizacji? Może powinienem zastanowić się nad innym sposobem liczenia, albo zaimplementować gotowy wzór, bo być może samo to jest w sobie trudne?
Moja metoda polega na zliczeniu po kolei kombinacji np. w zbiorze 4 elementowym liczba podzbiorów 2 elementowych to po kolei: 123, 124, 134, 234, czyli wynik to 4.
#include <iostream>
using namespace std;
inline void liczbaE(int& wynik, int& zb_g, int& pod_zb, int kol, int w)
{
if(kol == pod_zb)
{
wynik += zb_g-w+1;
}
else
{
for(; w <= kol+zb_g-pod_zb; w++)
{
liczbaE(wynik, zb_g, pod_zb, kol+1, w+1);
}
}
}
int main()
{
int t;
cin >> t;
while(t--)
{
int zb_g /* ilosc elementow w zbiorze glownym */,
pod_zb /* ilosc elementow w podzbiorach */;
cin >> zb_g >> pod_zb;
if(pod_zb == 1)
cout << zb_g + 1 << endl;
else if( zb_g == pod_zb || pod_zb == 0)
cout << "1" << endl;
else
{
int wynik{0};
liczbaE(wynik, zb_g, pod_zb, 1, 1);
cout << wynik << endl;
}
}
return 0;
}