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ść
osobliwy_nick
Temat założony przez niniejszego użytkownika
Policzenie wszystkich kombinacji liczby danej wzorem
» 2016-03-19 21:02:10
Witam. Od jakiegoś czasu zajmuję się problemami związanymi z problemem Collatza. Po drodze natrafiłem na konieczność wypisywania oraz sprawdzania właściwości liczb zadanych poniższym wzorem, stąd moja obecność tutaj.

Jak napisać program, będzie liczył czy wśród liczb postaci:

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)

są liczby naturalne?

przy czym wykładniki muszą spełniać warunki:
x1, x2, x3, ..., xn należą do liczb [0,x]
oraz
x1 >= x2 >= x3 >= ... xn

do tego n=y-1, czyli wykładników xn jest dokładnie y-1.

Liczby p, x, y mają być dane z góry. Program musi sprawdzić - policzyć wszystkie liczby w, które zadaje wzór. Do tego celu trzeba "wypisać" wszystkie kombinacje x1, x2, x3, ..., xn, zgodnie z podanymi warunkami (ilość tych kombinacji można policzyć z dwumianu Newtona, będzie ich (x+y) po y), a następnie "wstawić" je do wzoru i sprawdzać czy wynik jest całkowity/naturalny.

Utknąłem już na prostym przypadku y=5, gdy próbowałem policzyć wyniki dla zmiennej x1 i dla pozostałych przyjętych tymczasowo jako x_k=0. Nawet dla tego prostego przypadku program mi nie działa. Czy ktoś jest w stanie napisać uniwersalny kod dla ogólnego przypadku?
P-146244
mateczek
» 2016-03-19 21:50:03
zbyt wiele niejasności może znacząć od kawałka kodu

C/C++
#include<iostream>
#include<cmath>
using namespace std;

int main() {
    int x, p;
    cout << "podaj x i p" << endl;
    cin >> x >> p;
    int suma = 0;
    for( int xn = 0; xn <= x; xn++ ) {
        cout << xn << " ";
        suma += pow( p, xn ) / pow( 2, xn ); // czy elementy dzielenia mają być liczbami rzeczywistymi
        //(p^xn)/(2^xn) czy to wzór określa n-ty element ciągu??
    }
    cout << endl;
    cout << suma << endl;
   
}
P-146247
osobliwy_nick
Temat założony przez niniejszego użytkownika
» 2016-03-20 20:49:17
A co jest niejasne?

Może podam przykład, który ułatwi zrozumienie samego wzoru. Weźmy x=3, y=3 oraz p=3. Wstępnie mamy wzór:

(1 + 3/2 + 9/4)*2^2/(2^6-3^3)

mamy y-1 iksów; x1, x2 należą do liczb z przedziału od 0 do 2. Możemy utworzyć różne w:

w = ((1 + 3/2 + 9/4)*2^2)/(2^6-3^3) = 19/37

w = (2 + 3/2 + 9/4)*2^2/(2^6-3^3) = 23/37

w = (4 + 3/2 + 9/4)*2^2/(2^6-3^3) = 31/37

w = (8 + 3/2 + 9/4)*2^2/(2^6-3^3) = 47/37

w = (2 + 2*3/2 + 9/4)*2^2/(2^6-3^3)

w = (4 + 2*3/2 + 9/4)*2^2/(2^6-3^3)

w = (8 + 2*3/2 + 9/4)*2^2/(2^6-3^3)

w = (4 + 4*3/2 + 9/4)*2^2/(2^6-3^3)

w = (8 + 4*3/2 + 9/4)*2^2/(2^6-3^3)

w = (8 + 8*3/2 + 9/4)*2^2/(2^6-3^3) = 89/37

Ogólnie gdyby, nie warunek, że x1 >= x2 mielibyśmy (x+y) po y kombinacji (czyli 20), ale z uwagi na ten warunek jest ich o połowę mniej. Żadna z tych liczb nie jest liczbą całkowitą, naturalną. I niezwykle trudno takie znaleźć, dla dowolnie zadanych zmiennych. Jakkolwiek podejrzewam, że dla pewnych szczególnych parametrów te rozwiązania mogą się pojawiać. Analiza ma na celu między innymi zidentyfikowanie liczb Crandalla, które nie są liczbami Wieferich.


P-146302
michal11
» 2016-03-20 21:14:21
Co znaczy, że program nie działa dla y=5 ?
Masz już zaprogramowane generowanie tych liczb ? Jeżeli tak to wklej kod.
Nie wiesz jak sprawdzić czy wylosowana liczba jest naturalna ?
Z czym dokładnie masz problem ?
P-146308
osobliwy_nick
Temat założony przez niniejszego użytkownika
» 2016-03-20 21:32:06
1. Nigdy nie programowałem w C++. Jeżeli mam to zrobić muszę dokształcić się ze składni.

2. Napisałem program w c:

#include<stdio.h>
#include<math.h>

/*Crandall*/


int main(void)

{

long long int p;
double w;

long long int a;

long long int b;

long long int c;

long long int d;

for(;;)
{
a=0;
b=0;
c=0;
d=0;
printf("podaj liczbe: ");
scanf("%lld",&p);

for(a = 0;a < 33; a++)
{

w = (2^a+2^b*(97^1)/2+2^c*97^2/4+2^d*97^3/8+97^4/16)*4/(2^33-97^5);



if(floor(w)==w)
{
printf("                              CRANDALL\n");
}
else
{
printf("w\n");
}
}
}
return(0);

}

Właściwie, to nie wiem nawet jak wypisać wynik, jako liczbę po przecinku (bo chyba nie printf("w\n"). Muszę poszukać. W wyrażeniu muszę zmienić także zapis potęg na "pow". W każdym razie, ta wersja programu nie policzy mi wszystkich kombinacji, nie ma tu nawet określonego ogólnego przypadku wzoru dla dowolnych x i y. Zatem mam dwa problemy:

a) jak powiedzieć programowi jaki wzór ma liczyć (bo ilość składników sumy jest zmienna i zależy od podanego y). Trzeba do tego pewnie jakąś pętle na "budowanie tego wzoru".
b) gdy już wzór będzie utworzony program ma w miejsce zmiennych x1,x2,...,xn zacząć wstawiać wszystkie możliwe kombinacje, co też nie wiem jak zrobić. Ogólnie powinien zacząć np. od przyjęcia wszystkich x=0, później pierwsze x=1, pozostałe 0, następnie x1=1, x2=1, pozostałe 0. Później x1=1, x2=1, x3=1,... Aż do x1=2, pozostałe 0. Itd. Nie wie jak to zadeklarować, pewnie potrzeba będzie tu podwójnej pętli for, a może nie. Nie mam pomysłu.
P-146310
carlosmay
» 2016-03-20 21:43:18
Nigdy nie programowałem w C++.
Właściwie to co piszesz to jest C, nie C++.
P-146311
osobliwy_nick
Temat założony przez niniejszego użytkownika
» 2016-03-20 21:46:35
No tak. Pisałem proste programy tylko w C.

Dodam jeszcze, że sprawa jest dla mnie na tyle istotna (a jednocześnie odpowiednie dokształcenie się w zakresie programowania wydaje mi się perspektywą tak odległą), że chętnie zleciłbym komuś napisanie takiego programu w c. Może możecie polecić jakąś firmę lub osobę? Taki program nie powinien kosztować chyba więcej niż 100zł? Myślę, że godzinka u jakiegoś korepetytora rozwiąże problem.
P-146312
michal11
» 2016-03-21 01:33:42
Czy to musi być c ?

Akurat dla danych które podałeś to 5 przykład daje liczbę naturalną.

Coś tam naskrobałem (z tym, że w C++):
C/C++
#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, lastPow ) / pow( 2, lastPow );
    retVal *= pow( 2, 2 );
    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; // Obliczanie ze wzoru iteracyjnego
    }
   
    return( unsigned long long ) Wynik;
}

Niektóre zmienne są nazwane bez sensu(chociaż część poprawiłem), niektóre rzeczy mogły by zostać zrobione lepiej, ale przynajmniej działa i nie chce mi się już dzisiaj nad tym siedzieć. Mam nadzieję, że się przyda.
P-146322
« 1 » 2 3 4 5
  Strona 1 z 5 Następna strona