*Pravilnost algoritma

Pravilnost zgornjega algoritma najlažje dokažemo tako, da najprej dokažemo to pomožno trditev:

Trditev dokažemo s popolno indukcijo.

Za i = 1 trditve ni težko preveriti: spremenljivka naj po prvem obhodu zanke vsebuje prvi element tabele, ta pa je seveda najmanjši med prvimi i elementi tabele, če je i = 1.

Sedaj pa predpostavimo, da trditev velja za nek i < n, in preverimo, ali velja tudi za i+1. Recimo, da spremenljivka naj po i obhodih zanke res vsebuje najmanjše izmed prvih i števil v tabeli. V naslednjem obhodu zanke obravnavamo število, ki je v tabeli na mestu i+1. Če je to število manjše od doslej najmanjšega, se priredi spremenljivki naj, tako da naj sedaj vsebuje najmanjše število izmed prvih i+1 elementov tabele. V nasprotnem primeru – če število na mestu i + 1 ni manjše od najmanjšega med prvimi i elementi – pa spremenljivka naj prav tako vsebuje najmanjše število izmed prvih i + 1 elementov tabele, saj ostane nespremenjena. Trditev torej velja tudi za i+1, popolna indukcija pa nam zagotavlja, da velja za vse i ∈ {1, . . . , n}.

Kaj pa spremenljivka naj vsebuje po vseh n obhodih zanke? Sodeč po trditvi, ki smo jo pravkar dokazali, vsebuje najmanjše število izmed prvih n elementov tabele, torej najmanjši element celotne tabele! Funkcija potemtakem dokazano vrača pravilne vrednosti.

Vaja

def vsotaPrvihN(n):
  i = 0
  vsota = 0
  while i < n:
    i += 1
    vsota += i
  return vsota