Program | D.C, D.CPP, D.PAS |
Funkcijsko drevo nad mnoico spremenljivk { x1, x2, ... , xn } je polno dvojiško drevo z n+1 nivoji (tako drevo ima 2n+1 – 1 vozlišc), s katerim predstavimo Boolovo funkcijo f:{0,1}n®{0,1} na naslednji nacin: V listih drevesa (teh je ravno 2n) so shranjene vrednosti 0 in 1, vsak od prvih n nivojev drevesa pa ustreza eni od spremenljivk xi. Pri izracunu vrednosti funkcije se na vsakem nivoju odlocimo za levo ali desno poddrevo glede na to, kakšno vrednost ima spremenljivka, ki ustreza temu nivoju. Vrednost 0 pomeni levo, vrednost 1 pa desno poddrevo. Vaša naloga je pri danem drevesu in danih vrednostih spremenljivk izracunati vrednost funkcije, ki jo opisuje drevo.
Obe zgornji drevesi opisujeta funkcijo f (x1, x2, x3) = x1 Ù ( x2 Ú x3 ). Pri levem drevesu je vrstni red spremenljivk po nivojih enak x1, x2, x3, pri desnem pa je vrstni red enak x3, x1, x2.
S-Tree
#k:
", kjer je k zaporedna številka testnega primera. V naslednji
vrstici naj bodo v obliki niza m znakov 0 in 1 podane vrednosti funkcije
pri izbranih naborih vrednosti spremenljivk. Vsakemu izpisu testnega primera naj
sledi prazna vrstica.
Primer vhodnih podatkov
3
x1 x2 x3
00000111
4
000
010
111
110
3
x3 x1 x2
00010011
4
000
010
111
110
0
in pripadajoci rezultat
S-Tree #1:
0011
S-Tree #2:
0011