RAČUNALNIŠTVO

element, ki ga ta števka (bit) predstavlja. Deljenje števila r z dva in rezanjem na celi del v dvojiški predstavitvi odreže najbolj desno števko, kar omo-goca, da v vsaki iteraciji zanke preverjamo vrednost najbolj desne števke.
Algoritem 2: LexDerangPodmnoziče(n,r)
1	T = 0
2	for i = n,n - 1,..., 1 do if r mod 2 = 1 then
L T = T u {i}
r = UJ
6 return T
Algoritma za izračun naslednika ne bomo posebej zapisovali, saj lahko neposredno uporabimo zvezo med naslednikom ter rangiranjem in derangiranjem, predstavljeno s formulo (1).
Primer 4. Ta primer naredite sami. Naj bo n = 8 in T = {1, 3,4,6}. S pomočjo algoritma 1 izračunajte rang(T). Katero množico dobite, če s pomočjo algoritma 2 izračunte derang(181)?
V tem prispevku smo za našo osnovno množičo vzeli množičo S = {1,...,n}. Kaj pa, če želimo le-ksikografsko ureditev poljubne množiče A z n elementi? V tem primeru zadostuje, da poiščemo bijek-čijo f : A — S. Tako lahko poljubno podmnožičo X c A rangiramo kot
■	rang (X) = rang(f(X)).
Podobno derangiramo število r, 0 < r < 2n - 1, po naslednji formuli:
■	derang(r) = f-1 (derang(r)).
Pri tem je f-1 inverzna funkčija funkčije f, torej f(X) = Y natanko tedaj, ko je f-1 (Y) = X, kjer je X c A in Y c S.
Na začetku smo videli, da obstaja več različnih ureditev podmnožič dane množiče, leksikografska je le ena od njih. Na primeru 4 lahko opazimo tudi naslednje. Množiča {2, 3} ima rang enak 3, množiča {1} pa rang enak 4. V leksikografski ureditvi pod-množič množiče {1,2, 3} imamo torej dve zaporedni množiči, ki sta komplementarni (sta med seboj različni, kolikor se le da). Ali obstaja taka ureditev
podmnožic množice {1, 2, 3}, da se bosta dve poljubni zaporedni množici razlikovali za natanko en element? Odgovor je DA! Taka razvrstitev obstaja za poljubno množico {1, 2,...n}, kjer je n G N. Ampak to je morda zgodba za kdaj drugič. Vas pa izzivam, da najdete tako razvrstitev podmnožic množice {1, 2, 3}.
Literatura
[1] Donald L. Kreher, Douglas R. Stinson, Combinatorial algorithms: generation, enumeration, and search, CRC Press, 1999.
_ XXX
Nalogi
Marko Razpet
1.	Urejena m-teriča (x1,x2,..., xm-1,xm), v kateri so koordinate x1,x2,..., xm-1,xm naravna števila, je pitagorejska m-teriča, če velja
■x2+xi+...+xm-1 = xm
Pri tem je m > 3. Pitagorejska trojiča je na primer (3, 4, 5), ker je 32 + 42 = 52, pitagorejska četveriča pa (2, 3, 6, 7), saj je 22 + 32 + 62 = 72. Dokaži, da je za vsako naravno število n peteriča
■	(2n, 2n + 1, 2n + 2,6n2 + 6n + 2,6n2 + 6n + 3)
pitagorejska. Poišči tovrstne pitagorejske peteriče, katerih koordinate ne presegajo 100.
2.	Izračunaj
■	62 - 52, 562 - 452, 5562 - 4452, 55562 - 44452 Nato rezultate posploši na razliko kvadratov oblike
^55 . Si 62 - 44... 4 52.
n	n
XXX
28
PRESEK 45 (2017/2018) 3