Obliczanie dwumianu

Witam
rozwiazuje takie zadanie:
Dla liczb całkowitych n i k, 0 <= k <= n <= 1000, wyznacz liczbę różnych k-elementowych podzbiorów zbioru n-elementowego. Liczby n i k będą dobrane tak, aby wynik nie przekroczył 1 000 000 000.

Nie wiem dlaczego mam przekroczony limit czasu wykorzystalem algorytm rekurencyjny z tego co wiem nie ma szybszego?

// Dwumiany.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int dwumian(int n, int k)
{
   if(k==0||k==n)
   {
      return 1;
   }
   else
   {
      return ((dwumian(n-1,k-1))+(dwumian(n-1,k)));
   }
}


int _tmain(int argc, _TCHAR* argv[])
{
   int t;
   cin>>t;

   while(t)
   {
      int a,b;
      cin>>a>>b;
      cout<<dwumian(a,b)<<endl;

      t--;
   }

   cin.ignore();
   getchar();
   return 0;
}

Rekurencja jest najprostszym ale najwolniejszym rozwiązaniem.
Zwróć uwagę ile razy liczysz dwumian(3,2) jeśli chcesz mieć wynik dwumian(6,2)!
To jest więcej niż 4 razy, więc dla większych liczb problem jest o wile większy!
Problem był już na forum więc, jak się postarasz to znajdziesz lepsze rozwiązanie.

Trójkąt Pascala.
http://pl.wikipedia.org/wiki/Tr%C3%B3jk%C4%85t_Pascala

To jest akurat powolne rozwiązanie.
Ok mam dobry humor, więc:

unsigned long long int symbolNewtona(unsigned int n, unsigned int k)
{
    if(k==0) {
         return 1;
    }
    if(k<0) {
         return 0;
    }

    if(n<(k<<1)) {
         return symbolNewtona(n, n-k);
    }

    unsigned long long int result = n;
    for(int i=2; i<=k; ++k) {
         result *= --n;
         result /= i;
    }

    return result;
}

Zrobilem tak

// Dwumiany.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

unsigned long long int symbolNewtona(unsigned int n, unsigned int k);


int _tmain(int argc, _TCHAR* argv[])
{
	unsigned int a,b;
	int t;
	cin>>t;

	while(t)
	{		
		cin>>a>>b;
		cout<<symbolNewtona(a,b);

		t--;
	}

	cin.ignore();
	getchar();
	return 0;
}

unsigned long long int symbolNewtona(unsigned int n, unsigned int k)
{
    if(k==0) 
	{
         return 1;
    }
    if(k<0)
	{
         return 0;
    }

    if(n<(k<<1)) 
	{
         return symbolNewtona(n, n-k);
    }

    unsigned long long int result = n;
    for(unsigned int i=2; i<=k; ++k)
	{
         result *= --n;
         result /= i;
    }
    return result;
}

kompiluje sie poprawnie ale nie wyswietal odpowiedzi

w tym miejscu jakis blad musi byc

unsigned long long int result = n;
    for(unsigned int i=2; i<=k; ++k)
	{
         result *= --n;
         result /= i;
    }
    return result;

int tab[1000] = { 1 };

int silnia(int k) {
  for(int i = 1; i < k; i++)
    tab[i] = tab[i-1] * i; 
}

int dwumian(int n, int k) {
  return silnia(n)/(tab[k]*tab[n-k]);
}

Da się jeszcze trochę poprawić dla twoich wymagań, ale nie będę za ciebie odwalał roboty...

golota318 napisał(a)

w tym miejscu jakis blad musi byc

unsigned long long int result = n;
    for(unsigned int i=2; i<=k; ++k)
	{
         result *= --n;
         result /= i;
    }
    return result;

Ok znalazlem blad poprawnie ma byc

unsigned long long int result = n;
    for(unsigned int i=2; i<=k; ++i)
	{
         result *= --n;
         result /= i;
    }
    return result;

winerfresh napisał(a)

int tab[1000] = { 1 };

int silnia(int k) {
  for(int i = 1; i < k-1; i++)
    tab[i] = tab[i-1] * i; 
}

int dwumian(int n, int k) {
  return silnia(n)/(tab[k]*tab[n-k]);
}

Da się jeszcze trochę poprawić dla twoich wymagań, ale nie będę za ciebie odwalał roboty...

Dzieki za pomoc ale wlasnie znalazlem blad i juz wszystko ok ale jeszcze raz dzieki wszystkim za pomoc

fakt, takie było zamierzenie (standardowa pętla for) - jednak wkradła się mała literówka :)