Ples

In spravili so se plesat. V eno vrsto so se postavile ženske, v drugo moški. Prvi je plesal s prvo, drugi z drugo, tretji s tretjo in tako po očitnem vrstnem redu naprej.

Višine žensk in moških so podane takole (številke in število parov bi bilo lahko tudi drugačno!)

zenske = [158, 166, 150, 158, 152, 160, 172, 159, 158, 162] moski = [168, 172, 181, 166, 172, 174, 165, 169, 169, 185]

Ogrevalna naloga

Napiši program, ki za vsak par izpiše višino ženske, višino moškega in absolutno velikost razlike med njima.

Rešitev

Želena rešitev je

for e1, e2 in zip(zenske, moski): print(e1, e2, abs(e1 - e2))

Rešitev, ki ni tako želena, je

for i in range(len(zenske)): print(zenske[i], moski[i], abs(zenske[i] - moski[i]))

Razlog je očiten: daljša in nepreglednejša je.

Obvezna naloga

Napiši program, ki izpiše največjo (absolutno) razliko v višinah. Za gornje podatke izpiše 31.

Rešitev

naj_raz = 0 for e1, e2 in zip(zenske, moski): if abs(e1 - e2) > naj_raz: naj_raz = abs(e1 - e2) print(naj_raz)

Nekateri so tako navdušeni nad seznami, da jih morajo sestavljati tudi, kadar jih pravzaprav ne bi bilo potrebno. Takšni so nalogo rešili takole:

razlike = [] for e1, e2 in zip(zenske, moski): razlike.append(abs(e1 - e2) ) print(max(razlike))

Če bi kdo rekel, da je tole krajše, bi mu težko ugovarjali. Bolj pregledno? Tudi mogoče. Osebno mi ni všeč, ker brez potrebe naredi seznam.

Nekoč se bomo naučili prave rešitve tega problema. Pokažimo jo - za tiste, ki radi prehitevajo.

print(max(abs(e1 - e2) for e1, e2 in zip(zenske, moski)))

Dodatna naloga

Recimo, da bi radi poskrbeli, da bi bila največja razlika čim manjša. To storimo takole: najprej izračunamo največjo razliko, tako kot v obvezni nalogi. Nato pošljemo prvega moškega na konec. Ponovno ugotovimo največjo razliko in preverimo, ali je manjša kot prej. Nato pošljemo na konec še enega moškega ... Tako jih vrtimo, vsakič preverimo največjo razliko in si zapomnimo, za koliko je bilo potrebno zasukati vrsto moških, da smo dobili najmanjšo največjo razliko. (Besedilo je pravilno: največja razlika v višini mora biti čim manjša.)

Program naj izpiše, za koliko je potrebno zasukati vrsto moških in kakšna je tedaj največja razlika.

V gornjem primeru bomo dobili razliko 27, če prestavimo na konec 3 moške.

Rešitev

Naredimo lahko tako:

najm_raz = 1000 for odm in range(len(moski)): naj_raz = 0 for e1, e2 in zip(zenske, moski[odm:] + moski[:odm]): if abs(e1 - e2) > naj_raz: naj_raz = abs(e1 - e2) if naj_raz < najm_raz: najm_raz = naj_raz naj_odm = odm print(naj_odm, najm_raz)

Spremenljivka odm šteje, koliko moških damo na konec. Namesto da bi jih dejansko prestavljali, smo tu pustili seznam moških pri miru, pač pa smo v zip namesto moski dali nov seznam, ki smo ga sestavili tako, da smo odbili prvih odm moških (moski[odm:]) in nato na konec prilepili (prav teh) odm moških (moski[:odm]).

Kot se bo izkazalo na prihodnjih predavanjih, lahko prvi element seznama moski sicer prestavimo na konec tako, da napišemo moski.append(moski.pop(0)) - v seznam moških dodaj element, ki ga pobrišeš z začetka seznama.

Z

if naj_raz < najm_raz: najm_raz = naj_raz naj_odm = odm

smo si zapomnili najmanjšo največjo razliko in potrebno število premaknjenih moških (hm). Precej pogostejša rešitev je bila zlaganje vsega skupaj v nov seznam ter iskanje največjega elementa in njegovega indeksa v tem seznamu, podobno kot smo omenili že v prejšnji nalogi.. Tudi prav.

Rešitev postane preglednejša, če spravimo rešitev prejšnje naloge v funkcijo.

def naj_razlika(zenske, moski): naj_raz = 0 for e1, e2 in zip(zenske, moski): if abs(e1 - e2) > naj_raz: naj_raz = abs(e1 - e2) return naj_raz najm_raz = 1000 for odm in range(len(moski)): naj_raz = naj_razlika(zenske, moski[odm:] + moski[:odm]) if naj_raz < najm_raz: najm_raz = naj_raz naj_odm = odm print(naj_odm, najm_raz)

Vedno je lažje razmišljati o dveh enojnih zankah kot o eni dvojni.

Bolj Pythonovska rešitev bi bila takšna (to se bomo učili - nekoč):

def naj_razlika(zenske, moski): return max(abs(e1 - e2) for e1, e2 in zip(zenske, moski)) najm_raz, najm_odm = min((naj_razlika(zenske, moski[odm:] + moski[:odm]), odm) for odm in range(len(moski))) print(najm_odm, najm_raz)

Zelo dodatna naloga

V dodatni nalogi smo le vrteli vrsto moških, vrstni red pa je ostal enak. Napiši program, ki pove, kako je potrebno "poparčkati" moške in ženske, da bo razlika med najbolj različnim parom čim manjša. Pri tem je pare dovoljeno poljubno pomešati.

Rešitev

Izkaže se, da je dovolj, da uredimo oba seznama po velikosti. Torej:

print(naj_razlika(sorted(moski), sorted(zenske)))

Če imamo funkcijo naj_razlika, seveda. Sicer pa uredimo oba seznama in ju pošljemo čez kaj od tega, kar smo napisali zgoraj.

Naloga, prvič, zahteva, da znamo urediti seznama. To je, da izvohamo funkcijo sorted ali kaj podobnega.

Drugič, zahteva, da znamo dokazati, da tako res dobimo najmanjšo možno razliko. Dokaz (hvala, Tomaž Hočevar!) je narisan na sliki, razmislite pa ga sami.