Równanie na bitach
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Równanie na bitach

AutorWiadomość
Temat założony przez niniejszego użytkownika
Równanie na bitach
» 2018-06-03 14:34:51
Mam za zadanie napisać program który rozwiąże równanie x + y = x | y (gdzie znak '|' to bitowy or). Odpowiedzią do zadania jest k-te najmniejsze rozwiązanie tego rownania dla ustalonego x'a (rozwiązania liczymy od zerowego). Na wejściu mamy dwie liczby (1 <= x,k <= 10^9) Np. dla x = 5 i k = 1 odpowiedzią jest 2, a dla x = 10 i k = 3 odpowiedzią jest 5. Napisałem poniższy program, ale czas obliczania przekracza limit, który wynosi 1s. Prosiłbym o jakąś pomoc/wskazówkę jak przyspieszyć ten program.
C/C++
#include<iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );
    int x, k;
    cin >> x >> k;
    int numer_rozwiazania = 0;
    int i;
    for( i = 1; i < 2000000000; i++ )
    {
        if(( x + i ) ==( x | i ) )
        {
            numer_rozwiazania++;
            if( numer_rozwiazania == k ) break;
           
        }
       
    }
    cout << i;
    return 0;
}
P-171351
» 2018-06-03 14:53:31
Wymyśl lepszy algorytm. To jest: nie siłowy. Takie zadania są na myślenie, nie na sprawdzenie wszystkich możliwych liczb.

Podpowiedź: procesor jakoś dodaje do siebie liczby. Jak?
P-171353
Temat założony przez niniejszego użytkownika
» 2018-06-03 15:29:18
Tak właśnie myślałem, ze musi być na to jakiś sprytny sposób. Co do działania procesora to mało wiem, ale spróbuje poszukać jakichś informacji w internecie.
P-171356
Temat założony przez niniejszego użytkownika
» 2018-06-03 15:52:57
Niestety dalej, nie widzę żadnej zależności między or'em a binarnym dodawaniem. Wszystko co wymyślę sprowadza się do sprawdzania binarnej postaci kazdej liczby po kolei.
P-171357
» 2018-06-03 15:55:39
Alternatywnie możesz sobie dodać dwie liczby binarne na kartce. Bez używania dodawania. Też powinieneś zobaczyć co trzeba, jeśli będziesz patrzeć.
P-171358
Temat założony przez niniejszego użytkownika
» 2018-06-03 16:00:36
Chyba już mam. Spróboje wymyślić jeszcze jak przełozyć to na algorytm i dam znać.
P-171359
Temat założony przez niniejszego użytkownika
» 2018-06-03 17:44:36
Doszedłem do tego, ze rozwiązaniami takiego równania są wszystkie możliwe kombinacje zmian zer na jedynki, tzn. (gdy 10 to 1010 to rozwiązaniami będą 0101, 0001, 0100 oraz poprzednie liczby zwiekszone o 16). Próbowałem to zaimplementować, ale nic ciekawego z tego nie wyszło. Najpierw zamieniam liczbę na system binarny, a potem chciałbym szukać tych rozwiązań, ale nie mam pomysłu jak sie do tego zabrać.
P-171360
» 2018-06-03 17:57:30
Interesuje cię tylko k-te rozwiązanie. Koniunkcja i i x musi być zerowa, do tego już doszedłeś. k-ta kombinacja zmienionych zer na jedynki to liczba k, której bity zostały zapisane w polach, gdzie w x są zera. Do zaimplementowania tego nie potrzeba żadnych konwersji.
P-171361
« 1 » 2
 Strona 1 z 2Następna strona