Řešení úloh školního kola 43. ročníku
P-I-1
V zadání úlohy je stanoveno, že neznáme žádné předběžné
omezení hodnoty N a že N může být vysoké. Tato skutečnost nám
zakazuje použít v řešení úlohy pole, do něhož bychom si uložili
všechna čísla posloupnosti. Podobné pole by také bylo naprosto
zbytečné, k vyřešení úlohy nám bude stačit konstantní paměťový
prostor (nezávislý na N). Optimální algoritmus řešení, který zde
uvedeme, má lineární časovou složitost. Lepší řešení nemůže
existovat, neboť každé z daných N čísel je třeba jednou přečíst
a zpracovat.
Postup řešení úlohy je následující. Postupně budeme číst za
vstupu jednotlivá čísla tvořící zadanou posloupnost a budeme je
vyhodnocovat takovým způsobem, aby v následujících pomocných
proměnných byly stále aktuálně uloženy uvedené údaje:
- CISLO - právě přečtené číslo
- PREDCHOZI - předchozí číslo posloupnosti
- INDEX - pořadové číslo právě přečteného čísla
- HLADKY - pořadové číslo, kde začíná právě sledovaný
hladký úsek
- KONSTANTNI - pořadové číslo, kde začíná úsek stejných čísel
vedoucí až k právě přečtenému číslu
- H1 - menší z hodnot tvořících právě sledovaný
hladký úsek
- H2 - větší z hodnot tvořících právě sledovaný
hladký úsek
(tento údaj můžeme ukládat pro přehlednost,
ale není nezbytný, neboť pokud platí
HLADKY=KONSTANTNI, není H2 definováno,
jinak H2=H1+1)
- MAX - délka maximálního dosud nalezeného hladkého
úseku
Na začátku výpočtu přečteme první číslo posloupnosti
a dosadíme do proměnných vhodné počáteční hodnoty odpovídající
tomu, že zatím známe první hladký úsek délky 1 tvořený prvním
číslem posloupnosti. Po přečtení každého čísla posloupnosti jsme
schopni s využitím zaznamenaných údajů aktualizovat hodnoty všech
zde uvedených proměnných. Po zpracování všech N čísel bude
výsledek uložen v proměnné MAX. Způsob zpracování každého čísla
je již zřejmý z programu.
program Hladky_Usek;
var N:integer; {počet čísel v posloupnosti}
Cislo:integer; {právě přečtené číslo}
Predchozi:integer; {předchozí číslo}
Index:integer; {pořadové číslo přečteného čísla}
Hladky:integer; {index začátku aktuálního hladkého
úseku čísel v posloupnosti}
Konstantni:integer; {index začátku aktuálního konstant.
úseku čísel v posloupnosti}
H1:integer; {menší z hodnot v aktuálním úseku}
H2:integer; {větší z hodnot v aktuálním úseku}
Max:integer; {délka maximálního hladkého úseku}
I:integer; {počítadlo přečtených čísel}
begin
read(N);
read(Cislo);
Index:=1; Hladky:=1; Konstantni:=1;
H1:=Cislo;
Max:=1;
for I:=2 to N do
begin
Predchozi:=Cislo;
read(Cislo);
Index:=Index+1;
if Hladky=Konstantni then {aktuální hladký úsek je zatím
tvořen čísly jedné hodnoty}
begin
if Cislo=H1+1 then
begin
H2:=Cislo;
Konstantni:=Index
end
else if Cislo=H1-1 then
begin
H2:=H1;
H1:=Cislo;
Konstantni:=Index
end
else if Cislo<>H1 then {konec hladkého úseku}
begin
if Index-Hladky>Max then Max:=Index-Hladky;
Hladky:=Index;
Konstantni:=Index;
H1:=Cislo
end
end
else {aktuální úsek je tvořen čísly H1 a H2, kde H2=H1+1}
begin
if (Cislo=H1) or (Cislo=H2) then
begin
if Cislo<>Predchozi then Konstantni:=Index
end
else {konec hladkého úseku}
begin
if Index-Hladky>Max then Max:=Index-Hladky;
if (Cislo=H2+1) and (Predchozi=H2) then
{v novém hladkém úseku se využije závěrečný úsek
předcházejícho hladkého úseku (úseky se překrývají)}
begin
H1:=H2;
H2:=Cislo;
Hladky:=Konstantni
end
else if (Cislo=H1-1) and (Predchozi=H1) then
{v novém hladkém úseku se využije závěrečný úsek
předcházejícho hladkého úseku (úseky se překrývají)}
begin
H2:=H1;
H1:=Cislo;
Hladky:=Konstantni
end
else
begin
H1:=Cislo;
Hladky:=Index
end;
Konstantni:=Index
end
end
end;
if Index-Hladky+1>Max then
{ošetření případu, že by maximální hladký úsek byl na
samém konci zadané posloupnosti čísel}
Max:=Index-Hladky+1;
writeln(Max)
end.
Popsaný postup řešení je pro každá vstupní data jistě
konečný, neboť počet opakování jediného cyklu v algoritmu je
pevně určen délkou vstupní posloupnosti čísel. Odtud také plyne
již zmíněná lineární časová složitost algoritmu.
Správnost řešení vyplývá ze způsobu zpracování čísel.
V každé posloupnosti čísel jistě existuje nějaký hladký úsek,
přinejmenším každé číslo samo tvoří jednoprvkový hladký úsek.
V konečné posloupnosti čísel je hladkých úseků jenom konečně
mnoho, takže některý (případně některé) z nich má maximální
délku. Tento úsek bude algoritmem jistě nalezen a jeho délka bude
uložena do výsledné proměnné MAX. V proměnné MAX se totiž
průběžné počítá maximum ze všech hodnot proměnné HLADKY, tj. ze
všech délek hladkých úseků v dané posloupnosti, a proměnná HLADKY
obsahuje v každém okamžiku délku co nejdelšího hladkého úseku,
který končí u právě přečteného čísla posloupnosti.
P-I-2
Úloha P-I-2 je jednou z klasických úloh teorie grafů.
Silniční síť představuje souvislý neorientovaný ohodnocený graf,
v němž vrcholy grafu odpovídají městům, hrany grafu silnicím
a ohodnocením hran jsou délky jednotlivých silnic. Úkolem potom
je nalézt minimální kostru daného grafu.
Různé algoritmy řešení této úlohy lze nalézt v každé
základní učebnici diskrétní matematiky nebo teorie grafů. Můžeme
použít například tzv. hladový algoritmus. Před jeho uvedením si
ještě připomeňme, že libovolnou kostru souvislého grafu získáme
vynecháním co možná největšího počtu hran tak, aby graf zůstal
souvislým. Graf o N vrcholech může mít více různých koster, každá
z nich obsahuje přesně N-1 hran. Z minimality počtu hran plyne,
že kostra neobsahuje žádné cykly (tzn. mezi každou dvojicí
vrcholů existuje jediná cesta). Minimální kostrou grafu nazýváme
takovou kostru grafu, v níž je součet ohodnocení hran minimální.
Graf může mít více různých minimálních koster, v takovém případě
hledáme jednu libovolnou z nich.
Při řešení úlohy postupujeme následovně. Všechny hrany
daného grafu uspořádáme podle jejich ohodnocení vzestupně. Na
pořadí hran stejné délky nezáleží. Potom postupně bereme
jednotlivé hrany od nejkratší k nejdelší a pro každou z nich
zkoumáme, zda ji můžeme zařadit do vytvářené kostry, tj. zda by
jejím přidáním do kostry nevzniknul v kostře cyklus. Pokud cyklus
nevznikne, hranu do kostry zařadíme, v opačném případě ji
vynecháme. Celý výpočet ukončíme ve chvíli, kdy jsme do kostry
již zařadili potřebných N-1 hran.
K efektivnímu naprogramování uvedeného algoritmu je třeba
zvolit vhodnou datovou reprezentaci. Graf je zadán seznamem hran
a jejich ohodnocením. Vzhledem k tomu, že potřebujeme všechny
hrany setřídit, použijeme této podoby i pro vnitřní reprezentaci
grafu v programu. Ve stejném tvaru, tj. jako seznam hran, budeme
vytvářet a ukládat (nebo přímo tisknout) i výslednou kostru.
Zbývá nám poslední a nejtěžší úkol: Potřebujeme mít možnost
během výpočtu snadným způsobem testovat, kterou hranu lze přidat
do vytvářené kostry. Bylo by dost pracné a pomalé procházet vždy
celý seznam hran již zařazených do kostry a nějak zkoumat, zda
společně s právě zpracovávanou hranou netvoří cyklus. Lepší je
vytvořit si nějakou pomocnou datovou strukturu, v níž bude
zaznamenáno, které vrcholy grafu jsou již pospojovány hranami
zařazenými do kostry. Postupně vytvářená kostra je nesouvislým
podgrafem původního grafu, přičemž každým zařazením další hrany
do kostry se o 1 sníží počet komponent souvislosti. Na začátku
výpočtu není v kostře ještě žádná hrana a každý vrchol grafu je
izolovaný (tvoří vlastní komponentu souvislosti). Po zařazení
všech N-1 hran do kostry bude pospojováno všech N vrcholů do
souvislého grafu bez cyklů.
Evidenci průběžně vytvářených komponent souvislosti (tj.
skupin již pospojovaných vrcholů) je možné programově realizovat
různými způsoby. Jednoduchým a názorným řešením (i když
z hlediska efektivity ne tím zcela nejlepším) je použít pomocné
jednorozměrné pole velikosti N indexované čísly vrcholů od 1 do
N. V tomto poli bude pro každý vrchol uloženo číslo komponenty,
do níž momentálně náleží. Při zpracování každé další hrany pak
snadno otestujeme, zda její krajní vrcholy jsou již v téže
komponentě souvislosti. Pokud ano, zkoumanou hranu vynecháme,
v opačném případě ji zařadíme do kostry. Při zařazení nové hrany
do kostry musíme samozřejmě opravit také naši evidenci
pospojovaných vrcholů, neboť tím zároveň dojde k propojení dvou
dosud samostatných komponent souvislosti. Všem vrcholům obou
těchto komponent musíme proto přiřadit stejné číslo komponenty
souvislosti (například jedno z čísel právě spojovaných
komponent).
program Minimalni_Kostra;
const MaxN=100; {maximální počet měst}
MaxSilnic=1000; {maximální počet silnic}
type Silnice=record
M1,M2,Delka:integer {čísla měst, délka silnice}
end;
var Sit:array[1..MaxSilnic] of Silnice; {silniční síť}
Komponenta:array[1..MaxN] of integer; {čísla komponent}
N:integer; {počet měst}
S:integer; {počet silnic}
PomSilnice:Silnice; {pomocné pro třídění}
K1,K2:integer; {čísla komponent}
I,J,K:integer;
begin
{Vstup dat:
write('Počet měst: ');
readln(N);
writeln('Silnice: ODKUD KAM DÉLKA');
S:=0;
while not eof do
begin
S:=S+1;
with Sit[S] do read(M1,M2,Delka)
end;
writeln;
writeln('Vybrané silnice:');
{Setřídění silnic v poli Sit[1..S] podle délky od nejkratší
k nejdelší. Pro jednoduchost je zde použit algoritmus
přímého výběru s kvadratickou časovou složitostí, třídění
lze ovšem provést jiným, efektivnějším algoritmem}
for I:=1 to S-1 do
begin
K:=I;
for J:=I+1 to S do
if Sit[J].Delka<Sit[K].Delka then K:=J;
{nalezení nejkratší silnice}
if K<>I then
begin {prohození silnic na pozicích I a K}
PomSilnice:=Sit[K];
Sit[K]:=Sit[I];
Sit[I]:=PomSIlnice
end
end;
{Nalezení minimální kostry:}
for I:=1 to N do Komponenta[I]:=I;
I:=0; {číslo zkoumané hrany}
K:=0; {počet hran v kostře}
while K<N-1 do
begin
I:=I+1;
K1:=Komponenta[Sit[I].M1];
K2:=Komponenta[Sit[I].M2];
if K1<>K2 then {silnici Sit[I] zařadit do kostry}
begin
K:=K+1;
writeln(Sit[I].M1:5,Sit[I].M2:5);
for J:=1 to N do
if Komponenta[J]=K2 then Komponenta[J]:=K1
{spojení komponent, do nichž patří krajní vrcholy}
end
end
end.
Důkaz správnosti uvedeného algoritmu je matematicky trochu
obtížnější. Postup výpočtu je jistě konečný, neboť nejprve se
setřídí podle velikosti konečně mnoho hran a potom se vytváří
kostra postupným zkoumáním jednotlivých hran. Počet kroků tohoto
procesu je tedy omezen počtem hran. Složitost testování každé
hrany, zda ji můžeme přidat do kostry, je konstantní díky pomocné
evidenci komponent souvislosti, přidání hrany do kostry pak
vyžaduje projít pomocným polem, tj. provést výpočet délky
rovnající se počtu vrcholů. Odtud také přímo plyne časová
složitost algoritmu. Označíme-li počet hran v grafu (tj. počet
silnic) H, setřídění H hodnot podle velikosti můžeme provést
jednoduchým třídicím algoritmem složitosti O(H
2), jako jsme to
provedli v našem programu, nebo lepším třídicím algoritmem,
přinejlepším však s časovou složitostí O(H log H). Vlastní
hladový algoritmus potom vyžaduje maximálně H kroků, z nichž
každý může mít složitost N (kde N je počet vrcholů grafu, tj.
počet měst).
Z uvedeného postupu řešení je zřejmé, že algoritmus vyhledá
nějakou kostru zadaného grafu. Postupně totiž do vytvářené kostry
zařazuje jen takové hrany, jejichž přidáním nevznikne cyklus,
a zařadí jich tam maximální možný počet N-1. Zbývá ukázat, že
nalezená kostra je skutečně minimální. Hrany tvořící nalezenou
kostru pro potřeby důkazu označíme e1,
e2,..., ek, kde k=N-1,
v pořadí v jakém byly vybírány, tzn. podle velikosti od nejmenší
k největší. Každý graf má jistě nějakou minimální kostru (může
jich mít i více různých), neboť má konečně mnoho koster a z nich
lze vybrat kostru s minimálním ohodnocením. Uvažujme jednu
libovolnou minimální kostru, uspořádejme její hrany podle
velikosti od nejmenší k největší a označme je po řadě f1,
f2, ..., fk.
Dokážeme, že pro každé i od 1 do k platí, že
ohodnocení hrany eimusí být menší nebo rovno ohodnocení hrany
fi. Odtud již přímo plyne, že součet ohodnocení
všech hran e1,
e2, ..., ek není větší než součet ohodnocení hran
f1,
f2, ..., fk a
že tedy kostra nalezená naším algoritmem je minimální.
Důkaz provedeme sporem. Předpokládejme, že pro nějaké i mezi
1 a k platí, že ohodnocení eije ostře větší než ohodnocení hrany
fi. Jistě i>1, neboť za e1jsme v algoritmu
vzali hranu
s minimálním ohodnocením. Uvažujme množiny hran
Ei-1={e1, ...,ei-1} a
Fi={f1,...,fi}. Obě tyto množiny hran jsou
podmnožinami nějakých koster a proto neobsahují žádný cyklus.
K dokončení důkazu stačí ukázat, že v množině Fiexistuje taková
hrana f, že Ei-1U{f} neobsahuje cyklus.
Všechny hrany obsažené
v množině Fi mají totiž ostře
menší ohodnocení než hrana ei(to
plyne z předpokladu našeho důkazu a z uspořádání množiny Fi),
tedy i hrana f má ohodnocení menší než hrana ei. Popsaný
algoritmus nalezení minimální kostry by tudíž jako v pořadí
i-tou zařadil do vytvářené kostry hranu f místo hrany ei, což je
spor.
Existence hrany f, která je prvkem Fi, takové, že
Ei-1U{f} neobsahuje
cyklus, přímo vyplývá ze skutečnosti, že množina Fi obsahuje
o jednu hranu více než množina Ei-1. Uvážíme-li souvislé
komponenty grafu určené množinou hran Ei-1 (žádná z těchto
komponent neobsahuje cyklus), jistě existuje hrana z Fi
spojující dvě různé komponenty - a to je hledaná hrana f.
V opačném případě by totiž každá hrana z Fi musela spojovat
dvojici vrcholů téže komponenty, a protože v Fi je o jednu hranu
více než v Ei-1, nutně by tak něktará skupina hran
z Fi vytvořila cyklus.
P-I-3
- Nejprve se pokusíme hlouběji proniknout do průběhu uvedené hry
tím, že budeme sledovat situaci pro malé počty zápalek zbývající
na hromádce:
- zbývá 0 hráč na tahu prohrává (nemůže brát)
- zbývá 1 hráč na tahu prohrává (nemůže brát)
- zbývá 2 hráč na tahu prohrává (nemůže brát)
- zbývá 3 hráč na tahu vyhrává (vezme 3)
- zbývá 4 hráč na tahu vyhrává (vezme 3)
- zbývá 5 hráč na tahu vyhrává (vezme 3 nebo 5)
- zbývá 6 hráč na tahu vyhrává (vezme 5)
- zbývá 7 hráč na tahu vyhrává (vezme 5)
- zbývá 8 hráč na tahu prohrává (odebráním 3 nebo 5 se
soupeř dostane do pozice s vyhrávajícím tahem)
Po vyšetření dalších pozic zjistíme, že vyhrané a prohrané
pozice se pravidelně opakují (s periodou délky 8). Na základě
provedeného rozboru hry můžeme vyslovit následující hypotézu.
Je-li N tvaru 8k, 8k+1 nebo 8k+2, začínající hráč nemůže proti
dobrému soupeři vyhrát. Pro ostatní hodnoty N má naopak
začínající hráč jisté vítězství, bude-li se držet vítězné
strategie. Pro N tvaru 8k+3 nebo 8k+4 musí brát 3 zápalky, pro
N tvaru 8k+6 nebo 8k+7 musí brát 5 zápalek, je-li N tvaru 8k+5,
může hrát libovolně.
Správnost vyslovené hypotézy musíme ovšem ještě pořádně
dokázat. Je-li počáteční hodnota N tvaru 8k+3, 8k+4, 8k+5, 8k+6
nebo 8k+7 a zahrajeme-li svůj tah podle uvedené strategie,
dostane se náš soupeř vždy do situace, že má brát z hromádky
obsahující 8k, 8k+1 nebo 8k+2 zápalek. Ať zahraje jakkoliv, po
jeho tahu zbyde na hromádce opět počet zápalek tvaru 8k+3, 8k+4,
8k+5, 8k+6 nebo 8k+7 (samozřejmě pro hodnotu k o 1 menší než
dříve). Tak se situace opakuje pro stále se zmenšující hodnoty k,
každým tahem naším a soupeřovým se k sníží o 1. Po konečném počtu
tahů bude proto k nulové a soupeř bude na tahu v pozici s 0, 1
nebo 2 zápalkami na hromádce, což znamená jeho prohru.
Naopak, pro počáteční počet zápalek N tvaru 8k, 8k+1 nebo
8k+2 vede jakýkoliv tah začínajícího hráče do pozice s 8k+3,
8k+4, 8k+5, 8k+6 nebo 8k+7 zápalkami na hromádce (hodnota k je
zde opět o 1 menší) a bude-li se pak náš soupeř držet uvedené
strategie, má jisté vítězství ve hře.
- Úlohu řešíme zcela analogicky jako úlohu a). Na základě
rozboru situací s malým počtem zápalek zbývajících na hromádce
dojdeme k následující hypotéze. Je-li na hromádce počet zápalek
tvaru 10k, 10k+1, 10k+2 nebo 10k+6, začínající hráč prohraje,
pokud bude jeho soupeř hrát dobře. Pro ostatní hodnoty N má
naopak hráč na tahu jisté vítězství při dodržování této vítězné
strategie: pro N tvaru 10k+3, 10k+4 a 10k+5 musí vzít 3 zápalky,
pro N tvaru 10k+7, 10k+8 a 10k+9 bere 7 zápalek. Hypotézu
dokážeme stejnou úvahou jako v řešení úlohy a).
P-I-4
Většinu početních postupů, které jsme se učili na základní
škole provádět, lze konečným sekvenčním strojem přímočaře
modelovat. Řešení úloh b),d),e),f) by vás proto mělo napadnout
poměrně rychle.
- Ačkoli čísla podle velikosti porovnáváme častěji odzadu (tak
totiž máme zaručeno, že budeme porovnávat cifry odpovídajících si
řádů), existuje i jednoduchý algoritmus, jak je porovnávat
odpředu. Výsledek stroj ohlásí až po dočtení vstupních sledů,
během výpočtu se přitom musíme připravit na dvě možné situace:
- oba zápisy budou stejně dlouhé. V tom případě si potřebujeme
pamatovat rozdíl na prvním místě zpředu, kde se zápisy lišily.
- oba zápisy budou různě dlouhé. Pak můžeme o větším čísle
rozhodnout pouze na základě délky zápisu. Není podstatné, jaké
číslice obsahovaly oba zápisy, a tedy z průběhu výpočtu si
v tomto případě nepotřebujeme nic pamatovat.
Která z těchto možností nastává, však zjistíme až po
přečtení kratšího z obou čísel (resp. obou). Během výpočtu proto
musíme rozlišovat 3 možné situace:
- zápisy se zatím nelišily
- na prvním místě, kde se lišily, bylo první číslo větší
- na prvním místě, kde se lišily, bylo druhé číslo menší
Navržený stroj proto bude mít stavy N,A,B, které budou přesně
odpovídat výše uvedeným situacím. Pro potřeby ukončení budeme
ještě potřebovat další stav K (pro něj nebude definováno žádné
přechodové pravidlo). Počátečním stavem je N, přechodová funkce
je dána tabulkou. Řádky v tabulce jsou označeny původním stavem,
sloupce jsou označeny čteným symbolem z prvního resp. druhého
sledu. Údaj před lomítkem je nový stav, za lomítkem je uveden
vypisovaný znak.
| stav | čtené symboly |
| 0 0 | 0 1 | 1 0 | 1 1 | 0 _ | 1 _ | _ 0 | _ 1 | _ _ |
| N | N/_ | B/_ | A/_ | N/_ | K/P | K/P | K/D | K/D | K/S |
| A | A/_ | A/_ | A/_ | A/_ | K/P | K/P | K/D | K/D | K/P |
| B | B/_ | B/_ | B/_ | B/_ | K/P | K/P | K/D | K/D | K/D |
- Porovnávat zápisy čísel odzadu je běžná operace. Podobně jako
v úloze a) si v průběhu výpočtu potřebujeme pamatovat, zda se již
zápisy čísel lišily. Pokud ano, musíme si pamatovat, které
z čísel obsahuje vyšší cifru na místě, kde byla odlišnost
zjištěna naposled. Pamatujeme si tedy pouze odlišnost v dosud
nejvyšším testovaném řádu, odlišnosti v nižších řádech už na
výsledek porovnání nemohou mít vliv.
Stroj bude mít 4 stavy:
- N..zápisy čísel se zatím nelišily
- A..první číslo obsahovalo větší cifru
- B..druhé číslo obsahovalo větší cifru
- K..pomocný stav pro ukončení výpočtu.
Počáteční stav je N.
| stav | čtené symboly |
| 0 0 | 0 1 | 1 0 | 1 1 | 0 _ | 1 _ | _ 0 | _ 1 | _ _ |
| N | N/_ | B/_ | A/_ | N/_ | K/P | K/P | K/D | K/D | K/S |
| A | A/_ | B/_ | A/_ | A/_ | K/P | K/P | K/D | K/D | K/P |
| B | B/_ | B/_ | A/_ | B/_ | K/P | K/P | K/D | K/D | K/D |
- Úloha není konečným sekvenčním strojem řešitelná. Uvažujme
výpočty nad vstupními sledy o délce k cifer
1011.....11 a 1000.....01
a 1011.....11 a 1000.....00.
Do doby, než stroj ze vstupních sledů přečte poslední cifry, může
na výstup zapsat pouze 10, protože další cifra výstupu závisí na
posledních cifrách vstupů. Po dočtení vstupů pak bude muset
vypsat ještě k-1 dalších cifer (nul či jedniček). V případě, kdy
délka vstupů k je větší než počet vnitřních stavů stroje, si
stroj není schopen pomocí vnitřních stavů zapamatovat, kolik
znaků má po přečtení posledních cifer ze vstupu ještě vypsat.
- Jde o běžné sčítání čísel v poziční soustavě. Pro výpočet
stačí dva stavy, P (je přenos z nižších řádů) a B (bez přenosu).
Počátečním stavem je B.
| stav | čtené symboly |
| 0 0 | 0 1 | 1 0 | 1 1 | 0 _ | 1 _ | _ 0 | _ 1 | _ _ |
| B | B/0 | B/1 | B/1 | P/0 | B/0 | B/1 | B/0 | B/1 | - |
| P | B/1 | P/0 | P/0 | P/1 | B/1 | P/0 | B/1 | P/0 | B/1 |
- Řešení části e) lze získat jednoduchou modifikací stroje
z řešení úlohy f).
- Stroj bude simulovat písemné
dělení. Postupujeme od nejvyšších řádů k nižším. Pomocí vnitřních
stavů si pamatujeme dosavadní zbytek při dělení (N nula, J jedna,
D dva). V jednom kroku výpočtu "sepíšeme" další cifru, zapíšeme
jednu cifru do podílu a určíme nový dílčí zbytek. Po dočtení
vstupního čísla do konce bude vypsán podíl, zbytek bude určen
vnitřním stavem. Je třeba si dát pozor na to, že zápis výsledku
musí začínat jedničkou, ale tuto nepatrnou technickou komplikaci
snadno vyřešíme: přidáme nové dva stavy X,Y. Stroj má celkem pět
stavů, počáteční stav je X.
| stav | čtený symbol |
| 0 | 1 | _ |
| X | - | Y/_ | - |
| Y | D/_ | N/1 | - |
| N | N/0 | J/0 | - |
| J | D/0 | N/1 | - |
| D | J/1 | D/1 | - |