mateczek |
» 2016-03-21 07:28:59 jak dla mnie sam wzór na
w = (2^x1 + 2^x2 * p/2 + 2^x3 * p^2/4 + 2^x4 * p^3/8 + ... + p^xn/2^xn) * 2^(y-1)/(2^(x+y)-p^y)
// 2^(y-1)/(2^(x+y)-p^y) to jest stała można zapisać jako "C"
c= 2^(y-1)/(2^(x+y)-p^y)
//więc
w = (2^x1 + 2^x2 * p/2 + 2^x3 * p^2/4 + 2^x4 * p^3/8 + ... + p^xn/2^xn)*c
dla przykładu czwarty element ciągu podajesz jako = 2^x4 * p^3/8
podczas gdy z ogólnego wzoru wynikało by, że czwarty element ciągu = p^xn/2^xn = p^x4 / 2^x4 = (p/2)^x4
co do generowania kombinacji sprawa nie jest trywialna ale algorytmy są choćby tu:) http://stackoverflow.com/questions/9430568/generating-combinations-in-cwiększość algorytmów są dla mnie tajemnicą ale ten prawie rozumię :P #include <iostream>
#include <iterator>
#include <vector>
#include <cstdlib>
using namespace std;
struct combinations
{
typedef vector < int > combination_t;
combinations( int N, int R )
: completed( N < 1 || R > N )
, generated( 0 )
, N( N )
, R( R )
{
for( int c = 1; c <= R; ++c )
curr.push_back( c );
}
bool completed;
int generated;
combination_t next()
{
combination_t ret = curr;
completed = true;
for( int i = R - 1; i >= 0; --i )
if( curr[ i ] < N - R + i + 1 )
{
int j = curr[ i ] + 1;
while( i <= R )
curr[ i++ ] = j++;
completed = false;
++generated;
break;
}
return ret;
}
private:
int N, R;
combination_t curr;
};
int main_combinations( int argc, char ** argv )
{
int N = argc >= 2 ? atoi( argv[ 1 ] )
: 5;
int R = argc >= 3 ? atoi( argv[ 2 ] )
: 2;
combinations cs( N, R );
while( !cs.completed )
{
combinations::combination_t c = cs.next();
copy( c.begin(), c.end(), ostream_iterator < int >( cout, "," ) );
cout << endl;
}
return cs.generated;
} |
|
osobliwy_nick Temat założony przez niniejszego użytkownika |
» 2016-03-21 18:47:02 "Czy to musi być c?"
Nie musi być, jeżeli będzie działać. Po prostu zupełnie nie znam C++, choć wiem, że jest podobny do C.
"Akurat dla danych które podałeś to 5 przykład daje liczbę naturalną."
Rzeczywiście dokładnie 6 przykład. Zapomniałem o tych przypadkach. Te przypadki rozwiązań można uznać za trywialne i bardzo łatwo je znaleźć. Liczbę 1 uzyskamy zawsze w jednym z przypadków, gdy przyjmiemy x=y.
w = (4 + 2*3/2 + 9/4)*2^2/(2^6-3^3) = 1
"Coś tam naskrobałem (z tym, że w C++)"
Próbowałem to skompilować w Dev, ale mi się nie udało. Nie jestem w stanie zweryfikować po samym kodzie, czy program może być poprawny (po poprawieniu błędów, na które natknął się kompilator).
"jak dla mnie sam wzór
w = (2^x1 + 2^x2 * p/2 + 2^x3 * p^2/4 + 2^x4 * p^3/8 + ... + p^xn/2^xn) * 2^(y-1)/(2^(x+y)-p^y)
// 2^(y-1)/(2^(x+y)-p^y) to jest stała można zapisać jako "C"
c= 2^(y-1)/(2^(x+y)-p^y)
//więc
w = (2^x1 + 2^x2 * p/2 + 2^x3 * p^2/4 + 2^x4 * p^3/8 + ... + p^xn/2^xn)*c"
Zgadza się. Po zadeklarowaniu x, y i p część wzoru oznaczona jako c jest stała.
"dla przykładu czwarty element ciągu podajesz jako = 2^x4 * p^3/8
podczas gdy z ogólnego wzoru wynikało by, że czwarty element ciągu = p^xn/2^xn = p^x4 / 2^x4 = (p/2)^x4"
Faktycznie był błąd we wzorze (jak mogłem tego nie zauważyć!). Już poprawiłem. Wzór ma wyglądać tak:
w = (2^x1 + 2^x2 * p/2 + 2^x3 * p^2/4 + 2^x4 * p^3/8 + ... + p^(y-1)/2^(y-1)) * 2^(y-1)/(2^(x+y)-p^y)
Dla uproszczenia pomijając "c" mamy:
1 + p^1/2^1 + p^2/2^2 + p^3/2^3 + ... + p^(y-1)/2^(y-1)
i teraz mnożymy wszystkie składniki, poza ostatnim razy kolejne 2^x1, 2^x2, 2^xn
w = (2^x1 + 2^x2 * p^1/2^1 + 2^x3 * p^3/2^3 + ... + p^(y-1)/2^(y-1)) * c
"co do generowania kombinacji sprawa nie jest trywialna ale algorytmy są choćby tu"
Ok. Sądziłem, że generowanie tych kombinacji będzie prostsze.
PS Chciałbym sprawdzić między innymi przypadek p=3, x=55, y=94. Generuje to ok. 1,38*10^41 liczb do sprawdzenia (ich całkowitości), które są wielkości od około 106 do 3,8*10^18. To wykonalne dla domowego laptopa i współczesnych komputerów w rozsądnym czasie? |
|
michal11 |
» 2016-03-21 18:57:49 #include <iostream>
using namespace std;
#include <conio.h>
#include <string>
#include <vector>
#include <cmath>
double computeW( int pX, int pY, int pP, const vector < vector < int >>& pXn, const vector < int >& pXIndxs );
bool isNaturalNum( double value );
unsigned long long newton( unsigned int n, unsigned int k );
int main()
{
int x = 3;
int y = 3;
int p = 3;
vector < vector < int >> xn( y - 1, vector < int >( x ) );
for( auto & vec: xn )
{
for( int i = 0; i <= x; ++i )
{
vec[ i ] = i;
}
}
vector < int > xIndxs( xn.size(), 0 );
double w;
unsigned long long howMany = newton( x + y, y ) / 2;
for( unsigned long long k = 0; k < howMany; ++k )
{
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 )
{
if( j == xIndxs.size() ) { break; }
++xIndxs[ j + 1 ];
for( int pom = j; pom >= 0; --pom )
{
xIndxs[ pom ] = xIndxs[ j + 1 ];
}
break;
}
}
}
cout << "Koniec" << 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 )
{
int intPart = value;
double rest = value - intPart;
return rest == 0;
}
unsigned long long 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( unsigned long long ) Wynik;
}
Ok, poprawiłem wzór, jest tylko jeden błąd isNaturalNum() zwraca czy liczba jest całkowita a nie naturalna, ale to można łatwo poprawić. Jakie błędy ci wyskakują w dev ? Pewnie coś o c++11. Program dla poprzednich danych (poprzedniego wzoru) na pewno działał dobrze (takie same wyniki cząstkowe jak podałeś), wklej dokładne błady które dostajesz to ci pomogę skompilować. |
|
osobliwy_nick Temat założony przez niniejszego użytkownika |
» 2016-03-21 19:05:26 double computeW( int pX, int pY, int pP, const vector < vector < int >>& pXn, const vector < int >& pXIndxs );
[Error] '>>' should be '> >' within a nested template argument list
vector < vector < int >> xn( y - 1, vector < int >( x ) );
[Error] '>>' should be '> >' within a nested template argument list
for( auto & vec: xn )
[Error] range-based 'for' loops are not allowed in C++98 mode
vec[ i ] = i;
[Error] invalid types 'int[int]' for array subscript
PS Jeżeli program działa prawidłowo powinien znajdować trywialne rozwiązania dla x=y oraz p=3 (wynik 1). Ponadto powinien znaleźć 4 liczby dla x=13, y=2 oraz p=181. To tak w ramach testu warto sprawdzić. |
|
mateczek |
» 2016-03-21 19:17:09 | Ok. Sądziłem, że generowanie tych kombinacji będzie prostsze. |
Jest nawet trywialna jeśli chcesz wygenerować trójki (można trywialnie 3 fory zastosować) w przypadku nieznanych wartości trzeba posłużyć się bardziej wymyślnymi sposobami. kombinacje 3 z 10 na 3 forach :) sposób nie przejdzie dla nieznanych wartości niestety #include <iostream>
using namespace std;
int main() {
for( int i = 0; i < 10; i++ ) {
for( int k = i + 1; k < 10; k++ ) {
for( int j = k + 1; j < 10; j++ ) {
cout << i << " " << k << " " << j << " " << endl;
}
}
}
}
|
|
michal11 |
» 2016-03-21 19:25:42 Włącz c++11 w opcjach kompilatora, na pasku wejdź w Narzędzia >> Opcje kompilatora >> Wytwarzanie/optymalizacja kodu >> Wytwarzanie kodu >> Language standard ustaw na ISO C++11. Powinno się kompilować.
Dla danych x = 55; y = 94; p = 3; po ok 10 minutach (procesor 3,4GH) nie wykonał się nawet 1%, inna sprawa, że nie optymalizowałem tego programu, użyłem typu doble do pomieszczenia dużych liczb (lepszy pewnie byłby jakiś bigint) itp. rzeczy.
Może, ale podkreślam może, da się ten algorytm tak zmodyfikować żeby wykonywał się na wielu wątkach, wtedy wzrost wydajności byłby proporcjonalny do ilości wątków, niestety ale mój algorytm raczej tak nie zadziała.
Zaraz sprawdzę dla mniejszych danych.
@mateczek
Właśnie ja zrobiłem takie dynamiczne "generowanie pętli". |
|
osobliwy_nick Temat założony przez niniejszego użytkownika |
» 2016-03-21 19:30:32 Mateczek rozumiem. Niestety chodzi o kombinacje y-elementowe utworzone ze zbioru (x+y)-elementowego, których ilość określa dwumian newtona - (x+y) po y. A dokładnie chodzi o połowę z tych kombinacji - z uwagi na warunek x1 >= x2 >= ... >= xn. Ogólnie kosztem wydajności programu można by nawet wyrzucić ten warunek, ale nie dość, że przysporzyłoby to sprawdzenia 2 razy większej ilości liczb, to dodatkowo do sprawdzenia wpadłyby te największe liczby. |
|
osobliwy_nick Temat założony przez niniejszego użytkownika |
» 2016-03-21 19:43:17 Michal11 - sprawdziłem p=181 i działa prawidłowo.
Spróbowałem p=49667, y=5 oraz x=78 i się zawiesił. W ogóle dla większych parametrów się zawiesza. Natomiast dla p=3, y=94 i x=55 kończy pracę w ułamek sekundy po włączeniu (chyba nie mógł tego tak szybko policzyć?).
|
|
| 1 « 2 » 3 4 5 |