Počítač to vidí jinak: zjišťování dělitelnosti

Co se naučíš:

• Jak v Pythonu elegantně zjišťovat vzájemnou dělitelnost čísel.
• Jak uplatnit zjišťování dělitelnosti při řešení rozličných úloh.

Těsná souvislost s matematikou

K řešení úloh s dělitelností je samozřejmě potřeba umět matematiku. Úlohy lze ale využít i naopak: s jejich pomocí zlepšit porozumění dělitelnosti a souvisejících algoritmů.

Asi už je ti jasné, že počítač „vidí“ leccos jinak než člověk. Ukážeme si to příkladu zjišťování dělitelnosti, který se nám navíc bude hodit i v budoucnu.

Zjišťování dělitelnosti na počítači

Příklad: Věrnostní program

Standardizované palety pro usnadnění přepravy materiálu

Velkoobchod stavebnin přičte věrnostní body odběrateli za každou objednávku, u níž materiál vyjde přesně na celý počet palet. Samozřejmě nechtějí platit zaměstnance na to, aby kontroloval objednávky a body přiděloval. Chtějí napsat program. Napiš funkci, která dostane jako parametr množství objednaného materiálu v kusech) a kapacitu jedné palety a vrátí hodnotu True nebo False podle toho, jestli mají být za objednávku odběrateli připočteny věrnostní body. Například tvárnic ztraceného bednění určitého rozměru se na paletu vejde 36. Za objednávku 100 kusů se tedy body nepřičtou, za objednávku 216 kusů naopak ano, protože 216 kusů vyjde přesně na 6 palet.

Jak na řešení? Nejdřív je nutno si ujasnit co dostaneme (vstupy) a co máme zjistit (výstup). Prima je, že je to už popsáno v zadání: vstupem je počet objednaných kusů a počet kusů, který zaplní paletu. Výstupem je logická hodnota odpovídající započtení věrnostních bodů. Kdy se započtou body? To je taky v zadání: Když objednané zboží vyjde přesně na palety.

Jak to ale zjistit? Obvykle je dobrý nápad zamyslet se nad konkrétním příkladem a jeho řešením papírem, tužkou a hlavou. Nejpozději po chvíli zkoušení odhalíš, že se vlastně ptáme na dělitelnost. Pokud je velikost objednávky násobkem kapacity palety, body se mají připočíst, a jinak ne. Nebo jinými slovy, aby se připočetly body, musí být kapacita palety dělitelem velikosti objednávky.

Původní problém jsem tedy převedli na problém jiný (snad jednodušší, jinak bychom si moc nepomohli). Jak zjišťujeme dělitelnost? Na to znáš spoustu pravidel ze základní školy. Sudá čísla poznáš podle poslední číslice, dělitelnost třemi podle ciferného součtu a tak dále. Počítač ale čísla „vidí“ jinak — ve dvojkové soustavě. Naše lidská pravidla, pracující s číslicemi v desítkovém zápisu, by samozřejmě použít šla. Ale bylo by to nepraktické, navíc pro drtivou většinu čísel (už třeba pro číslo sedm) jednoduché pravidlo ani nemáme. Počítač sice neumí jednoduše pracovat s desítkovými číslicemi, zato umí velmi rychle počítat. Nejjednodušší (a přitom rychlá) cesta ke zjištění dělitelnosti tak je prostě výpočet zbytku po dělení. To už umíš z kapitoly o počítání. Číslo je dělitelné, právě když je zbytek nulový:

Teď už tedy víme, jak kontrolovat dělitelnost, a můžeme zpracovat celý program.

def PridelitBody(ObjednanoKusu, KapacitaPalety) :
	if ObjednanoKusu % KapacitaPalety == 0 :
		return True
	else:
		return False

Programátoři mají rádi stručnost

Výsledkem vyhodnocení podmínky zapsané za klíčovým slovem if je logická hodnota — přesně ta, kterou vzápětí funkce vrací. V tom případě je tedy možné ji vrátit rovnou, není se o čem rozhodovat!

def PridelitBody(ObjednanoKusu, KapacitaPalety) :
	return ObjednanoKusu % KapacitaPalety == 0

Proč velkoobchod tento věrnostní program zrušil?

Analýzou objednávek velkoobchod zjistil, že udělování věrnostních bodů vede jen ke zvýšení administrativní zátěže a program zrušil. Odhadneš proč? Jak asi odběratelé objednávali zboží, když potřebné množství nevycházelo přesně na palety?

Sudost, lichost a počet potřebných otázek (bitů) v obecném případě

Teď už umíme rozhodovat o dělitelnosti, umíme tedy také rozlišit sudá a lichá čísla. Díky tomu můžeme vylepšit předchozí program na zjišťování počtu potřebných bitů (otázek).

Příklad:

V minulé kapitole jsme napsali program, který fungoval správně jen pro mocniny dvou. Nyní ho zobecníme, aby dával smysluplnou odpověď i pro jiné počty možností. Vyjdeme ze stejného postupu, jaký používáme při ručním počítání pomocí postupného dělení dvěma: pro jistotu předpokládáme smůlu, takže v případě lichého počtu možností vezmeme tu „větší půlku“.

Využijeme předchozí program. Už víme, že naše „půlení“ v obecném případě neodpovídá dělení dvěma, protože někdy uvažujeme „větší půlku“:

def PocetBitu (PocetMoznosti) :
	PocetPuleni = 0
	while PocetMoznosti != 1:
		PocetMoznosti = VetsiPulka ( PocetMoznosti )
		PocetPuleni = PocetPuleni + 1
	return PocetPuleni

Program můžeš zkusit spustit, ale asi selže. Dosud jsme totiž nepopsali, jak pracuje funkce VetsiPulka. V té se musíme rozhodovat. Pokud je počet možností sudý, stačí vrátit obyčejnou polovinu. Pokud je lichý, musíme vrátit tu „větší půlku“. Tu získáme třeba tak, že budeme dělit dvěma číslo o jedna větší:

def VetsiPulka ( n ):
	if n % 2 == 1 :
		return n / 2
	else :
		return (n+1) / 2

Nefunguje!

Funkce VetsiPulka() funguje opačně, lichá čísla se snaží půlit přesně, a ze sudých dělá lichá.

Prověř, jestli program funguje podle našeho očekávání!

Výpis dělitelů

Úloha:

K řešení nejrůznějších problémů se hodí umět rychle hledat dělitele daného přirozeného čísla. Naprogramuj funkci, která na vstupu dostane přirozené číslo a vypíše všechny jeho dělitele.

Nápověda

1. Víc hlav víc ví. Klidně s někým spolupracuj!
2. Rozmysli si, jestli dobře rozumíš zadání.
3. Najdi systematický a spolehlivý postup pro hledání všech dělitelů:
   1. Zkus si několik příkladů ručně na papír, najdi třeba dělitele čísel 12, 15, 28, 164.
   2. Co se ve tvém postupu stále opakuje? Jak zajistíš, že žádný dělitel nechybí?
   3. Čím větší čísla vyzkoušíš, tím víc omezíš svou intuiciNapř. dělitelnost dvěma vidíš na první pohled, stejně tak znáš zpaměti některá prvočísla... a donutíš se spolehnout na systematický postup.
4. Nalezený postup nějakým způsobem popiš — v Pythonu, vývojovým diagramem nebo svými slovy.
5. Popis zkontroluj: zkus ho na nějakém příkladu přesně provést, aby bylo jisté, že popisuje přesně to, co si představuješ. Ještě lepší bude zkontrolovat si popisy vzájemně s někým dalším.
6. Popis postupně přepracuj do Pythonu: použij proměnné, výpočty, rozhodování, opakování...
7. Nezapomeň výsledek opět otestovat a případně opravit.

Řešení

Při hledání dělitelů chceme postupovat systematicky, např. od nejmenšího. Ručně postupujeme tím způsobem, že zkoušíme jedno číslo za druhým, jestli náhodou není jedním z dělitelů. Jestli ano, tak jej zapíšeme, jestli ne, pokračujeme s testováním dalšího čísla. Takto postupujeme od nejmenšího možného do největšího možného dělitele, tedy od jedné do samotné zadané hodnoty. (Možně jsou samozřejmě i jiné postupy, tento je jeden z nejjednodušších na naprogramování.)

def VypisDelitele (Cislo) :
	Delitel = 1
	while Delitel <= Cislo :
		if Cislo % Delitel == 0 :
			print (Delitel)
		Delitel = Delitel + 1

Shrnutí

• Některé osvědčečné postupy nejsou na počítači zrovna praktické.
• Dělitelnost zjišťujeme podle zbytku po dělení: platí-li Delenec % Delitel == 0, je dělitel vskutku dělitelem dělence.

Úlohy

Úloha: Co když neznám operátor modulo (%)?

Ukázali jsme si zjišťování dělitelnosti pomocí operátoru modulo. Jak je ale naprogramovaný samotný operátor? Ne každý procesor umí počítat zbytek po dělení přímo (na hardwarové úrovni). V takových případech je nutno zbytek po dělení naprogramovat pomocí jednodušších operací (např. jen sčítání, odčítání) a případně s pomocí rozhodování, cyklů atd.

Podaří se ti naprogramovat funkci ZbytekPoDeleni(Delenec, Delitel), která vrátí hodnotu zbytku po dělení hodnoty parametru Delenec hodnotou parametru Delitel? Až ti funkce bude fungovat pro přirozená čísla, můžeš ji zkusit rozšířit na záporná celá čísla.

Nápověda

Při hledání algoritmu uplatni už známý postup:

1. Vyzkoušej si několik příkladů s papírem a tužkou. Všímej si:
   • Jak vlastně postupuješ?
   • Proč postupuješ právě tím postupem? Vede jistě ke správnému výsledku?
   • Které části postupů pro různé hodnoty se shodují, které se liší? Jak?
   • Které části postupů by mohly fungovat obecně?
2. Lidskému pohledu na čísla (např. hned vidíš, že 55=11⋅5) zabráníš použitím větších čísel.
3. Zformuluj svůj postup co nejpřesněji, třeba pomocí vývojového diagramu.
4. Zkus vyřešit několik příkladů pomocí vytvořeného postupu - funguje správně? Co je třeba doplnit či přepracovat?
5. Vyzkoušej, jak algoritmus funguje pro vhodné testovací hodnoty: velká čísla, malá čísla, krajní hodnoty, totožná čísla atp.
6. Máš-li dostatečně podrobný popis algoritmu, zapiš jej pomocí Pythonu.

Pro někoho je naopak snazší napsat nejdřív krátký a částečně funkční program, ten potom postupně doplňovat a rozšiřovat. Výhoda je, že lze výsledky své práce okamžitě testovat. Nevýhoda je, že bude výsledný program dost možná méně přehledný, než program, který byl od začátku promyšlený.

Řešení

Dělení nulou

Problém uvedeného řešení se projeví při pokusu dělit nulou. Otázka je, jak by se měl program správně zachovat. To by si měli promyslet především studenti. Patrně dojdou k tomu, že by se měl chovat obdobně, jako když se pokoušíme dělit nulou při běžném dělení. Nepadá totiž v úvahu vrátit nějaké číslo (to by si někdo mohl nesprávně vyložit jako skutečný výsledek výpočtu) nebo nějak tiše pokračovat (to bychom si nemuseli všimnout, že nastal nějaký problém). Asi nejjednodušší způsob, jak vyvolat potřebné chování bez vysvětlování mechanismu výjimek, je v dané situaci prostě zkusit nulou opravdu dělit. Program spolehlivě selže (což je žádoucí chování, a studenti by to měli pochopit; podobně žádoucí je třeba vypadávání pojistek). Správným řešením je raise ZeroDivisionError("integer division or modulo by zero").

Jedno z možných řešení:

def ZbytekPoDeleni(Delenec, Delitel) :
    while Delenec > Delitel :
        Delenec = Delenec - Delitel
    return Delenec

Uvedený program má jednu „drobnou vadu“. V některých případech nikdy neskončí. Zjisti proč a chybu odstraň.

Úloha: Vojáci na seřadišti

Tradiční školní úlohy na procvičení dělení se zbytkem zní např. takto:

„Skupina vojáků se snaží seřadit, ale pořád někdo přebývá. Dvojstup se nedaří. Při pokusu o trojstup přebývají dva vojáci. Při čtyřstupu přebývá jeden. Při pětistupu přebývají tři. Při šestistupu jich přebývá pět.
Kolik vojáků se snaží seřadit?“

Vyřeš úlohu a podle potřeby si pomoz Pythonem a interaktivní konzolí. Odpověz i na další související otázky: Jak by to mohli udělat, aby nikdo nepřebýval? Kolik je různých řešení, co mají společného? Kolik je vojáků nejméně, kolik nanejvýš? Lze vždy najít nějaké vhodné seřazení? Kdy ano, kdy ne? Má každá varianta uvedené úlohy řešení? Své odpovědi podpoř úvahou, příkladem, či zdrojovým kódem.

Tip: Python jako kalkulačka

Jak by nám mohl k řešení pomoci Python? Jako první se nabízí počítání v interaktivní konzoli, např. při ověřování, jestli má nějaké číslo správné zbytky. Nezapomeň využít klávesové zkratky k vyvolání a úpravě některého z dříve zadaných příkazů. Použitím proměnných si můžeš ušetřit vypisování hodnot.

Tip: Kontrola řešení

Možná postupuješ tak, že zkoušíš najít nějaký slibný počet vojáků (třeba s pomocí známých znaků dělitelnosti) a ten potom ověřuješ. Uvědom si, že to ověřování může probíhat pořád stejně: Zkontrolujeme správný zbytek pro dvojstup, pro trojstup, pro čtyřstup atd., a pokud někde nevyjde správná hodnota podle zadání, víme, že daný počet vojáků je špatně. Naopak pokud počet vojáků všemi kontrolami projde, správnou odpověď jsme našli.

Zkus napsat funkci, která jako parametr přijímá navrhovaný počet vojáků a vrací hodnotu True nebo False podle toho, jestli daný počet splňuje podmínky zadání.

Řešení

def SpravnyPocet( Pocet ) :
	if Pocet % 2 != 1 :
		return False
	if Pocet % 3 != 2 :
		return False
	if Pocet % 4 != 1 :
		return False
	if Pocet % 5 != 3 :
		return False
	if Pocet % 6 != 5 :
		return False
	return True	# kontroly neodhalily zadnou nesrovnalost, Pocet je spravny

Rozmysli si, proč se v uvedeném zdrojovém kódu nikde nevyskytuje else.

Tvoje funkce může samozřejmě vypadat odlišně, klidně použij svou vlastní verzi! Např. lze rozhodování obrátit a vzájemně vnořit. To je sice poměrně přirozená myšlenka, ale výsledný kód je hůře čitelný a náchylnější k chybě:

def SpravnyPocet( Pocet ) :
	if Pocet % 2 == 1 :
		if Pocet % 3 == 2 :
			if Pocet % 4 == 1 :
				if Pocet % 5 == 3 :
					if Pocet % 6 == 5 :
						return True
	return False	# kontroly nekde selhaly, Pocet tedy neni spravny

Místo vnořování je lepší kontroly případně spojit do jedné podmínky (s pomocí logického and):

def SpravnyPocet( Pocet ) :
	if (Pocet % 2 == 1) and (Pocet % 3 == 2) and (Pocet % 4 == 1) and (Pocet % 5 == 3) and (Pocet % 6 == 5) :
		return True
	else:
		return False	# kontrola nekde selhala, Pocet tedy neni spravny

Jiná možnost je ukládat prozatimní výsledek do logické proměnné a její hodnotu pak vrátit. To je pro někoho přehlednější, protože pak má funkce jediný výstupní bod:

def SpravnyPocet( Pocet ) :
	Odpoved = True	# na zacatku predpokladejme, ze je pocet spravny
	if Pocet % 2 != 1 :
		Odpoved = False
	if Pocet % 3 != 2 :
		Odpoved = False
	if Pocet % 4 != 1 :
		Odpoved = False
	if Pocet % 5 != 3 :
		Odpoved = False
	if Pocet % 6 != 5 :
		Odpoved = False
	return Odpoved

Takováto funkce bude v průměru o něco pomalejší než předchozí. Rozmysli si kdy a pročNapř. pro hodnotu 52 selže hned první kontrola a je jasné, že nejde o správnou odpověď — funkce přesto kontroluje dál.! Šlo by funkci upravit tak, aby pracovala rychleji, a pokud je některá podmínka splněna, aby se nezkoušely dalšíZkus vhodně použít elif?

Hotovou funkci zkoušej volat pro různé nadějné hodnoty v interaktivní konzoli. Zjistíš, že najednou postupuješ mnohem rychleji!

Tip: Automatické hledání správné odpovědi

Když už umíme nechat automaticky zkontrolovat správnost odpovědi, tak je možná zbytečné se namáhat s ručním hledáním kandidátů na výsledek. Napiš program, který postupně zkouší všechny hodnoty, dokud nedojde ke správnému řešení.

Řešení

PokusnyPocet = 6 + 5                      # nejmensi mozne reseni: v sestistupu prebyva 5 vojaku
while not SpravnyPocet(PokusnyPocet) :    # dokud PokusnyPocet neni spravnym resenim
	PokusnyPocet = PokusnyPocet + 1   # zvysujeme jej o 1 a novou hodnotu opet proverime
print(PokusnyPocet)                       # cyklus skoncil, takze PokusnyPocet je hledanym resenim

Tip: Hledání dalších řešení

Výše uvedený program vydá nejmenší správnou odpověď. Není jich ale víc? Můžeš zkusit program spustit několikrát za sebou (s několika potřebnými úpravami — v hledání chceš pokračovat k vyšším hodnotám, nikoliv nacházet stále dokola totéž řešení.

Řešení

PokusnyPocet = 6 + 5                      # nejmensi mozne reseni: v sestistupu prebyva 5 vojaku
while not SpravnyPocet(PokusnyPocet) :    # dokud PokusnyPocet neni spravnym resenim
	PokusnyPocet = PokusnyPocet + 1   # zvysujeme jej o 1 a novou hodnotu opet proverime
print(PokusnyPocet)                       # cyklus skoncil, takze PokusnyPocet je hledanym resenim
PokusnyPocet = PokusnyPocet + 1           # posuneme se na dalsi hodnotu k overeni
while not SpravnyPocet(PokusnyPocet) :    # odsud dal jsou proste okopirovane predchozi radky
	PokusnyPocet = PokusnyPocet + 1   
print(PokusnyPocet)                       
PokusnyPocet = PokusnyPocet + 1           
while not SpravnyPocet(PokusnyPocet) :    
	PokusnyPocet = PokusnyPocet + 1   
print(PokusnyPocet)

Vypadá to, že řešení bude opravdu víc. O něco lepší bude samozřejmě práci programu automatizovat, tedy použít cyklus: hledat řešení můžeme znovu a znovu, dokud nepřesáhneme třeba hodnotu 350.

Řešení

PokusnyPocet = 6 + 5
while PokusnyPocet < 350:
    while not SpravnyPocet(PokusnyPocet) :
    	PokusnyPocet = PokusnyPocet + 1
    print(PokusnyPocet)
    PokusnyPocet = PokusnyPocet + 1

Všimni si, co je na uvedeném kódu stejné a čím se naopak od předchozího liší.

Rozmysli si, jak je možné, že je poslední vypsané řešení vyšší než hodnota 350 zadaná jako mez vnějšího while cyklu?

Jak by se tedy vojáci mohli seřadit?

Při správném seřazení nechceme žádné přebývající vojáky. Hledáme dělitele počtu vojáků. Mohli bychom samozřejmě postupovat ručně. Lepší bude zamyslet se, jestli bychom nemohli využít nějakou již dříve naprogramovanou funkci.

Řešení

Už máme hotovou funkci VypisDelitele, stačí ji do našeho programu zapracovat (nezapomeň před tento zdrojový kód přidat také samotnou funkci VypisDelitele, aby Python věděl, jak funguje!):

PokusnyPocet = 6 + 5
while PokusnyPocet < 350:
    while not SpravnyPocet(PokusnyPocet) :
    	PokusnyPocet = PokusnyPocet + 1
    VypisDelitele(PokusnyPocet)             # misto poctu vypiseme rovnou delitele, dany pocet mezi nimi bude taky
    print("-----------------")              # timto na obrazovce oddelime vypis delitelu jednotlivych poctu vojaku
    PokusnyPocet = PokusnyPocet + 1

Zobrazené výsledky jsou ale nějaké divné. Vypadá to, že řešením této úlohy jsou prvočísla! To by byla skvělá zpráva, prvočísla jsou velmi důležitá pro šifrování dat (např. při bezpečné komunikaci s bankou). Prověř tedy, jestli jsme skutečně narazili na jednoduchý způsob hledání prvočísel. Samozřejmě nech Python ať ti pomůže, zkus znovu využít již jednou napsané funkce.

Zamysli se i nad dalšími otázkami, jejichž řešení zde už uvádět nebudeme:

• Existuje nějaké řešení, které vojákům umožní jiné řazení než do zástupu?
• Kolik je různých řešení, co mají společného? Kolik je vojáků nejméně, kolik nanejvýš?
• Má každá varianta úlohy (s jinými počty přebývajících vojáků apod.) řešení?
• Co je potřeba upravit na výsledném programu a použitých funkcích, když dostaneme jiné zadání podobného úkolu?

Matematika zůstává užitečná

Ukázali jsme, že lze úkol s pomocí programování vyřešit poměrně snadno, a není třeba znát hodně matematiky. To ale zdaleka neznamená, že by takové znalosti nebyly užitečné. Umožní tak např. řešení značně zrychlit tím, že některé možnosti prostě vůbec nebude kontrolovat. Zamysli se: je opravdu potřeba kontrolovat sudá i lichá čísla? Možná bychom si mohli polovinu kontrol zcela ušetřit, a tím program zrychlit (resp. umožnit řešení pro větší hodnoty).

Abychom si rozuměli: uvedené řešení není zrovna intelektuálně uspokojivé a navíc vyžaduje počítač. Mnohem elegantnější by bylo využít znalosti matematiky a odpovědi na otázky odvodit přímo. To ale není vždycky možné. Někdy třeba nemáme potřebné odborné znalosti nebo čas je správně použít (nebo potřebná teorie ani neexistuje). Právě v takových případech se potom velmi hodí využít způsob sice dosti primitivní, ale funkční, včetně třeba zkoušení všech možností. Programování tak umožňuje řešení složitějších problémů i těm, kteří např. v matematice ještě nejsou tak daleko.