Domácí úkol 2

Naprogramujte funkci

void report(int p[], int n, int lb, int ub)

Kde p je pole celých čísel, n je jeho velikost, lb je dolní hranice a ub je horní hranice součtu (viz dále).

Funkce vypíše všechny neprázdné množiny X indexů (platných pro pole p) takové, že pokud sečteme hodnoty prvků pole p na indexech z X, dostaneme hodnotu alespoň lb a současně nejvýše ub.

Příklad

p  = {1,5,6,-1,1},
n  = 5,
lb = 2,
ub = 5

Funkce vytiskne například
{0,4}      protože p[0]+p[4] == 2 a máme lb <= 2 <= ub,
{1}        protože p[1] == 5, a máme lb <= 5 <= ub,

(Pozn. funkce vypíše i další množiny, předchozí dvě jsou pouze příklad.)

Ke generování množin indexů použijte reprezentaci množiny pomocí celého čísla. K práci s množinami pak použijte bitové operátory (viz obsah semináře a nápověda níže). Můžete předpokládat, že maximální velikost pole je nejvýše počet bitů v typu int zmenšený o jedna. Doporučuji testovat pro malá pole, pro větší pole může program běžet dlouho.

Nápověda

Bitové operátory (příklady na 4 bitových číslech)

&      bitova konjunkce,  1001 & 0101 = 0001
|      bitova disjunkce,  1001 | 0101 = 1101
<<     bitovy posuv,      1001 << 1 = 0010, 1001 << 2 = 0100, 1001 << 3 = 1000

Test toho, jestli je bit na indexu i v čísle a roven 1

a & (1 << i)   //  i-ty bit je 1 právě když je výsledek nenulový

Dále je pro nás zajímavá následující tabulka (zde pro 3 bitová čísla, pro větší počty bitů je situace analogická).

   cislo | binarne  | bity nastavene na 1
   --------------------------------------
     0   |   000    |
     1   |   001    |    0
     2   |   010    |    1
     3   |   011    |    0,1
     4   |   100    |    2
     5   |   101    |    0,2
     6   |   110    |    1,2
     7   |   111    |    0,1,2
   ---------------------------------------

Není náhoda, že tabulka má 8 řádků, zápis čísla 8 ve dvojkové soustavě je 1000.