Nepadajoča zaporedja

Naloga

Napišite program, ki v seznamu poišče najdaljše nepadajoče zaporedje.

Poglejmo si nekaj primerov:

• l = [1,2,3,2,3,4,5]

  V seznamu l sta skriti dve nepadajoči zaporedji [1,2,3] in [2,3,4,5], torej je odgovor 4.

• l = [1,2,6,8,10,1,1,1,1,1,1,0]

  Seznam l tokrat razpade na nepadajoča zaporedja [1,2,6,8,10], [1,1,1,1,1,1] in [0]. Odgovor je potlej 6.

• l = [1,4,6,2,3,4,7,1,4,5,8,2,4,1,4,5,5,6,8,7,3,5,5,3,5,7,1,2,2,5,7,9,9,9,1,2]

  Odgovor je 8.

Seznama vam ni potrebno brati od uporabnika (recimo z input), ampak ga lahko definirate kar v svojem programu.

Standardne rešitve

Med običajnimi rešitvami obstajata dve osnovni strategiji. Tole je najbolj klasična rešitev. l = [1,4,6,2,3,4,7,1,4,5,8,2,4,1,4,5,5,6,8,7,3,5,5,3,5,7,1,2,2,5,7,9,9,9,1,2] to = 1 naj = 0 for i in range(1, len(l)): if l[i] < l[i-1]: to = 1 else: to += 1 if to > naj: naj = to print(naj) Spremenljivka to meri dolžino trenutnega podzaporedja. Če je trenutno število večje od prejšnjega, povečamo dolžino zaporedja za 1. Če je trenutno število manjše, se je začelo novo zaporedje in njegova dolžina je 1. Dolžina najdaljšega doslej najdenega zaporedja je shranjena v naj. V zanki preverjamo, ali je trenutno zaporedje daljše od doslej najdaljšega in v tem primeru zapišemo dolžino tega novega, najdaljšega zaporedja, v naj. V programu je nekoliko potratno, da pogoj to > naj preverjamo vsakič, čeprav bi ga zadoščalo, da bi ga po koncu vsakega zaporedja. Tako pridemo do naslednjega programa, ki pa ima manjšo napako. # Ta program ne deluje povsem pravilno! l = [1,4,6,2,3,4,7,1,4,5,8,2,4,1,4,5,5,6,8,7,3,5,5,3,5,7,1,2,2,5,7,9,9,9,1,2] to = 1 naj = 0 for i in range(1, len(l)): if l[i] < l[i-1]: if to > naj: naj = to to = 1 else: to += 1 print(naj) Program ne deluje, če se seznam konča z najdaljšim zaporedjem. Tako pri zaporedju [1, 2, 1, 2, 3, 4] odgovori 2 namesto 4. To lahko uredimo na več načinov: zadnje zaporedje lahko umetno prekinemo tako, da za zadnji element seznama dodamo "stražarja", element, ki je manjši od zadnjega. To storimo z l.append(l[-1]-1). To je grdo, saj nas ni nihče "pooblastil", da spreminjamo seznam l. Kaj, če smo ta seznam pripravili nekje v nekem drugem delu programa in si ga ne smemo kar tako popackati? Ena možnost je tale. l = [1,4,6,2,3,4,7,1,4,5,8,2,4,1,4,5,5,6,8,7,3,5,5,3,5,7,1,2,2,5,7,9,9,9,1,2] to = 1 naj = 0 lenL = len(l) for i in range(1, lenL+1): if i == lenL or l[i] < l[i-1]: if to > naj: naj = to to = 1 else: to += 1 print(naj) Ta program je neučinkovit (čeprav nas tule to najbrž ne boli preveč), ker v vsakem koraku preverja, ali je i že dosegel konec seznama. Mimogrede, dolžino seznama sem shranil v lenL, da mi ni potrebno stalno klicati funkcije len. Klici funkcij so "dragi": namesto da bi stalno klicali in klicali eno in isto funkcijo, si rezultat raje nekam zabeležimo. Najbolj praktično pa je na koncu zanke preveriti, ali je zadnje, "neprekinjeno" zaporedje daljše od najdaljšega, recimo, takole. l = [1,4,6,2,3,4,7,1,4,5,8,2,4,1,4,5,5,6,8,7,3,5,5,3,5,7,1,2,2,5,7,9,9,9,1,2] to = 1 naj = 0 for i in range(1, len(l)): if l[i] < l[i-1]: if to > naj: naj = to to = 1 else: to += 1 if to > naj: naj = to print(naj) Nekaterim, ki so delali tako, sem predlagal, da poskusijo spodnji if nekako združiti z zgornjim. Načelno se izogibamo temu, da večkrat ponavljamo enake dele programa. To navadno pomeni, da nečesa nismo dobro razmislili ali da bi morali definirati funkcijo, ki bo vsebovala ta košček kode (kar se bomo še učili). Še en razlog, da se izogibamo temu je tale: če v kodi, ki se takole ponovi, najdemo napako, moramo popraviti kodo na več mestih in lahko katero od mest spregledamo. Še en način, kako se znebiti drugega if, ki so ga odkrili tudi nekateri študenti, je tale l = [1,4,6,2,3,4,7,1,4,5,8,2,4,1,4,5,5,6,8,7,3,5,5,3,5,7,1,2,2,5,7,9,9,9,1,2] to = 1 naj = 0 for i in range(1, len(l)): if l[i] < l[i-1]: if to > naj: naj = to to = 1 else: to += 1 print(max(to, naj)) Isti trik lahko pravzaprav uporabimo tudi znotraj zanke. l = [1,4,6,2,3,4,7,1,4,5,8,2,4,1,4,5,5,6,8,7,3,5,5,3,5,7,1,2,2,5,7,9,9,9,1,2] to = 1 naj = 0 for i in range(1, len(l)): if l[i] < l[i-1]: naj = max(to, naj) to = 1 else: to += 1 print(max(to, naj)) Pokažimo še rokohitrsko različico programa. Naj razume, kdor hoče. l = [1,4,6,2,3,4,7,1,4,5,8,2,4,1,4,5,5,6,8,7,3,5,5,3,5,7,1,2,2,5,7,9,9,9,1,2] to = 1 naj = 0 for i in range(1, len(l)): naj = max(to, naj) to = to * (l[i]>=l[i-1]) + 1 print(naj) Druga oblika je zelo podobna prvi, le da naredimo zanko prek l, ne prek range(len(l)). Ker nimamo indeksa, pa ne moremo priti do prejšnjega elementa... zato si ga zapomnimo. V to obliko lahko predelamo katerokoli od gornjih različic. Lotimo se kar druge, one, kjer je šla zanka od 0 do len(n ). l = [1,4,6,2,3,4,7,1,4,5,8,2,4,1,4,5,5,6,8,7,3,5,5,3,5,7,1,2,2,5,7,9,9,9,1,2] to = 0 naj = 0 prej = l[0] for zdaj in l: if zdaj < prej: to = 1 else: to += 1 if to > naj: naj = to prej = zdaj print(naj) Glavni trik je konec zanke, kjer shranimo prejšnji element, da bomo z njim primerjali element iz naslednje iteracije zanke. Ko se zanka izvede prvič, pa primerjamo prvi element sam s sabo, ker ni manjši od sebe, bomo pristali v bloku else in povečali to z 0 na 1. Velika večina študentov je nalogo rešila na enega od teh načinov, predvsem na one, ki uporabljajo range(len(l)).