Dwumiany - brak pomysłu co dalej ;(

Question

Hej!

Zadanie dotyczy obliczania ile jest możliwości wyznaczenia ze zbioru n elementowego zbioru k elementowego. (dwuman Newtona)

Próbowałam rozwiązywać to na kilka sposobów, ale niestety na spoju nie zalicza.

Pierwszym pomysłem było pisanie silni ale niestety zbyt duże wartości przekraczające long long int ;(

Drugim było wyznaczenie odpowiedniej wartości z tzw trójkąta Pascala - długo zajmowało liczenie

Trzecim sposobem bylo wyznaczenie odpowiedniego iloczynu i na bieżąco skracanie ułamków..

Niestety wyskakuje błędna odpowiedz a ja juz nie wiem co zrobiłam tam żle..podejrzewam jednak, że gdzieś pojawia się przepełnienie i dlatego ;(

tu link do zadania https://pl.spoj.com/problems/BINOMS/

tu mój kod (trzeci pomysł):

#include <iostream>
//#include <iomanip>
using namespace std;



int main()
{

    int n;
    int k;
    cin>>n>>k;
    if(k>n/2)
        k=n-k;
    //cout<<k<<endl;

    long long int iloczyn=1;
    int doIlu=n-k+1;
    long long int wynik;
    if(k==1) cout<<n<<endl;
    else if(k==0) cout<<1<<endl;
    else
    {
        for(int i=n;i>=doIlu;i--)
    {
        //cout << setprecision(1000);
        iloczyn=iloczyn*i;
        //cout<<iloczyn<<endl;
    }
    //cout<<"iloczyn "<<iloczyn<<endl;
    //cout<<"DO ilu "<<doIlu<<endl;
    for(int j=2;j<k+1;j++)
    {
        wynik=iloczyn/j;
        iloczyn=wynik;
    }
    cout<<wynik<<endl;
    }

    return 0;
}

Będę wdzięczna jeśli ktoś mnie nakieruje <3

Comments

Zadanie jest trudne, bo silnia szybko przepełnia zakres liczb :) Trzeba szukać dzielników :)

---

W sumie próbowałam.. jakies tam nwd ale sam fakt ze tam pojawia się silnia generuje problem.. W teorii dzielenie juz powinno troche skrócić liczenie ale nadal nie wiem czemu błędna odpowiedź

Answer 1

Dałem niedawno przykład jak to policzyć:

https://www.wolframalpha.com/input/?i=binominal%28320%2C300%29

 

g++ -std=c++11 -O3 main.cpp -o main
./main 
Podaj K: 300
Podaj N: 320
28419027580261196864563227795376

Typ buint trzeba dostosować do swojego systemu.

Dla VC jest tam:

https://stackoverflow.com/questions/6759592/how-to-enable-int128-on-visual-studio

 

#include <iostream>

typedef unsigned __int128 buint;

static std::ostream& operator<<( std::ostream& dest, buint value ) {
    std::string buf;
    while( value ) {
        char c[2] = "0";
        c[0] += value % 10;
        value /= 10;
        buf = c + buf;
    }
    if( buf.size() == 0 ) {
        buf = "0";
    }
    dest << buf;
    return dest;
}

class MyException : public std::exception {
private:
    const std::string swhat;

public:
    MyException( const char *const swhat ) : swhat(swhat) {
    }

    virtual const char* what() const throw(){
        return swhat.c_str();
    }
};

static int getK() {
    std::cout << "Podaj K: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < 1) {
        throw MyException("Nieprawidłowe K");
    }
    return n;
}

static int getN(const int k) {
    std::cout << "Podaj N: ";
    int n;
    std::cin >> n;
    if( std::cin.fail() || n < k ) {
        throw MyException("Nieprawidłowe N");
    }
    return n;
}


int main(int argc, char *argv[]) {
    (void)argc;
    (void)argv;
    try {
        buint K  = getK();
        buint N  = getN( (int)K );
        if( K > N/2 ) {
            K = N-K;
        }
        buint IK = 2;
        buint IN = 1;
        buint v = 1;
        while( IN <= K || IK <= K ) {
            while( IK <= K && v % IK == 0 ) {
                v /= IK ++ ;
            }
            if( IN <= K ) {
                v *= N - K + IN ++ ;
            }
        }
        std::cout << v << std::endl;
    }
    catch( std::exception &e ) {
        std::cout << "Wystapił błąd: " << e.what() << std::endl;
    }
    return 0;
}