Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Policzenie wszystkich kombinacji liczby danej wzorem

Ostatnio zmodyfikowano 2016-04-24 14:46
Autor Wiadomość
michal11
» 2016-03-22 20:34:12
Jednak zostawiłem trochę bałaganu w wypisywaniu.

C/C++
#include <iostream>
#include <iomanip>
using namespace std;
#include <conio.h>
#include <string>
#include <vector>
#include <cmath>
#include <limits>

//====================================================================================================================

double computeW( int pX, int pY, int pP, const vector < vector < int >>& pXn, const vector < int >& pXIndxs );
bool isNaturalNum( double value );
double newton( unsigned int n, unsigned int k );

//====================================================================================================================

int main()
{
    int x = 73;
    int y = 5;
    int p = 49667;
   
    cout << "Podaj x: ";
    cin >> x;
    cout << "Podaj y: ";
    cin >> y;
    cout << "Podaj p: ";
    cin >> p;
   
    vector < vector < int >> xn( y - 1, vector < int >( x + 1 ) );
   
    for( auto & vec: xn )
    {
        for( int i = 0; i <= x; ++i )
        {
            vec[ i ] = i;
        }
    }
   
    vector < int > xIndxs( xn.size(), 0 );
    double w;
    bool exit = false;
    double counter = 0;
    unsigned long long howManyFound = 0;
   
    cout << "Start " << endl;
   
    while( !exit )
    {
        counter++;
       
        w = computeW( x, y, p, xn, xIndxs );
        if( isNaturalNum( w ) )
        {
            ++howManyFound;
           
            cout << "w= " << fixed << w << "; ";
            for( int i = 0; i < xn.size(); ++i )
            {
                cout << "x" << i + 1 << "=" << xn[ i ][ xIndxs[ i ] ] <<( i == xn.size() - 1 ? ""
                    : ", " );
            }
            cout << endl;
        }
       
        ++xIndxs[ 0 ];
       
        for( int j = xIndxs.size() - 1; j > 0; --j )
        {
            if( xIndxs[ j ] == x )
            {
                if( j == xIndxs.size() - 1 ) { exit = true; break; }
               
                ++xIndxs[ j + 1 ];
               
                for( int pom = j; pom >= 0; --pom )
                {
                    xIndxs[ pom ] = xIndxs[ j + 1 ];
                }
               
                break;
            }
        }
       
        if( xIndxs[ 0 ] == x + 1 )
        {
            if( xIndxs.size() >= 2 )
            {
                ++xIndxs[ 1 ];
                xIndxs[ 0 ] = xIndxs[ 1 ];
            }
            else
            {
                exit = true;
            }
        }
    }
   
    cout << "Koniec" << endl;
    cout << "wszystkich iteracji: " << fixed << setprecision( 0 ) << counter << endl;
    cout << "Policzonych, calkowitych liczb w: " << howManyFound << endl;
   
    getch();
    return 0;
}
//====================================================================================================================
double computeW( int pX, int pY, int pP, const vector < vector < int >>& pXn, const vector < int >& pXIndxs )
{
    double retVal = 0;
   
    int lastPow;
    for( int i = 0; i < pXn.size(); ++i )
    {
        retVal += pow( 2, pXn[ i ][ pXIndxs[ i ] ] ) * pow( pP, i ) / pow( 2, i );
       
        lastPow = i + 1;
    }
   
    retVal += pow( pP, pY - 1 ) / pow( 2, pY - 1 );
    retVal *= pow( 2, pY - 1 );
    retVal /= pow( 2, pX + pY ) - pow( pP, pY );
   
    return retVal;
}

//*****************************************************************************
bool isNaturalNum( double value )
{
    unsigned long long intPart = value;
    double rest = value - intPart;
   
    return rest == 0;
}
//*****************************************************************************
double newton( unsigned int n, unsigned int k ) // not working
{
    double Wynik = 1;
   
    for( unsigned int i = 1; i <= k; i++ )
    {
        Wynik = Wynik *( n - i + 1 ) / i; // Obliczanie ze wzoru iteracyjnego
    }
   
    return Wynik;
}

po czym, gdy program skończy pracę, niech wypisze wynik i ponownie prosi o nowe zmienne.
Dodaj pętlę zewnętrzną. Ile tych powtórzeń ma być ?

3. Fajnie by było, gdyby program informował o postępie procentowo np. co 3 minuty
Z tym jest problem, ponieważ okazało się, że funkcja newton źle oblicza ile tych iteracji ma być to jest praktycznie nie do zrobienia, można wypisywać co 3 min. ile już się wykonało ale baz danych ile jeszcze to ma niewiele sensu. Jak napiszesz lub znajdziesz dobrze liczącą funkcję newtona to można o to poprawić.
P-146427
osobliwy_nick
Temat założony przez niniejszego użytkownika
» 2016-03-22 21:09:13
Najlepiej dowolna ilość powtórzeń.

Chodzi o funkcję Newtona wziętą z jakichś bibliotek C++? To łatwe do policzenia, bo:

(x+y) po y = (x+y)!/(y! * x!)

Przy czym "!" oznacza silnię. Czyli ogólnie ilość kombinacji jakie liczby program wynosi:

y/(x+y) * (x+y)!/(y! * x!)

Z policzeniem silni chyba nie będzie problemu.

PS Cały czas jest problem z weryfikacją całkowitości liczb np. dla p-49667, y=5 i x=73. Czy to wynika z nieodpowiednich typów zmiennych (za krótkich, które nie mieszczą odpowiedniej ilość liczb po przecinku), przez co całe obliczenia przeprowadzane są zaokrąglanych liczbach typu 1,2567 * 10^10 (pomimo, że liczba ma 10 miejsc po przecinku), czy coś nie tak stricte ze sposobem sprawdzenia czy liczba jest naturalna? A może mamy pełne 10 miejsc po przecinku, ale sam test naturalności kończy na powiedzmy 1,25676, uznając liczbę za naturalną i dopisując dalej zera 12567600000 podczas, gdy rozpatrywana liczba wygląda naprawdę tak 125676222222,14. Pewnie występuje jeden z tych problemów.
P-146429
michal11
» 2016-03-22 21:29:29
Właśnie z policzeniem silni jest problem, bez używania dodatkowych bibliotek dla bigIntów można obliczyć silnię dla max bodajże 20el (nie sprawdzałem tego dokładnie) czyli twoje x+y nie mogło by być większe niż 20.
Dlatego napisałem, że jak sam napiszesz algorytm albo znajdziesz jakiś działający w internecie na obliczanie dwumianu newtona to można to poprawić, teraz to nie działa.

Edit.
Akurat nic lepszego niż double bez używania bibliotek nie znajdziesz. Co masz na myśli przez "problem z weryfikacją całkowitości liczb" ?
P-146431
osobliwy_nick
Temat założony przez niniejszego użytkownika
» 2016-03-22 21:45:00
Można skrócić ten wzór:

(x+y) po y = (x+y)!/(y! * x!) = (x+1)*(x+2)*...*(x+y)/(y!)  --> gdy x jest większe niż y

albo

(x+y) po y = (x+y)!/(y! * x!) = (y+1)*(y+2)*...*(x+y)/(x!)  --> gdy y jest większe niż x

Gdy x=y oba wzory będą tak samo wydajne. Przykład:

(73+5) po  = (78)!/(5! * 73!) = 1*2*3*...*73*74*75*76*77*78/(1*2*3*4*5 * 1*2*3*...*73) = 74*75*76*77*78/(1*2*3*4*5) =

Jakkolwiek potrzeba użycia dużych intów dla jeszcze większych wartości znów może się pojawić. Czy źródłem problemów ze sprawdzaniem naturalności liczb nie są też za małe inty lub za małe liczby zmiennoprzecinkowe? Chodzi mi o to, że program znajduje fałszywe "w" dla parametrów p=49667, x=73 i y=5, a także dla niektórych innych parametrów.

EDIT:

Właściwie to nie ma sensu chyba zajmować się nawet powyższym uproszczonym wzorem na symbol newtona. Silnię najlepiej liczyć od razu wzorem Stirlinga:

n! = (n/e)^n * (2*pi*n)^0,5

To powinno załatwić sprawę. Przy czym e to liczba Eulera. Trzeba tylko pamiętać, że daje on przybliżenie, ale na potrzeby sprawdzania postępu wystarczy.

https://pl.wikipedia.org/wiki/Wzór_Stirlinga
P-146433
michal11
» 2016-03-22 22:03:33
Czy źródłem problemów ze sprawdzaniem naturalności liczb nie są też za małe inty

Może tak być, aktualnie największa liczba którą można sprawdzić czy jest całkowita wynosi : 18446744073709551615 czyli 1.84467e+19, wydawało mi się, że spełnia to twoje wymagania.
P-146440
osobliwy_nick
Temat założony przez niniejszego użytkownika
» 2016-03-22 22:22:38
To też nie to. Podam przykład. Program twierdzi, że liczba:

(2^68+2^68*49667/2+2^68*49667^2/4+2^11*49667^3/8+49667^4/16)*16/(2^78-49667^5) = 2912413543064874015563107240017 / 13734584404743437

jest całkowita i wynosi 212049630284467. W rzeczywistości wynosi ona:

2.1204963013362311524700845051409607825619882905555198... * 10^14

Program chyba błędnie dzieli liczby.
P-146443
michal11
» 2016-03-22 22:47:59
Niestety ale już nie jestem w stanie ci pomóc. Prawdopodobnie liczby są za duże, ale niewiele więcej jestem w stanie zrobić.
P-146446
osobliwy_nick
Temat założony przez niniejszego użytkownika
» 2016-03-22 23:06:05
Ok. I tak dużo pomogłeś. Program jest właściwie gotowy. Tylko, że jednym z pierwszych przypadków, które chciałem w nim sprawdzić była liczba p=49667. Jeżeli problem tkwi tylko w liczbach, to chyba można pobrać odpowiednie biblioteki? Np. GMP:

https://gmplib.org

Choć nie wiadomo, czy na pewno o to chodzi.

EDIT:

Dodam tylko, że na pewno chodzi o typy zmiennych. Gdy zdefiniowałem "w" jako float, a nie double, program znalazł jeszcze więcej fałszywych rozwiązań. Prawdopodobnie po prostu ucinając "nadprogramowe" liczby (nie policzywszy ich nawet do końca, gdy np. do dodania był jeszcze człon 49667^4/16 po prostu nie zostawał dodany, tylko wyzerowany, bo nie było na niego miejsca) i podając te obcięte wyniki jako liczby całkowite.

EDIT:

Wprowadziłem 2 zmiany w programie. Program działa także dla "w" ujemnych, na koniec dopisując, że liczył na ujemnych "w". Do tego program zawieszał się dla y=1. Zostało to rozwiązane prosto, gdyż gdy y=1 zawsze istnieje tylko jedno rozwiązanie w=1.
P-146447
1 2 3 « 4 » 5
Poprzednia strona Strona 4 z 5 Następna strona