Tölvunarfræði 2

Vikublað 10

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

Heimadæmi 9

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. (a₁)² + (a₂)² + ... + (a_n)² , þar sem a_i 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. ]