08.71.35 Uppbygging tölva

Forritunarverkefni 2


Í şessu verkefni eigiğ şiğ ağ skrifa fall í 16-bita x86 smalamáli sem útfærir svokallağa Quick-find lausn á Union-Find-verkefninu, sem şiğ ættuğ ağ kannast viğ úr Tölvunarfræği 2.

Falliğ sem şiğ skrifiğ fær í DS:SI bendi á vektorinn id, sem er óupphafsstilltur N-staka vektor af 16-bita orğum, í CX er gildiğ N, sem er fjöldi staka í id og í DX er gildiğ M, sem er fjöldi samruna (e. union) sem á ağ framkvæma. Falliğ upphafsstillir vektorinn id og uppfærir hann síğan meğ slembisamrunum. Slembitölurnar eru fengnar úr fallinu slembi, en şağ skilar 16-bita slemitölugildi sem şarf síğan ağ kvarğa, şannig ağ şağ sé á bilinu 0 til N-1.

Hér ağ neğan er útgáfa af Quick-find í C++.

	void QuickFind( int id[], int N, int M )
	{
	    int i, j, p, q;
	
	    for( i=0; i<N; i++ )
	        id[i] = i;
	
	    for( j=0; j<M; j++ ) {
	        p = slmb(N);  q = slmb(N);
	        int t = id[p];
	        if (t == id[q]) continue;
	        for( i=0; i<N; i++ )
	            if (id[i] == t) id[i] = id[q];
	    }
	}
Í forritinu er gert ráğ fyrir ağ falliğ slmb(N) skili slembitölu á bilinu 0 til N-1.

Şiğ eigiğ líka ağ skrifa ağalforrit sem skilgreinir 10000 staka vektor og kallar síğan á QuickFind meğ N=10000 og M=10000. Síğan gæti forritiğ notağ vektorinn id til ağ framkvæma Find-ağgerğir. Şiğ şurfiğ şó ekki ağ skrifa şann hluta.

Ef şiğ viljiğ ekki byrja alltaf meğ sama upphafsgildi í slembitölufallinu şá getiğ şiğ notağ ykkur ağ DOS geymir 32-bita teljara í 0040:006C, sem er hækkağur 18.2 sinnum á sekúndu.


Skiliğ útprentun fimmtudaginn 18. október.

hh (hja) hi.is, 10. október, 2001.