Rozkład liczby na sumę dwóch kwadratów
Logowanie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zapomniałem hasła
» Forum » Programowanie » [C, C++] Szukam pomocy

Rozkład liczby na sumę dwóch kwadratów

Ostatnio zmodyfikowano 2018-02-10 21:29
Autor Wiadomość
Abigail
Temat założony przez niniejszego użytkownika
Rozkład liczby na sumę dwóch kwadratów
» 2018-02-08 21:07:32
Mam za zadanie rozłożyć wprowadzoną na wejściu liczbę całkowitą dodatnią na sumę kwadratów dwóch liczb całkowitych dodatnich. Mam na razie takie, błędne rozwiązanie:
C/C++
int rozklad( const int n )
{
    int a = 0, b = n, sum;
    for( a; a < n; a++ ) {
       
        for( b; b > 0; b-- ) {
            int bt = pow( 2, b );
            int at = pow( 2, a );
            sum = at + bt;
            if( sum == n )
                 cout << sum;
           
        }
       
    }
   
    return 0;
}[ \c pp ]

Jednak wyglada na to, ze ono nie ma wiele sensu. Jak to poprawic,zeby działało?
P-169328
darko202
» 2018-02-09 09:54:55
1.
czytając problem wydało mi sie, że nie każda liczba naturalna ma rozkład na sumę kwadratów dwóch innych liczb
np. 23
znalazłem na to potwierdzenie na google + "Rozkład liczby na sumę dwóch kwadratów algorytm"
https://www.google.pl/search​?source=hp​&ei=WlF9WorFO4uzkwWAyY-4Bw​&q=Rozk%C5%82ad+liczby+na+sum%​C4%99+dw%C3%B3ch+kwadrat%C3%B3​w+algorytm​&oq=Rozk%C5%82ad+liczby+na+sum​%C4%99+dw%C3%B3ch+kwadrat%C3%B​3w+algorytm​&gs_l=psy-ab.3..33i160k1l2.2701.8515.0.8975.10.10.0.0.0.0.383.1114.7j2j0j1.10.0....0...1c.1.64.psy-ab..0.10.1109...0i22i30k1j33i21k1.0.J0hKeC2TYKo

pierwszy link "Twierdzenie Waringa"
"Liczbę n ∈ N możemy przedstawić w postaci sumy dwóch kwadratów liczb całkowitych wtedy i tylko wtedy jeżeli ..."
potwierdza to moje podejrzenie
kolejne linki też poruszają ten problem - poszukaj pewnie jest i algorytm

2.
> Jak to poprawic ?
 
weźmy dobry przykład : N= 25 = 16 + 9
widać z niego że wystarczy badać liczby w zakresie <1, pierwiastek(N) >
ograniczy to złożoność obliczeniową algorytmu

weźmy zły przykład :   N= 23  -> nie ma rozkładu
* sprawdzamy wszystkie możliwości -> nie ma rozwiązania -> wyrzucamy komunikat o braku takiego rozkładu

3.
aby było to elegancko to wykorzystałbym to "Twierdzenie Waringa"
w realizowanym algorytmie :

* Jezeli n, N 2 N i zachodzi n | N2 + 1, to istnieja liczby s, t 2 Z,
ze n = s2 + t2 (warunek dostateczny).
* Jezeli n jest liczba pierwsza postaci n = p = 4k + 1, to istnieja
liczby s, t 2 Z, ze n = s2 + t2 (warunek dostateczny).
* Liczbe n 2 N mozemy przedstawic w postaci sumy dwóch
kwadratów liczb całkowitych wtedy i tylko wtedy jezeli w jej
rozkładzie kanonicznym wszystkie podstawy pierwsze postaci
4k + 3 wystepuja w potegach parzystych (sa kwadratami).
Jest to warunek konieczny i dostateczny


P-169341
Abigail
Temat założony przez niniejszego użytkownika
» 2018-02-10 19:39:25
No tak... Chociaż przed przeczytaniem Twojej odpowiedzi udało mi się wymyślić niedokończoną i prawie dobrze działającą wersję. Wezmę pod uwagę też to, co napisałeś, darko 202, to zresztą chyba lepsze rozwiązanie. Dla lepszego porównania, mógłby ktoś skomentować poniższy kod?
C/C++
int rozklad( int n )
{
    int x = sqrt( n );
    int y = sqrt( n );
    for( x; x >= 0; x-- )
    {
        while( y != 0 )
        {
            y--;
            if( pw( 2, y ) + pw( 2, x ) == n )
                 cout << y << "+" << x << endl; //Poprawić, wersja testowa
           
        }
        if( x != 0 )
             y = sqrt( n );
       
    }
    return 0;
}[ cpp\]
P-169364
mateczek
» 2018-02-10 21:29:01
C/C++
#include <iostream>
#include<cmath>
using namespace std;

//funkcja sprawdzająca czy pierwiastek jest całkowity
bool calkowityPierwiastek( int liczba ) {
    double a = sqrt( liczba );
    int b = a;
    return b == a;
}
int main() {
    int liczba = 26;
    for( int i = 0; i <= liczba; i++ ) { //i<=liczba/2 // dla optymalizacji
        //rozbijam liczbę na dwie częśći "i" oraz "liczba-i" i sprawdzam czy ich pierwiastki są liczbami całkowitymi ??
        if( calkowityPierwiastek( i ) && calkowityPierwiastek( liczba - i ) ) {
            cout << i << " " << liczba - i << endl;
        }
    }
}
P-169366
« 1 »
  Strona 1 z 1  
» Forum » Programowanie » [C, C++] Szukam pomocy
© Wszelkie prawa zastrzeżone 2005-2024