10. Procedurální programování

Přiřazovací příkaz a jeho varianty

Tato lekce je věnována procedurálnímu programování v Mathematice. Jde o programátorský styl známý z klasických programovacích jazyků, jako je Pascal, C, Java, Python, atd.

Důležitou roli v procedurálním programování má přiřazovací příkaz (globální pravidlo).

x=16

Příbuzná konstrukce je  x+=c, která je zkratkou za  x=x+c.

x+=2

Pro odčítání, násobení a dělení existují podobné zkratky:

x-=2

x*=2

x/=2

Další dvě užitečné zkratky jsou  x++ a x-- (zvětšení a zmenšení hodnoty proměnné o 1).

Složený příkaz

Složený příkaz je posloupnost příkazů oddělených středníky. Postupně se vyhodnocují jednotlivé příkazy, výsledkem je výstup posledního příkazu.

a=3;b=2;a+b

Poznámka: Mathematica nerozlišuje mezi příkazem a výrazem. Např. a+b je možné chápat jako výraz, ale i jako příkaz “sečti a, b”.

Napíšeme-li středník na konec složeného příkazu, nezobrazí se žádný výstup (jde o složený příkaz, kde poslední příkaz je prázdný).

a=1000!;(* výpočet faktoriálu a uložení do proměnné bez zobrazení výsledku *)

Clear[a,b]

V dalších částech se věnujeme cyklům, podmíněným příkazům a dalším konstrukcím. Bude-li uvedeno, že na nějakém místě může stát libovolný příkaz/výraz, znamená to, že tam může být též složený příkaz.

Cykly

Konstrukce Do[příkaz,{j,min,max}] opakovaně vykonává zadaný příkaz, přičemž za j postupně dosazuje hodnoty od min do max.

f[n_]:=(i=1;Do[i*=j,{j,1,n}];i)(* funkce pro výpočet n! pomocí cyklu Do *)

Poznámka: Na pravé straně v definici funkce jsou kulaté závorky, neboť := má vyšší prioritu než ;. Cyklus Do sám o sobě nevrací žádný výstup, proto je na konci složeného příkazu ještě uvedeno “i” jakožto návratová hodnota funkce.

f[5]

Clear[f]

Konstrukce While[podmínka,příkaz] vykonává příkaz tak dlouho, dokud platí zadaná podmínka. Na rozdíl od cyklu Do tedy nemusíme předem vědět, kolikrát cyklus proběhne.

f[n_]:=(i=j=1; While[j<=n,i*=j;j++];i)(* funkce pro výpočet n! pomocí cyklu While *)

f[5]

Clear[f]

Konstrukce For[inicializace,podmínka,inkrementace,příkaz] nejprve vyhodnotí inicializaci. Poté vykonává příkaz a inkrementaci tak dlouho, dokud platí zadaná podmínka. Inicializace a inkrementace mohou být libovolné příkazy.

f[n_]:=(For[i=j=1,j≤n,j++,i*=j];i)(* funkce pro výpočet n! pomocí cyklu For *)

f[5]

Clear[f]

Lokální proměnné

Předchozí funkce pro výpočet faktoriálu modifikují obsahy globálních proměnných i, j, viz hodnoty po skončení posledního výpočtu:

i

j

Clear[i,j]

Toto chování může být nežádoucí, neboť v proměnných může mít uživatel uložena data, která mu funkce přepíše.

Pomocí konstrukce Module[seznam lokálních proměnných,příkaz] můžeme deklarovat lokální proměnné (a případně jim přiřadit počáteční hodnoty).

f[n_]:=Module[{i=1,j},Do[i*=j,{j,1,n}];i]

Uvnitř modulu jsou i, j nyní chápány jako lokální proměnné odlišné od stejnojmenných globálních proměnných. Kontrola:

i=0;

f[5]

i

Vidíme, že funkce nepřepsala obsah globální proměnné i, neboť pracuje s lokální proměnnou i.

Clear[f]

Podmíněné příkazy

If[podmínka,výraz,alternativní výraz] vyhodnotí a vrátí výraz nebo alternativní výraz podle toho, zda je splněna zadaná podmínka. Alternativní výraz je nepovinný (jestliže není zadán a podmínka není splněna, pak If vrátí Null).

Příklad: Vezměme libovolné číslo (Subscript[c, 0]). Zkonstruujme posloupnost (Subscript[{(Subscript[c, n])}, n=1]^∞) takovou, že (Subscript[c, n+1])=(Subscript[c, n])/2 pokud (Subscript[c, n]) je sudé, jinak (Subscript[c, n+1])=3(Subscript[c, n])+1. 
Např. pro (Subscript[c, 0])=10 dostáváme další členy 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

Collatzova hypotéza (Lothar Collatz, 1937): Pro každou volbu (Subscript[c, 0])∈ℕ existuje index n takový, že (Subscript[c, n])=1.

Hypotéza je jedním ze slavných otevřených problémů v matematice.

Program pro testování Collatzovy hypotézy – pro zadané (Subscript[c, 0]) počítáme členy posloupnosti tak dlouho, dokud nenarazíme na jedničku:

collatz[c0_]:=Module[{s={c0},i=c0},While[i>1,i=If[EvenQ[i],i/2,3i+1];AppendTo[s,i]];s]

collatz[10]

Jak dlouho trvá, než narazíme na jedničku? Následující graf ukazuje závislost počtu kroků na volbě (Subscript[c, 0]).

DiscretePlot[Length[collatz[n]],{n,1,40},PlotRange->All]

Clear[collatz]

If používáme v případě, že se rozhodujeme mezi dvěma variantami. V případě více variant je vhodný příkaz Which.

Which[(Subscript[podmínka, 1]),(Subscript[výraz, 1]),...,(Subscript[podmínka, n]),(Subscript[výraz, n])] najde nejmenší i takové, že (Subscript[podmínka, i]) je splněna. Poté vyhodnotí (Subscript[výraz, i]) a vrátí výsledek.

Hádání čísel - vygenerujeme náhodné číslo mezi 1 a n a necháme uživatele, aby hádal:

f[n_]:=Module[{x=RandomInteger[{1,n}],ok=False,y},
While[!ok,y=Input["Zadej číslo"];
Which[y==x,ok=True;Print["Správná odpověď!"],
y>x,Print["Správné číslo je menší než ",y],
x>y,Print["Správné číslo je větší než ",y]]]]

f[20]

Clear[f]

V předchozím programu si všimněte, kde jsou středníky a kde čárky – nelze je zaměňovat! Čárky oddělují argumenty funkcí, středníky oddělují příkazy ve složeném příkazu.

Srovnání programátorských stylů

Často se stává, že nějakou úlohu můžeme v Mathematice řešit mnoha různými způsoby (programátorskými styly). Dobře to ilustruje následující úloha.

Máme k dispozici mince o hodnotách (Subscript[c, 1]), ..., (Subscript[c, n]) (od každé hodnoty neomezený počet kusů). Chceme pomocí nich zaplatit částku x, pokud možno co nejmenším počtem mincí. Jaké typy a počty mincí máme použít? Předpokládejme, že (Subscript[c, 1])>(Subscript[c, 2])>...>(Subscript[c, n]) a (Subscript[c, n])=1 (jinak by úloha nemusela mít řešení).

K řešení použijeme hladový algoritmus: Vezmeme co největší počet mincí s hodnotou (Subscript[c, 1]) tak, abychom nepřekročili x, poté co nejvíce mincí (Subscript[c, 2]) tak, abychom nepřekročili zbytek, atd.
Je dokázáno, že pro běžné sady mincí (např. české koruny, euro, americké dolary) dává hladový algoritmus optimální výsledek, tj. nejmenší možný počet mincí.

Naprogramujeme funkci, která na vstupu dostane požadovanou částku x a seznam mincí {(Subscript[c, 1]), ..., (Subscript[c, n])}. Výstupem bude seznam, který říká, kolik kusů máme vzít od každého druhu mince.

czMince={50,20,10,5,2,1};(* hodnoty českých mincí *)

Budeme používat funkci Quotient, která vrací celočíselnou část podílu dvou čísel (Quotient[x,y] je totéž jako Floor[x/y]).

Quotient[13,5]

Promyslete si, jak fungují následující řešení!

1. řešení: procedurální programování

rozmen1[x_,mince_] := Module[{zbytek=x,s={},m,q,i},For[i=1,i≤Length[mince],i++,m=mince[[i]];q=Quotient[zbytek,m];AppendTo[s,q];zbytek-=m*q];s]

rozmen1[179,czMince]

Kontrola:

%.czMince

2. řešení: rekurze

rozmen2[x_,{}] := {}

rozmen2[x_,mince_] := Join[{Quotient[x,First[mince]]},rozmen2[Mod[x,First[mince]],Rest[mince]]]

rozmen2[179,czMince]

3. řešení: funkcionální programování

rozmen3[x_,mince_] := Module[{zbytek=x,q},Map[(q=Quotient[zbytek, #]; zbytek-= q #;q)&, mince]]

rozmen3[179,czMince]

Pro některé exotické sady mincí/bankovek nedává hladový algoritmus optimální výsledek.
Příklad: Západoafrický frank (např. Benin, Burkina Faso, Pobřeží slonoviny) má mince/bankovky v hodnotách 1, 5, 10, 25, 50, 100, 200, 250, 500.

rozmen3[400,{500,250,200,100,50,25,10,5,1}]

Ale optimální řešení je 400=200+200.

Clear[rozmen1,rozmen2,rozmen3]

Bonus: 15 způsobů, jak počítat faktoriál

Použitý zdroj: 
Michael Morrison (Wolfram Research, Inc.), Analyze, Visualize, Simulate: Mathematica for University Research, Wolfram Technology Conference 2011

StandardForm@Grid[{
{" ",Style[HoldForm[f=Factorial],"Input",FontSize->14, Background->White,Background->White]},
{" ",Style[HoldForm[f[n_]:=n!],"Input",FontSize->14, Background->White]},
{Style["Rule-based",FontFamily->"Arial",Gray,FontSize->14, Background->White],Style[HoldForm[f[n_]:=n f[n-1];f[1]=1],"Input",FontSize->14, Background->White]},
{Style["Procedural",FontFamily->"Arial",Gray,FontSize->14, Background->White],Style[HoldForm[f[n_]:=Module[{t=1},Do[t=t*i,{i,n}];t]],"Input",FontSize->14, Background->White]},
{" ",Style[HoldForm[f[n_]:=Module[{t=1,i},For[i=1,i<=n,i++,t*=i];t]],"Input",FontSize->14, Background->White]},
{Style["List-based",FontFamily->"Arial",Gray,FontSize->14, Background->White],Style[HoldForm[f[n_]:=Apply[Times,Range[n]]],"Input",FontSize->14, Background->White]},
{" ",Style[HoldForm[f[n_]:=Fold[Times,1,Range[n]]],"Input",FontSize->14, Background->White]},
{Style["Recursive",FontFamily->"Arial",Gray,FontSize->14, Background->White],Style[HoldForm[f[n_]:=If[n==1,1,n*f[n-1]]],"Input",FontSize->14, Background->White]},
{Style["Functional",FontFamily->"Arial",Gray,FontSize->14, Background->White],Style[HoldForm[f=If[#1==1,1,#1*#0[#1-1]]&],"Input",FontSize->14, Background->White]},
{" ",Style[HoldForm[f[n_]:=Fold[#2[#1]&,1,Array[Function[t,#t]&,n]]],"Input",FontSize->14, Background->White]},
{Style["Constructive",FontFamily->"Arial",Gray,FontSize->14, Background->White],Style[HoldForm[f[n_]:=Length[Permutations[Range[n]]]],"Input",FontSize->14, Background->White]},
{Style["Pattern-based",FontFamily->"Arial",Gray,FontSize->14, Background->White],Style[HoldForm[f[n_]:=First[{1,n}//.{a_,b_/;b>0}:>{b*a,b-1}]],"Input",FontSize->14, Background->White]},
{Style["String-based",FontFamily->"Arial",Gray,FontSize->14, Background->White],Style[HoldForm[f[n_]:=StringLength[Fold[StringJoin[Table[#1,{#2}]]&,"\"A\"",Range[n]]]],"Input",FontSize->14, Background->White]},
{Style["Mathematical",FontFamily->"Arial",Gray,FontSize->14, Background->White],Style[HoldForm[f[n_]:=Gamma[n+1]],"Input",FontSize->14, Background->White]},
{" ",Style[HoldForm[f[n_]:=Product[i,{i,n}]],"Input",FontSize->14, Background->White]}
},Alignment->{{Right,Left}},
Frame->{None,None,{{1,2}->True,{2,2}->True,{3,2}->True,{4,2}->True,{5,2}->True,{6,2}->True,{7,2}->True,{8,2}->True,{9,2}->True,{10,2}->True,{11,2}->True,{12,2}->True,{13,2}->True,{14,2}->True,{15,2}->True}},
Spacings->{1,0.40}
]