Příklad. Napište funkci prohod(seznam, i, j), která v zadaném seznamu prohodí hodnoty na pozicích i, j. Nic nenavrací, jen změní seznam, který dostala.
>>> s = [1, 2, "a", "b"]
>>> prohod(s, 1, 3)
>>> s
[1, 'b', 'a', 2]
def prohod(seznam, i, j):
seznam[i], seznam[j] = seznam[j], seznam[i]
Příklad. Napište funkci je_uvnitr(delsi_seznam, kratsi_seznam), která zjistí, zda je kratsi_seznam někde vcelku obsažený v seznamu delsi_seznam. Je to tedy něco jiného než podmínka in na seznamech; bude se ale chovat podobně jako podmínka in na řetězcích.
>>> je_uvnitr([1,2,3,4,5], [3,4,5])
True
>>> je_uvnitr([1,2,3,4,5], [3,5])
False
>>> je_uvnitr([1,2,3,4,5,1,3,5,7], [3,5])
True
def je_uvnitr(delsi_seznam, kratsi_seznam):
for i in range(delsi_seznam):
if delsi_seznam[i:i+len(kratsi_seznam)] == kratsi_seznam:
return True
return False
Příklad. Slavný problém dvou loupežníků: dostaneme seznam čísel (vyjadřujících ceny nějakých hodnotných šperků, či v aktuálním kontextu též kabelek apod.) a chceme zjistit, jestli je nějakým způsobem jde rozdělit na férové poloviny (se stejným součtem cen). Napište funkci loupeznici(ceny), která pro zadaný seznam ceny navrátí True nebo False.
>>> loupeznici([1,1,2,2])
True # protože 1+2 == 1+2
>>> loupeznici([1,2,3])
True # protože 1+2 == 3
>>> loupeznici([1,2,7])
False
>>> loupeznici([12,34,56,78])
True # protože 12+78 == 34+56
>>> loupeznici([12,34,67,88])
False
def loupeznici(ceny):
return loupeznici_s_rozdilem(ceny, 0)
def loupeznici_s_rozdilem(ceny, vyhoda_prvniho):
if not ceny:
# pokud je seznam prázdný, musí být už lup rozdělený přesně napůl
return vyhoda_prvniho == 0
hodnota = ceny[0] # cena předmětu, který v tomhle kole rozdáme
zbytek = ceny[1:] # seznam bez tohoto předmětu
return (loupeznici_s_rozdilem(zbytek, vyhoda_prvniho + hodnota) or
loupeznici_s_rozdilem(zbytek, vyhoda_prvniho - hodnota))
# jen pro zajímavost; tenhle kód nemusíte číst.
def loupeznici(ceny):
for kod in range(2 ** len(ceny)):
# proměnná `kod` v binárním zápisu určuje, které věci připadnou komu
# sečteme tedy věci ohodnocené jedničkou a odečteme ohodnocené nulou
# když se součet rovná, našli jsme řešení
soucet = 0
for vec in ceny:
# dělením se zbytkem získáváme postupně všechny číslice čísla kod
# (v binárním zápisu)
kod, zbytek = divmod(kod, 2)
if zbytek == 1:
soucet += vec
else:
soucet -= vec
if soucet == 0:
return True
# pokud je součet nenulový, nestane se nic a zkusíme další řešení
return False
# Mimochodem, v Pythonu to jde přepsat i na jeden řádek:
def loupeznici(ceny):
return any(sum(c if kod & 2**i else -c for i, c in enumerate(ceny)) == 0 for kod in range(2**len(ceny)))
# Ale dělat by se to nemělo, protože to není ke čtení...
Doplním ještě další úlohu k procvičení.
Příklad. Máte dané dva řetězce, řekněme dvě slova. Napište funkci, která vymyslí, o kolik písmen je oproti sobě posunout, aby co nejvíc písmen bylo stejných.
Ukázky.>>> posunuti("abraka", "brok")
1 # druhé slovo posuneme o znak doprava; pak se budou shodovat tři písmena
>>> posunuti("nejneobdelavavatelnejsimi", "simpanz")
21
>>> posunuti("nejneobdelavavatelnejsimi", "konejte")
-2
def posunuti(prvni, druhe):
# začneme s asi nejhorším řešením a zkusíme najít nějaké lepší
nejlepsi_posunuti = 0
nejlepsi_pocet = 0
# projdeme všechna posunutí, kdy se slova aspoň písmenem překrývají
for posunuti in range(-len(druhe), len(prvni)):
pocet = 0
# spočítáme shodující se písmena
for i in range(len(prvni)):
if i - posunuti >= 0 and i - posunuti < len(druhe):
if prvni[i] == druhe[i-posunuti]:
pocet += 1
if pocet > nejlepsi_pocet:
nejlepsi_posunuti = posunuti
nejlepsi_pocet = pocet
return nejlepsi_posunuti