Ohjelmistotekniikan linja

Johdatustietojenkäsittelytieteeseen I 31.10.2001

1. Kahden luonnollisen luvun (ei-negatiivisen kokonaisluvun) a ja b suurimmalla yhteisellä tekijällä (syt) tarkoitetaan luonnolista lukua, jolla sekä a että b ovat (tasan) jaollisia.

a)      Kirjoita moduuli syt(a, b), joka määrää iteratiivisesti luonnollisten lukujen a ja b suurimman yhteisen tekijän

b)      Kirjoita moduuli syt(a, b) rekursiivisesti

c)      Esitä laskennallisesti vaihe vaiheelta, miten lukujen 42 ja 24 suurimman yhteisen tekijän määräytyminen tapahtuu (joko iteratiivisesti tai rekursiivisesti).

2. Kirjoita moduuli MatriisiSumma(A, m, n), joka laskee m x n - matriisin A alkioiden summan. (Huom. merkintä: A[r, s] on matriisin A alkio rivillä r , sarakkessa s ) .

3. Luonnollisten lukujen a ja b kertolasku voidaan esittää muodossa

a*b = a+a+a+ … +a ( b kertaa )

Tee tähän sääntöön perustuva kertolaskualgoritmi

a)      iteratiivisesti

b)      rekursiivisesti.

4. Erään binääripuun solmut esijärjestyksessä lueteltuina ovat 1, 2, 3, 4, 6, 8, 9, 7, 5. Saman puun solmut välijärjestyksessä ovat 2, 1, 8, 6, 9, 4, 7, 3, 5. Miten puun muoto voidaan päätellä annetuista tiedoista. Piirrä puu.

5. Tee moduli, joka muuttaa annetun kokonaislukuvektorin järjestetyksi binääripuuksi. Esitä kuvion avulla, millainen järjestetty binääripuu syntyy vektorista:

{34, 6, 12, 5, 3, 19, 18, 4, 1, 36, 15, 25, 20, 40, 38, 35, 39, 42}