Tölvunarfræği 2

Vikublağ 10


Í şessari viku fjöllum viğ um Shell röğun úr kafla 6.6, en síğan verğur byrjağ á Quicksort, sem er í kafla 7.

Í dæmatímum verğur rætt um síğustu heimadæmi.

Heimadæmi 9

Leysiğ eftirfarandi dæmi og skiliğ í hólf dæmatímakennara ykkar fyrir kl 12:00 mánudaginn 21. mars. Şeir taka ekki dæmum sem koma seinna.

  1. [Próf 2004] Gefinn er eintengdur listi, şar sem hver hnútur inniheldur heiltölu. Skrifa á endurkvæmt fall í C++ til ağ reikna summu kvağrata, ş.e. (a1)2 + (a2)2 + ... + (an)2 , şar sem ai er talan í hnúti i í tengda listanum.
    1. Skoğiğ föllin hér ağ neğan og segiğ til um hvers vegna şau leysa ekki şetta verkefni. Útskıriğ vandamáliğ í hverju tilfelli og segiğ hvağ muni gerast ef föllin væru keyrğ.
      i)
      	int sumKvrt( node *h )
      	{
      		if( h != NULL )
      			return ( sumKvrt( h->next ) * sumKvrt( h->next ) );
      	}
      
      ii)
      	int sumKvrt( node *h )
      	{
      		if( h == NULL )
      			return 0;
      		return ( h->item * sumKvrt( h->next ) );
      	}
      
      iii)
      	int sumKvrt( node *h )
      	{
      		return 0;
      		if( h->next != NULL )
      			return ( h->item * h->item ) + sumKvrt( h->next );
      	}
      
    2. Skrifiğ rétta endurkvæma útgáfu af şessu falli og útskıriğ hvernig ykkar fall leysir verkefniğ ağ reikna summu kvağrata talnanna í tengda listanum.

  2. Er Valröğun (e. selection sort) eins og hún er sınd á bls. 273 í kennslubókinni stöğug (e. stable)? Ef hún er stöğug rökstyğjiğ şağ á sannfærandi hátt. Ef hún er ekki stöğug sıniğ mótdæmi og segiğ hvort hægt sé ağ breyta forritinu şannig ağ şağ sé stöğugt.

  3. [Haustpróf 2001] Hver er hámarksfjöldi skipta sem stærsta stak fylkis er fært milli sæta í fylkinu í Innsetningarröğun, miğağ viğ Forrit 6.3 á bls. 276 í kennslubók?

  4. Í raunveruleikanum virğist mun algengara ağ tíğni gilda fylgi Zipf-dreifingu en ağ şau séu jafndreifğ á tilteknu bili. Gögn eru Zipf-dreifğ ef algengasta gildiğ kemur fyrir c sinnum, næstalgengasta kemur fyrir c/2 sinnum, şriğja algengasta c/3 sinnum, og almennt ağ i-ta algengasta gildiğ kemur fyrir c/i sinnum. Şetta gildir auğvitağ yfirleitt ekki nákvæmlega, en til dæmis dreifing orğa í bókum líkist oft Zipf-dreifingu, sama gildir um vinsældir Vefsíğna og ımislegt fleira.
    Şiğ eigiğ ağ skrifa fall sem bır til slembifylki heiltalna miğağ viğ ákveğnar forsendur um tíğni algengasta staksins, (c) og heildarfjölda gilda (n). Falliğ hefur hausinn:
        void slembiZipf( int c, int n, int a[] )
     
    Geriğ ráğ fyrir ağ fylkiğ a sé şegar skilgreint og af stærğ sem er a.m.k. n. Athugiğ ağ best er ağ setja stökin fyrst inn í fylkiğ í röğ eftir tíğni şeirra (látiğ töluna 1 vera şá algengustu, töluna 2 vera næstalgengasta, o.s.frv.) og stokka síğan stökin í fylkinu. Stokkun umrağar stökum fylkis şannig ağ allar umrağanir şess eru jafnlíklegar. Hún fer şannig fram ağ ef viğ hefğum 100-staka fylkiğ a şá er fyrst tekiğ stakiğ í a[99], valin slembitala r á bilinu 0 til 99 og víxlağ á stökunum a[99] og a[r] (athugiğ ağ r gæti veriğ 99). Şvínæst er valin slembitala r á bilinu 0 til 98 og víxlağ á a[98] og a[r]. Şetta er gert şar til komiğ er niğur í 0.
    Beriğ síğan saman hrağa Innsetningarröğunar á annars vegar jafndreifğu fylki og hins vegar á fylki meğ Zipf-dreifğri tíğni staka.

  5. Dæmi 6.35 á bls. 292 í kennslubók.
    [Şığing: Teikniğ upp myndir, svipağar myndum 6.8 og 6.9, fyrir lyklanna E A S Y Q U E S T I O N. ]


hh (hja) hi.is, 14. mars, 2005.