michal11 |
» 2016-03-21 20:09:47 Minęło ponad 12min i ciągle nie osiągnąłem choćby 1%, przerywam teraz, bo już mi się nie chce czekać. Dla danych x=13, y=2, p=181 znalazłem:
w= 27; x1=2
w= 35; x1=5
w= 99; x1=8
w= 611; x1=11
Tylko nie wiem czemu wyniki mi się powtarzają, dziwne. Edit. Masz jeszcze taki kod, on się nie zawiesza tylko mi pokazuje, że wykonało się mniej iteracji niż miało być, jesteś pewny, że twoje obliczenia co do ilości iteracji są prawidłowe ? A może to błąd funkcji newton, nie wiem, i szczerze mówiąc już mi się nie chce tego sprawdzać, w zasadzie to rozwiązałem twój problem z tego tematu. #include <iostream>
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 = 78;
int y = 5;
int p = 49667;
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;
double howMany = newton( x + y, y ) / 2;
bool exit = false;
unsigned long long counter = 0;
cout << "Start " << endl;
while( !exit )
{
counter++;
w = computeW( x, y, p, xn, xIndxs );
if( isNaturalNum( w ) )
{
cout << "w= " << 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 + 1 || 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;
}
}
}
cout << "Koniec c:" << counter << ", hm:" << howMany << 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 )
{
double Wynik = 1;
for( unsigned int i = 1; i <= k; i++ )
{
Wynik = Wynik *( n - i + 1 ) / i;
}
return Wynik;
}
|
|
osobliwy_nick Temat założony przez niniejszego użytkownika |
» 2016-03-21 20:32:01 A możesz sprawdzić p=49667, y=5, x=78? Czy też nie daje rady?
Też nie wiem czemu wyniki się powtarzają.
|
|
michal11 |
» 2016-03-21 20:34:23 Zaktualizowałem poprzedni post, wyniki się powtarzały bo pętla wykonywała się więcej razy niż było indeksów w tablicy.
Dla p=49667, y=5, x=78 nie znajduje mi liczb całkowitych, a generowania liczby w było 1666900 razy. |
|
osobliwy_nick Temat założony przez niniejszego użytkownika |
» 2016-03-21 21:03:12 Dla y=3 i x=3 wychodzi, że x1,x2 należą do [0,2]. Możemy zatem utworzyć:
000
100
200
110
210
220
211
221
111
222
czyli 10 kombinacji. Program liczy ich jak rozumiem tylko 7. Tych kombinacji powinno być chyba y/(x+y) * ((x+y) po y). Przy czym ((x+y) po y) to symbol newtona. Jestem niemal pewien, że tyle ich powinno być. W każdym razie na pewno coś jest nie tak, co obrazuje powyższy przykład.
Dla y=5 i x=78 powinno być natomiast 1749060 komibnacji. Ciekawe, że dla p=181, x=13 i y=2 program wykonał błędną liczbę operacji, bo 13 zamiast 14, ale znalazł wszystkie rozwiązania. Nie wiadomo, czy zgubił tylko jedną kombinację, czy powtórzył kilka razy te same, a zgubił ich więcej. Wydaje mi się, że nie przyjął x1=0 lub x1=13.
Kolejnym problemem jest fakt, że program znajduje rozwiązania dla p=49667, x=73, y=5, pomimo, że takie nie istnieją. Np. dla x1=70, x2=69, x3=69, x4=65. I dla wielu innych (które są bliskie liczbom całkowitym). Sprawdziłem niektóre z nich w Wolfram Alpha i nie są prawdziwe. Tak naprawdę w ogóle nie wiadomo, które są prawdziwe, a program wypisał ich kilkadziesiąt. Jest zatem problem z dokładnością obliczeń dla dużych liczb. |
|
michal11 |
» 2016-03-21 21:56:06 Możesz to sprawdzić np. wypisując sobie poszczególne parametry.
Jeżeli chodzi o niedokładności wyników to pewnie jest to spowodowane użyciem typu double i moim "prostym" sposobem na sprawdzenie czy liczba jest całkowita czy nie. |
|
osobliwy_nick Temat założony przez niniejszego użytkownika |
» 2016-03-22 14:40:32 Będę musiał zmienić te double na jakieś lepsze rodzaje zmiennych. A jak sprawdzasz, czy dana liczba jest naturalna? Z tego co widzę użyłeś jakiejś funkcji (a ta sprawdza pewnie tylko skończoną liczbę miejsc po przecinku lub samo dzielenie wykonuje się do skończonych miejsc po przecinku)?
Ponadto nie widzę w tym kodzie jak udało Cię wyłonić ze wszystkich kombinacji (x+y) po y tylko te w których x1>=x2>=...>=xn. Tam gdzieś musi być drobny błąd. Może program nie bierze przypadków x1=x2=...xn? To by tłumaczyło dlaczego dla x=3 i y=3 brakuje akurat 3 przypadków.
PS A jak będzie wyglądał program, gdy zrezygnujemy z warunku x1>=x2>=...>=xn i policzymy po prostu wszystkie kombinacje? Ostatecznie tak też można zrobić.
|
|
michal11 |
» 2016-03-22 16:14:41 Ehh, rozpisałem się jak działa program, ale nie zauważyłem, że mój post nie został zapisany i wszystko poszło w piach. Tu masz poprawiony kod, potestowałem trochę i działa teraz dobrze, był problem dla indeksów x1. #include <iostream>
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 = 3;
int y = 4;
int p = 3;
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;
double howMany = newton( x + y, y ) / 2;
bool exit = false;
unsigned long long counter = 0;
cout << "Start " << endl;
while( !exit )
{
counter++;
w = computeW( x, y, p, xn, xIndxs );
if( isNaturalNum( w ) )
{
cout << "w= " << w << "; \n";
for( int i = 0; i < xn.size(); ++i )
{
}
}
++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 c:" << counter << ", hm:" << howMany << 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 );
cout << retVal << endl;
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 )
{
double Wynik = 1;
for( unsigned int i = 1; i <= k; i++ )
{
Wynik = Wynik *( n - i + 1 ) / i;
}
return Wynik;
}
za komentowałem tylko wypisywanie wyników a dodałem wypisywanie aktualnie obliczanych indeksów dla xn dzięki temu zobaczysz, że jest wszystko ok. Program ogólnie działa tak, że tworzy macierz xn która zawiera wartości jakie może przyjąć każdy xn (wartości od 0 do x) plus tworzy tablice indeksów aktualnych xn inicjowaną zerami bo od zerowych indeksów chcemy zacząć. Przy każdej iteracji zwiększany jest indeks da x1 i jest sprawdzane czy jakiś indeks nie doszedł do wartości końcowe ( równej x), wtedy x(i+1) jest zwiększany o jeden i wszystkie xn "na lewo" od tego x(i+1) jest im ustawiana wartość indeksów taka sama jak x(i+1) po to żeby obsłużyć przypadek x1 >= x2 >= .. >= xn. |
|
osobliwy_nick Temat założony przez niniejszego użytkownika |
» 2016-03-22 19:40:33 Znalazło jakieś wyniki dla x=73, y=5, p=49667. Tylko teraz nie mogę się połapać jakie, bo program nie wypisuje całych liczb. Poza tym przerwałem mu pracę, bo to wypisywanie trwa bardzo długo.
W związku z tym jeszcze jedna prośba, bo sam pewnie nawet i tego nie zrobię:
0. Czy możesz przywrócić wypisanie zmiennych x1,x2,...,xn przy uzyskanym wyniku całkowitym. To było bardzo przydatne. I usunąć wypisywanie tych niecałkowitych przypadków, które teraz wypisuje.
1. Czy możesz dodać deklarowanie zmiennych z poziomu cmd? Typu:
podaj p:
podaj y:
podaj x:
po czym, gdy program skończy pracę, niech wypisze wynik i ponownie prosi o nowe zmienne.
2. Pod wynikami (lub brakiem wyników) fajnie byłoby wypisać liczbę "k" - policzonych kombinacji (znów tylko gwoli sprawdzenia, tak jak wcześniej).
3. Fajnie by było, gdyby program informował o postępie procentowo np. co 3 minuty - choć nie wiem czy to rozsądny czas (wszystkie kombinacje potrzebne do wykonania można policzyć ze wzoru y/(x+y) * (x+y) po y i wystarczy je porównać z dotychczasową liczbą policzonych już kombinacji), przynajmniej do dwóch cyfr po przecinku, bo w przypadku dużych liczb po prostu nie wiem czy jest sens czekać.
Wiem, że to proste rzeczy do zrobienia. Ale znów nawet tak prostych poprawek nie umiem sam jeszcze wnieść. Jakkolwiek program na pewno stanie się obiektem mojej analizy na najbliższe tygodnie, a może miesiące, aż może zrozumiem jak dokładnie działa.
EDIT:
Ad. 0 Przywróciłem wypisywanie zmiennych x1,x2,...,xn.
Ad. 2 Liczba policzonych kombinacji jest przecież nadal wypisywana - nie zauważyłem.
Część z tych wyników dla x=73, y=5, p=49667 jak poprzednio została tylko błędnie zidentyfikowana jako liczby naturalne. |
|
| 1 2 « 3 » 4 5 |