Naloga D: Funkcijska drevesa

 

Program D.C, D.CPP, D.PAS

Funkcijsko drevo nad množico 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.

Vhod

Vhod je sestavljen iz zaporedja testnih primerov. Vsak testni primer se zacne s številom spremenljivk n (1 £ n £ 7) v svoji vrstici. Temu v naslednji vrstici sledi zaporedje spremenljivk xi1 xi2 ... xin, , kot si sledijo po nivojih (cleni zaporedja so zapisani kot znak x, ki mu sledi številka spremenljivke, med seboj pa so loceni s presledki). Temu v naslednji vrstici sledi niz 2n znakov 0 in 1. Ti znaki predstavljajo vrednosti v listih funkcijskega drevesa, naštete od leve proti desni. V naslednji vrstici je število vprašanj m >=0. Sledi m vrstic, vsaka od njih pa vsebuje zaporedje n znakov 0 in 1. Te vrstice predstavljajo vrednosti spremenljivk, pri katerih je treba izracunati vrednost funkcije, ki jo predstavlja funkcijsko drevo. Pri tem prvi znak pomeni vrednost spremenljivke x1, drugi vrednost spremenljivke x2, ... , zadnji pa vrednost spremenljivke xm. Konec poda­t­kov oznacuje testni primer z n = 0.

Izhod

Za vsak testni primer je treba v svoji vrstici izpisati besedilo "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