8086-spyrnan 2001

Hin árlega hrağaksturkeppni 8086 forrita



Hin árlega keppni nemenda í Uppbyggingu tölva í ağ skrifa hrağvirk 8086 smalamálsforrit er nú ağ hefjast. Ağ şessu sinni er tengist verkefniğ hinu sígilda reikniritaverkefni Union-Find. Verkefniğ er fólgiğ í şví ağ framkvæma tiltekinn fjölda samrunaağgerğa (Union) á mengi til ağ undirbúa leitun ağ stökum í menginu (Find). Nánari lısing á ağferğinni er á Verkefnablaği 2 í Uppbyggingu tölva.

Falliğ ykkar fær sem inntak bendi á 16-bita vektorinn id í DS:SI. Fjöldi staka í vektornum er 32000 og şağ gildi kemur sem viğfang í CX. Şiğ megiğ şó gera ráğ fyrir şví í ykkar kóda ağ vektorinn hafi 32000 stök. Sömuleiğis er fjöldi samruna 32000 og sú tala kemur niğur í falliğ í gistinu DX. Falliğ má ekki hafa breytt neinum gistum şegar şví er lokiğ. Í ağfalforritinu, sem ykkur verğur gefiğ er 32-bita upphafsgildi slembitölugjafa lesiğ úr skránni SAEDI.DAT. Einnig er gefiğ falliğ slmb(N) sem skilar slembitölu á bilinu 0 til N-1. Şiğ verğiğ ağ nota şetta fall til ağ fá slembitölur í keppnisfallinu ykkar. Şağ má ekki breyta ağalstefinu eğa slembitölugjöfunum.

Quick-find er ekki besta ağferğin fyrir Union-Find verkefniğ, en í şessari keppni veriğ şiğ ağ nota şá ağferğ. Şağ má ekki nota hinar ağferğirnar sem skoğağar voru í Tölvunarfræği 2, svo sem Quick-union, viktuğu útgáfuna af Quick-union eğa path-compression útgáfuna.


Reglur:

  1. Öll dırin í skóginum skulu vera vinir. Ekkert dır má éta annağ dır.
  2. Falliğ ykkar má ekki breyta neinum gistum. Ekki má breyta gefna ağalforritinu nema til ağ skilgreina víğvær minnissvæği. Ağeins má nota 8086 skipanir í forritinu.
  3. Öll vinnan viğ samruna stakana í vektornum verğur ağ vera samkvæmt Quick-find ağferğinni.
  4. Keppnisstjóri er Hjálmtır Hafsteinsson og sér hann um ağ taka tímann á forritunum, sem keyrğ verğa á Pentium II tölvu í nemendaveri tölvunafræğiskorar. Einnig úrskurğar hann um vafaatriği.
  5. Allir nemendur í Uppbygging tölva haustiğ 2001 mega taka şátt í keppninni, en ağrir tölvunarfræğinemar geta einnig tekiğ şátt sem gestir, en şeir geta şó ekki sigrağ í keppninni.
  6. Sigurvegari keppninnar telst sá sem samdi forritiğ sem tekur stystan tíma og hlıtur hann (hún) ağdáun íturvaxinna kvenna (karla).


Tímamælingin fer fram í tölvuveri tölvunarfræğinema í kjallara Tæknigarğs 2 fimmtudaginn 25. október kl. 15:00. Allir sem áhuga hafa eru boğnir velkomnir.

hh@hi.is, október, 2001.