Dwumian Newtona

Question

Zadanie: 
Napisz program, który wczytuje pary liczb 33>=n>=k>=0 a następnie wypisuje współczynniki dwumianowe "n nad k". 

Pary liczb wczytuj tak długo, aż pojawi się para 0,0. Wówczas wypisz ostatni wynik ("0 nad 0" wynosi 1) i zakończ wczytywanie.

Przykładowe dane:
2 1
15 3
0 0

Wynik:
2
455
1
Problem: 
Program wywal się prze danych 5 0 i nie pokazuje wyniku dla 0 0. Gdy usunę pierwsze wprowadzanie n i k w main i zostawię tylko to w pętli, program pokazuje wynik dla 0 0 ale wywal się przy 5 0 

 
Mój kod: 
 

#include <iostream>

using namespace std;

bool dwumian_Newtona(int n, int k)
{
    int roznica_nk = (n - k);
    unsigned long int wynik = 1;
    int najwieksza = 0;
    int obroty = 0;

    // sprawdzam newralgiczne przypadki
    if (k == 0 || k == n)
        cout /*<< "tu: "*/ << '1' << endl;
    else
    {
        // sprawdzamy która silnia w mianowniku jest większa, aby później mogła zosatć skrócona z licznikiem
        if (k > roznica_nk)
        {
            najwieksza = k;
            obroty = roznica_nk;
        }
        else
        {
            // liczba obrotow calego programu zalezy od liczby w mianowniku
            najwieksza = roznica_nk;
            obroty = k;
        }

        // metoda z lekcji (sasiednia para w liczniku/pierwsza liczba z mianownika), wynik poprzedni*nastepna z licznika/2 liczba w mianowniku itd.
        int y = 1;
        while (y < obroty)
        {
            for (int i = (najwieksza + 1); i <= n; i++)
            {
                //cout << "i: " << i << " i+1: " << i + 1 << endl;
                //cout << "y: " << y << endl;
                wynik = (wynik * (i) / y);
                //cout << "Wynik w petli: " << wynik << endl;
                y++;
            }
        }
        cout << "wynik: " << wynik << endl;
    }
}

int main()
{
    int n = 0;
    int k = 0;

    cin >> n;
    cin >> k;
    while ((n != 0) && (k != 0))
    {
        dwumian_Newtona(n, k);
        cin >> n;
        cin >> k;
    }
    cout << "out of while!" << endl;
    return 0;
}

/*

 

Answer 1

Masz kilka błędów.

Po pierwsze funkcja dwumian_Newtona zwraca typ bool, a ty nie zwracasz nic, także warto ją zamienić na typ void.

Po drugie warunek pętli while jest zły ponieważ ona się wykonuje do momentu kiedy n i k są różne od zera, więc jeśli jedno z nich jest równe 0 kończy działanie.

Najpierw w tej while wyświetlasz dane a dopiero potem pobierasz nowe, dlatego jeśli pętla się kończy to zostawiasz te 2 liczby i nic z nimi nie robisz, proste rozwiązanie wywołać jeden raz funkcję po while.

Drobne nieścisłości jakieś jeszcze się znajdą ale to już mniejsza. Na dole poprawiony kod, aby działał.

#include <iostream>
 
using namespace std;
 
void dwumian_Newtona(int n, int k)
{
    int roznica_nk = (n - k);
    unsigned long int wynik = 1;
    int najwieksza = 0;
    int obroty = 0;
 
    // sprawdzam newralgiczne przypadki
    if (k == 0 || k == n)
    {
        cout /*<< "tu: "*/ << "wynik: 1" << endl;
        return;
    }
    else
    {
        // sprawdzamy która silnia w mianowniku jest większa, aby później mogła zosatć skrócona z licznikiem
        if (k > roznica_nk)
        {
            najwieksza = k;
            obroty = roznica_nk;
        }
        else
        {
            // liczba obrotow calego programu zalezy od liczby w mianowniku
            najwieksza = roznica_nk;
            obroty = k;
        }
 
        // metoda z lekcji (sasiednia para w liczniku/pierwsza liczba z mianownika), wynik poprzedni*nastepna z licznika/2 liczba w mianowniku itd.
        int y = 1;
        while (y < obroty)
        {
            for (int i = (najwieksza + 1); i <= n; i++)
            {
                //cout << "i: " << i << " i+1: " << i + 1 << endl;
                //cout << "y: " << y << endl;
                wynik = (wynik * (i) / y);
                //cout << "Wynik w petli: " << wynik << endl;
                y++;
            }
        }
    }
    cout << "wynik: " << wynik << endl;
}
 
int main()
{
    int n = 0;
    int k = 0;
 
    cin >> n;
    cin >> k;
    while (!((n == 0) && (k == 0)))
    {
        dwumian_Newtona(n, k);
        cin >> n;
        cin >> k;
    }
    dwumian_Newtona(n, k);
    cout << "out of while!" << endl;
    return 0;
}

 

Comments

Zadanie zaliczone, musiałem jeszcze 2 warunki dopisać. O jakich błędach mówisz ?

---

To co widziałem to poprawiłem. W stylu, że w złym miejscu masz wypisanie wyniku, raz wypisujesz wynik,raz nie. Nic poważniejszego.

Answer 2

Na kilku przykładach u mnie to zadziałało:

#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;
    std::cout << sizeof(buint) << std::endl;
    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;
}

 

Comments

prog.cpp:29:38: warning: dynamic exception specifications are deprecated [-Wdeprecated-dynamic-exception-spec]
    virtual const char* what() const throw(){
                                     ^~~~~~~
prog.cpp:29:38: note: use 'noexcept' instead
    virtual const char* what() const throw(){
                                     ^~~~~~~
                                     noexcept
prog.cpp:26:36: warning: constructor parameter 'swhat' shadows the field 'swhat' of 'MyException' [-Wshadow-field-in-constructor]
    MyException( const char *const swhat ) : swhat(swhat) {
                                   ^
prog.cpp:23:23: note: previous declaration is here
    const std::string swhat;
                      ^
prog.cpp:60:20: warning: implicit conversion changes signedness: 'int' to 'buint' (aka 'unsigned __int128') [-Wsign-conversion]
        buint K  = getK();
              ~    ^~~~~~
prog.cpp:61:26: warning: use of old-style cast [-Wold-style-cast]
        buint N  = getN( (int)K );
                         ^    ~
prog.cpp:61:20: warning: implicit conversion changes signedness: 'int' to 'buint' (aka 'unsigned __int128') [-Wsign-conversion]
        buint N  = getN( (int)K );
              ~    ^~~~~~~~~~~~~~
prog.cpp:21:7: warning: 'MyException' has no out-of-line virtual method definitions; its vtable will be emitted in every translation unit
      [-Wweak-vtables]
class MyException : public std::exception {
      ^

 

---

typedef unsigned __int128 buint;

To rozwiązanie nie ma racji bytu, przy wyżej wymienionym problemie autora. Jest to wyłącznie dla gcc.

 http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf 7.20.1.1

---

U mnie się kompiluje, uruchamia i na kilku przykładach przeszło testy. Mam ustawione c++11. Coś musisz dostosować do swojego środowiska.

 

g++ -std=c++11 -O3 main.cpp -o main
./main
16
Podaj K: 990
Podaj N: 1000
263409560461970212832400

 

---

[

To rozwiązanie nie ma racji bytu, przy wyżej wymienionym problemie autora. Jest to wyłącznie dla gcc.

]

Przeczytaj uważnie kod zamiast pleść że nie ma racji bytu, specjalnie jest typedef, aby łatwo dostosować do dowolnego środowiska, może nawet do GMP by się udało. Pod windowsem może być __uint128;

---

Na gcc, ale w innym środowisku może być lipa. Myślę, że mokrowski ma trochę więcej flag.

---

Nie umiecie wpisać long long w typedef?

A tu macie dla visual studio int 128:

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

---

VS19Twój kod nie przejdzie na Spoju po prostu. 

 

---

Mój kod nie jest po to aby cokolwiek przechodził, jest poglądowy, do analizy, do rozmowy, itd. Musicie też być trochę samodzielni. Jak przedefiniowaleś w typedef na typ dla którego już jest przeładowany operator <<, to zakomentuj jeszcze (zdublowaną) funkcję operatorową:

 

Spróbuj tak:

#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;
    std::cout << sizeof(buint) << std::endl;
    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 ++ ;
                std::cout << "x";
            }
            std::cout << std::endl;
            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;
}

 

Albo tak:

#include <iostream>

typedef unsigned long long 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;
    std::cout << sizeof(buint) << std::endl;
    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 ++ ;
                std::cout << "x";
            }
            std::cout << std::endl;
            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;
}

 

Edit:

Jestem ciekawy czy ta heurystyka z dzieleniem w pętli wewnętrznej coś pomaga i czy mnożenie od namniejszych coś daje.

Pozdrawiam

---

Kurczę, Twój kod nie jest zgodny ze standardem po prostu, nic więcej. Zmiana 128 bitowej liczby na 64, raczej może być dość znacząca...

---

Nie wiem czy jest niezgodny ze standardem C++11. Na typ int128 można spojrzęć jak na typ biblioteczny, a biblioteki w kompilacji pomiędzy różnymi systemami zawsze się dostosowywało. Może trzeba npisać coś w tym stylu:

ifdef linux

typedef ...

ifdef windows

typedef ...

Każda przenośna biblioteka w C++ ma masę tego typu ustawień preprocesora.

 

Ale powtórzę, z typem long long powinno działać.

---

Jeszcze jedna poprawka, był zbędny backslash:

#include <iostream>

typedef unsigned long long 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;
    std::cout << sizeof(buint) << std::endl;
    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 ++ ;
                std::cout << "x";
            }
            std::cout << std::endl;
            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;
}