Domača naloga

Mirnesa Klisura

18. 05. 1999

Povzetek

Podana imamo dva seznama, ki ju hočemo združiti v en seznam. Z indukcijo bomo dokazali veljavnost trditve, da oba seznama hkrati ne moreta biti prazna.

1. Opis delovanja funkcije zlij

Na vajah smo napisali funkcijo zlij , ki zlije dva seznama v en seznam.

PRIMER: sez1 = 1 3 6 8 ; sez2 = 2 4 5 ; ⟹ nov seznam = 1 2 3 4 5 6 8 ;

Del kode funkcije zlij , izgleda takole:

tSeznam rezultat;
int glava;
if (sez1 == NULL) return sez2;
if (sez2 == NULL) return sez1;
rezultat = NULL;
do{
  if (vred_glave(sez1) > vred_glave(sez2))
    sez2 = izloci_glavo(&glava, sez2);
  else
    sez1 = izloci_glavo(&glava, sez1);
  rezultat = Dodaj_na_koncu(glava, rezultat);
} while ((sez1 == NULL) || (sez2 == NULL));

Funkcija zlij pa deluje na naslednji način:

• Če je sez1 prazen, vrnemo sez2.

• Če pa je sez2 prazen, potem vrnemo sez1.

• Če pa seznama nista prazna, potem gremo preverjati:

– če je vrednost glave iz sez1 večja od vrednosti glave iz sez2, potem iz sez2 izločimo glavo,

– drugače pa izločimo glavo iz sez1 in glavo dodamo na konec seznama.

To delamo dokler eden od seznamov ni prazen.

Ugotovili smo, da oba seznama hkrati ne moreta biti prazna. To pa zaradi tega, ker:

1. na začetku zanke oba seznama nista prazna,

2. v zanki se vedno samo en seznam krajša.

2. Naloga

Dokazati moramo veljavnost trditve. Pravilnost trditve pa bomo dokazali z indukcijo. Najprej bomo dokazali veljavnost trditve za bazo oz. osnovno vrednost. Nato pa bomo, s pomočjo predpostavke, trditev dokazali še za korak.

3. Dokaz

TRDITEV: Oba seznama hkrati ne moreta biti prazna.

BAZA: Dokazati moramo, da je trditev veljavna za vsako dolžino prvega niza, ki je večja od 0 in drugega, ki je 0, ter obratno.

1. sez1 = NULL, sez2≠NULL; Ker je sez1 prazen seznam, vrnemo sez2. Iz tega sledi, da je trditev veljavna.

2. sez1≠NULL, sez2 = NULL; Ker je sez2 prazen sezanam, vrnemo sez1. Iz tega sledi, da je trditev veljavna.

PREDPOSTAVKA: Predpostavljamo, da je trditev veljavna za vsako dolžino prvega seznama, ki je največ n_{1} in drugega, ki je največ n_{2}.

|sez1| = n_{1} |sez2| = n_{2}

KORAK: Dokazati moramo, da je trditev veljavna:

• za vsako dolžino prvega niza, ki je največ n_{1} + 1 in drugega, ki je največ n_{2}

• za vsako dolžino prvega niza, ki je največ n_{1} in drugega, ki je največ n_{2} +1

• za vsako dolžino prvega niza, ki je največ n_{1} + 1 in drugega, ki je največ n_{2} + 1

1. |sez1| = n_{1} + 1 |sez2| = n_{2} Ker noben od seznamov ni prazen, se sprehodimo po zanki do - while.

• Če je vred glave(sez1) > vred glave(sez2), se izloči glava iz sez2, dolžina sez2 pa se zmanjša za 1. Torej je

|sez2| = n_{2} − 1, |sez1| = n_{1} + 1

Dolžina sez2 se zmanjšuje za 1 toliko časa

– dokler sez2 ni prazen Za ta primer pa smo že dokazali veljavnost trditve (baza).

– ali pa dokler vred glave(sez1) ni manjša od vred glave(sez2) V tem primeru se izloči glava iz sez1, dolžina sez1 pa se zmanjša za 1. Sledi, da je

|sez1| = n_{1}, |sez2| = n_{2} − 1

Ker pa je po predpostavki, trditev veljavna za vsako |sez1| = n_{1} in |sez2| = n_{2}, potem velja tudi za ta primer, ko sta niza dolga n_{1} in n_{2} − 1.

• Če pa je vred glave(sez1) < vred glave(sez2), potem se izloči glava iz sez1, dolžina sez1 pa se zmanjša za 1. Torej je

|sez1| = n_{1}, |sez2| = n_{2}

Po predpostavki, pa trditev velja za ta dva niza.

2. |sez1| = n_{1} |sez2| = n_{2} + 1 Ker noben od seznamov ni prazen, se sprehodimo po zanki do - while.

• Če je vred glave(sez1) > vred glave(sez2), se izloči glava iz sez2, dolžina sez2 se zmanjša za 1. Torej je

|sez2| = n_{2}, |sez1| = n_{1}

Po predpostavki pa trditev velja za ta dva niza.

• Če pa je vred glave(sez1) < vred glave(sez2), potem se izloči glava iz sez1, dolžina sez1 pa se zmanjša za 1. Torej je

|sez1| = n_{1} − 1, |sez2| = n_{2} + 1

Dolžina sez1 se zmanjšuje za 1 toliko časa

– dokler sez1 ni prazen Za ta primer pa smo že dokazali,da trditev velja (baza).

– ali pa dokler vred glave(sez1) ni večja od vred glave(sez2) V tem primeru se izloči glava iz sez2, dolžina sez2 pa se zmanjša za 1. Sledi, da je

|sez2| = n_{2}, |sez1| = n_{1} − 1

Po predpostavki pa je trditev veljavna, za vsako dolžino sez1, ki je največ n_{1} in dolžino sez2, ki je največ n_{2}. Torej velja tudi za primer, ko je

|sez2| = n_{2}, |sez1| = n_{1} − 1

3. |sez1| = n_{1} + 1 |sez2| = n_{2} + 1 Ker noben od seznamov ni prazen se sprehodimo po zanki do - while.

• Če je vred glave(sez1) > vred glave(sez2), se izloči glava iz sez2, dolžina sez2 se zmanjša za 1. Torej je

|sez2| = n_{2}, |sez1| = n_{1} + 1

Pravilnost trditve za ta primer pa smo že pokazali v točki 1.

• drugače pa se izloči glava iz sez1, dolžina sez1 pa se zmanjša za 1.

Sledi, da je

|sez1| = n_{1}, |sez2| = n_{2} + 1

Za ta primer pa smo pokazali veljavnost trditve v točki 2.

4. Zaključek

S pomočjo indukcije, smo dokazali pravilnost trditve. Oba seznama hkrati torej ne moreta biti prazna.