Przedstawienie liczby jako sumy ujemnych i dodatnich potęg 2.

Cześć,

Muszę napisać program, który dla zadanej liczby N sprawdza czy da się ją przedstawić
jako sumę wybranych elementów ze zbioru S1 bez powtarzania. A następnie czy dla się
wykonać to samo dla zbioru S2. N jest rzędu 10^30.

S1 = {1, -2, 4, -8, 16, -32, 64, -128, ...}
S2 = {-1, 2, -4, 8, -16, 32, -64, 128, ...}

np:
N = 7 mamy S1: 7 = 1 + (-2) + (-8) + 16
                   S2: 7 = (-1) + 8

Dziękuję za pomysły,
Pozdrawiam

Algorytm ma tylko zwrócić bool: da się|nie da się?
Podpowiedz: znajdź liczby których nie dasz rady przedstawić w ten sposób. Tak na kartce, bez algorytmu.

Ma wypisać indeksy z tych 2 tablic S1 i S2 jeśli się da. Jeśli nie to jakiś komunikat.

@Delor: Możesz podać jakiś przykład dla którego nie działa? Bo tak na szybko nie mogę znaleŹć nic.

Zrób sobie tabelę np:

i tak wpisuj kolejne liczby aż znajdziesz prawidłowość.
Dla ujemnych liczb podobnie.

Faktycznie kolumny się powtarzają ale nie do końca wiem jak mając daną liczbę znaleźć jej odpowiednik w tabeli.

Ok. To teraz widzisz jak możesz te wartości przedstawić jak bity. 1/0 w zależności od tego które dodajesz a które nie.
Jeden bit to zakres [0; 1]
Dwa bity to zakres [-2; 1]
Trzy bity: [-2; 5]
Cztery bity: [-10; 5]
Itd.
I dalej to podobnie jak przy zamianie liczby dziesiętnej na binarną (z tą różnicą że tam zwiększałeś zakres tylko w jedną stronę a tutaj w obie).
Jak kolejne zwiększenie zakresu obejmie liczbę to "zapalasz" odpowiedni bit i odejmujesz odpowiadającą mu wartość od liczby. I tak do końca aż uzyskasz zero.

Czyli łopatologicznie przykład dla liczby 6.
6 jest dodatnie więc sumujesz dodatnie wartości: 1 + 4 + 16 = 21
6 - 16 = -10
-10 jest ujemne więc: (-2) + (-8) = -10
(-10) - (-8) = -2
-2 jest ujemne: (-2) = -2
(-2) - (-2) = 0

No tak, dzięki wielkie. Problem tylko jeszcze z reprezentacją liczby bo jest rzędu 10^30 tak samo z sumowaniem potęg. Mógłbym użyć ewentualnie bignumów chyba że masz jakiś inny pomysł na to?

Potrzebujesz czegoś co zmieści 2^100. Wybierz coś w zależności od języka.
Polecam pythona gdzie bignuma masz "z automatu".

Problem ogólny nazywa się SubsetSum i jest NP-zupełny ;) https://en.wikipedia.org/wiki/Subset_sum_problem Ale że masz potęgi 2 i nic się nie powtarza, to można faktycznie trywialnie rozłożyć wejściową liczbę na bity. Nie wiem tylko gdzie jest problem z rozmiarem liczb skoro mozesz zrobić tu zwykłą tablicę bitów i tyle. Nie trzeba żadnego bignuma tutaj robić. Robimy np. tak:

    S1 = [1, 2, 8, 16, 64, 128]
    set_bits = {int(math.log(x, 2)) for x in S1}

i cyk, mamy informacje które bity są dla nas "dostepne". Teraz wystarczy rozłożyć N na bity i sprawdzać czy jeśli i-ty bit N jest 1 to czy mamy i w zbiorze set_bits.

Przykład:

import math


def main():
    N = 6
    S1 = [1, 2, 8, 16, 64, 128]
    set_bits = {int(math.log(x, 2)) for x in S1}
    bits = []
    while N != 0:
        bits.append(N % 2)
        N /= 2
    result = []
    for index, bit in enumerate(bits):
        if index not in set_bits:
            print("Nie da sie, brakuje nam %d" % 2 ** index)
            result = None
        else:
            result.append(2 ** index)
    if result:
        print("Rozwiazanie: %s" % result)


main()

Żadnych bignumów ani innych cudów :)