Jakie liczby zostały użyte?

Question

Witam, mam następujący ciąg liczb:

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 ... 262144

Ogólnie 2^n gdzie n zawiera się w przedziale 0 - 18

 

Weźmy teraz dowolne liczby z tego przedziału np.  2, 8, 128, 512

Dodajmy je: 2+8+128+512 = 650

 

Moim zadaniem jest napisanie programu który po podaniu mu tej liczby tj. 650

zwróci mi z jakich liczb została ona stworzona tzn. zwróci mi: 512, 128, 8, 2

 

Na samym początku wyznaczam największą możliwą do uzyskania liczbę w naszym przypadku to będzie 512 bo 1024 jest już większe niż 650.

Sprawdzam ją w taki sposób:

    int liczba;
    int max_ilosc_wartosci_w_ciagu = 18;

    cout << "Podaj liczbe: ";
    cin >> liczba;
    cout << endl << "Z tych liczb mozesz utworzyc: " << liczba << endl;


    for (int i=max_ilosc_wartosci_w_ciagu; i>=0; i--){
        if ((liczba-(1<<i)) > 0){
            cout << (1<<i)<< endl;
        }
    }

 

I na tym moje pomysły się kończą.

 

 

 

 

 

 

Answer 1

Nie wiem czy przypadkiem sma sobie nie odpowiedziałeś. Po prostu szukasz największej potęgi 2 mniejszej lub równej aktualnej liczie.
Np. masz to 650. Najwiekszą, mniejsza od 650 potęga 2 to 512. Teraz odejmujesz 512 od 650 i to samo robisz z otrzymaną liczbą. Powtarzasz to, aż suma znalezionych potęg nie wyniesie 650.

Comments

Zauważ też, że w taki sam sposób są zapisywane liczby binarne :P Mozesz tez ten fakt wykorzystać, bardzo możliwe, że w ten sposób program byłby wydajniejszy...

Answer 2

#include <iostream>
#include <cmath>

int main()
{
    long long int liczba;
    int wykladnik = 0;
    std::cin >> liczba;
    while(liczba > 0)
    {
        if(pow(2, wykladnik) > liczba)
        {
            std::cout << pow(2, wykladnik - 1) << " ";
            liczba -= pow(2, wykladnik - 1);
            wykladnik = 0;
        }
        else
            wykladnik++;
    }
    return 0;
}

Program opiera się na pętli, w której sprawdzamy, która potęga o podstawie 2 jest większa od naszej liczby (albo od tego, co zostało po odejmowaniu). Jeśli ją znajdziemy, to odejmujemy 2 ^ wykladnik - 1 (dlatego odejmujemy jedynkę, ponieważ 2 ^ wykladnik przewyższa liczbę) od naszej liczby i sprawdzamy to samo dla reszty, która została, aż nie dojdziemy do sytuacji, gdy liczba = 0.

Comments

Dzięki wielkie o to właśnie chodziło. Aż wstyd że na to nie wpadłem blokada jakaś czy cos :D Dzięki jeszcze raz