Začneme prohledáváním grafu do hloubky z libovolného zvoleného vrcholu. Jestliže při tomto prohledávání navštívíme všechny vrcholy, našli jsme šéfa - je jím vrchol, kterým jsme prohledávání začali. V opačném případě pokračujeme tak, že zahájíme nové prohledávání do hloubky v jednom z vrcholů, které jsme dosud nenavštívili (dříve navštívené vrcholy grafu přitom necháme označené jako navštívené). To opakujeme tak dlouho, dokud nenavštívíme všechny vrcholy našeho grafu. Nechť r je vrchol, v němž jsme zahájili poslední prohledávání.
Tvrzení: Má-li náš graf aspoň jednoho šéfa, potom vrchol r je šéfem.
Důkaz: Předpokládejme, že náš graf má šéfa a že vrchol r není šéfem. Nechť je šéfem vrchol s. Musíme uvažovat dvě možnosti:
program Agenti;
const MAXM = 10000;
MAXN = 100;
var rozkazuje: array [1..MAXM] of integer;
ind_od, ind_do: array [1..MAXN] of integer;
{agent i+6 rozkazuje agentům rozkazuje[ind_od[i]]...rozkazuje[ind_do[i]]}
N: integer;
navstiven: array [1..MAXN] of boolean;
procedure Nacti;
var i,M,agent: integer;
begin
write('Počet agentů:'); readln(N);
M:=0;
for i:=1 to N do begin
write('Agent ',i+6,' rozkazuje: (ukonči -1)');
ind_od[i]:=M+1;
read(agent);
while (agent>0) do begin
M:=M+1;
rozkazuje[M]:=agent-6;
read(agent);
end;
ind_do[i]:=M;
end;
end; {procedure Nacti}
procedure Prohledej(i: integer);
var j: integer;
begin
if not navstiven[i] then begin
navstiven[i]:=true;
for j:=ind_od[i] to ind_do[i] do begin
Prohledej(rozkazuje[j]);
end;
end;
end; {procedure Prohledej}
var i,posledni: integer;
je_sef: boolean;
begin
Nacti;
for i:=1 to N do navstiven[i]:=false;
for i:=1 to N do begin
if not navstiven[i] then begin
posledni:=i;
Prohledej(i);
end;
end;
for i:=1 to N do navstiven[i]:=false;
Prohledej(posledni);
je_sef:=true;
for i:=1 to N do je_sef:= je_sef and navstiven[i];
if je_sef then
writeln('Šéfem je agent ', posledni+6)
else
writeln('Žádný agent není šéfem');
end. {program Agenti}
Pomůžeme si tím, že hodnoty, které nám budou přicházet, vložíme nejen do haldy, ale také do fronty. Mezi těmito dvěma datovými strukturami si budeme udržovat vzájemné odkazy, abychom v každém okamžiku dokázali o každém prvku fronty říci, kde je v haldě, a naopak.
Když tedy přijde nová hodnota, vložíme ji do haldy a na konec fronty. Následně ze začátku fronty odstraníme nejstarší hodnotu, pomocí odkazu ji najdeme v haldě a odstraníme ji také odtamtud. Nyní už jen vypíšeme hodnotu uloženou v kořeni haldy.
Obě operace s haldou mají časovou složitost O(log K),
zbývající operace dokážeme provést v konstantním čase. Paměť spotřebovaná
haldou i frontou je O(K). #include <stdio.h>
#define MAXK 100047
#define INFTY 1e10
#define SWAP(x,y) pom=(x); (x)=(y); (y)=pom
typedef struct { double val; int ptr; } tZaznam;
int K; // ze zadání
tZaznam H[MAXK],Q[MAXK]; // halda a fronta
int qs; // začátek fronty
tZaznam pom;
void init(void) { // naplníme haldu i frontu "nekonečně" velkými hodnotami
int i;
qs=0; H[0].val=-10000;
for (i=0;i<K;i++) { Q[i].val=H[i+1].val=INFTY; Q[i].ptr=i+1; H[i+1].ptr=i; }
}
void bubbleup(int idx) { // bublej prvkem nahoru v haldě
int next=idx,p1,p2;
if (H[idx/2].val > H[idx].val) next=idx/2;
if (next!=idx) {
p1=H[idx].ptr; p2=H[next].ptr;
SWAP(H[idx],H[next]);
Q[p1].ptr=next; Q[p2].ptr=idx;
bubbleup(next);
}
}
void bubbledown(int idx) { // bublej prvkem dolů v haldě
int next=idx,p1,p2;
if (2*idx<=K) if (H[2*idx ].val < H[next].val) next=2*idx;
if (2*idx+1<=K) if (H[2*idx+1].val < H[next].val) next=2*idx+1;
if (next!=idx) {
p1=H[idx].ptr; p2=H[next].ptr;
SWAP(H[idx],H[next]);
Q[p1].ptr=next; Q[p2].ptr=idx;
bubbledown(next);
}
}
int main(void) {
int delptr;
double x;
scanf("%d ",&K); init();
while (1) {
scanf("%lf ",&x); if (x==-1000) break;
delptr=Q[qs].ptr; // najdeme hodnotu, kterou je třeba vymazat z haldy
H[delptr].val=H[K].val; H[delptr].ptr=H[K].ptr; Q[H[K].ptr].ptr=delptr;
K--; bubbledown(delptr); bubbleup(delptr); K++; // smažeme a upravíme haldu
Q[qs].val=H[K].val=x; Q[qs].ptr=K; H[K].ptr=qs; bubbleup(K); // vložíme
qs= (qs+1)%K;
printf("%g\n",H[1].val);
}
return 0;
}
Další alternativní řešení, na které přišel Vladan Majerech,
nepoužívá haldu, ale vystačí si s lineárním seznamem. Myšlenka je
následující:
V seznamu si budeme uchovávat některé
z posledních K teplot. Ze seznamu vyřadíme ty teploty, za
kterými je v seznamu nižší teplota (tedy ty teploty,
které jsou vyšší než nějaká teplota, která přišla později). Seznam zřejmě obsahuje
všechny teploty, které by se mohli stát později nejmenší v daném období.
Jak to tedy udělat? Teploty si budeme ukládat do seznamu tak, jak přicházejí a u každé z nich si zapamatujeme čas, kdy přišla, abychom jí potom mohli ze seznamu vymazat. Pokaždé, když přidáváme novou teplotu, nejprve odebereme všechny prvky seznamu s teplotou menší než je nová teplota. Novou teplotu pak přidáme na konec seznamu. Protože nově přidávaná teplota je vždy větší než všechny ostatní teploty v seznamu, budou teploty v seznamu srovnány od nejmenší po největší. Lehce nahlédneme, že jsou teploty srovnány také podle času, kdy přišli, protože nově příchozí teploty dáváme vždy na konec. Díky tomu je nejstarší teplota první teplotou v seznamu a můžeme ji lehce odebrat, jakmile nebude v měřeném období. Samozřejmě tato teplota je také nejmenší teplotou v seznamu, kterou po každém přidání nové teploty vypisujeme. To je vše co potřebujeme.
Nyní se podívejme na časovou složitost. Každý prvek je
jednou přidán a jednou odebrán. Celková časová složitost s n teplotami je O(n). Ale v nejhorším případě, když
přidáváme novou teplotu odebereme až O(K) teplot. Pokud ovšem spojový seznam
nahradíme polem můžeme vylepšit časovou složitost na O(log K). Aby se
nám teploty do pole vešly, musíme ho "zacyklit". To znamená, že po K-tém prvku
bude následovat nultý prvek. Tohoto efektu dosáhneme tím, že se všemi indexi
budeme počítat modulo K + 1 (pole je indexované od 0 a má K + 1 prvků).
Protože jsou teploty seřazené použijeme k vyhledání hranice odebraných prvků
algoritmus půlení intervalu. Ten hledá hodnotu x v seřazeném poli A od indexu L do indexu P. Vezme prostřední prvek
A[(L + P) mod 2] a porovná ho s x. Jesliže je x
větší hledáme x v intervalu (L + P) mod 2 až P, ve
druhém případě hledáme v intervalu L až (L + P) mod 2. Protože je pole A zacyklené, může se stát, že P < L. V tom
případě musíme posunout P o K + 1 a prostřední prvek dostaneme jako A[((L + P + K + 1) div 2) mod (K + 1)].
Nyní máme index hranice prvků, za který přidáme novou
teplotu.
Pro milovníky algoritmů tu máme ještě jedno řešení od Zdeňka Dvořáka, které i v nejhorším případě zpracuje jednu teplotu ze vstupu v čase O(1).
Algoritmus bude pracovat v několika fázích. V každé fázi postupně načte a zpracuje K/2 teplot ze vstupu (pro jednoduchost předpokládejme, že K je sudé). V průběhu výpočtu si budeme vytvářet pomocná pole délky K/2. V okamžiku, kdy bude pomocné pole již vytvořeno, tak u každého prvku pole bude uloženo kromě jeho hodnoty i nejmenší prvek uložený v poli za tímto prvkem.
V i-té fázi budeme mít již vytvořeno pole pro hodnoty z (i-2)-hé fáze, pro teploty z (i-1)-ní fáze budeme pole vyvtvářet a hodnoty z i-té fáze si budeme prozatím jen ukládat. Navíc budeme mít vždy k dispozici minimum ze všech teplot načtených v (i-1)-ní fázi a v i-té fázi.
Po načtení k-té teploty v i-té fázi, 1<=k<=K/2, algoritmus nejdříve uloží k-tou teplotu do pomocného pole a upraví hodnotu minima teplot načtených v i-té fázi, je-li to potřeba. Poté spočte teplotu, kterou má vystoupit jako minimum z následujících tří hodnot: minimum z posledních (K/2-k) teplot v poli z (i-2)-hé fáze (toto minimum máme předpočítané), minimum teplot načtených v (i-1)-ní fázi a minimum dosud načtených teplot v i-té fázi. Nakonec spočte minimum posledních k prvků v poli z (i-1)-ní fáze jako minimum (K/2-k+1)-ního prvku a minima z posledních k-1 prvků (které spočítal po načtení předchozí teploty).
Na konci každé fáze, algorimus zamění pomocná pole (všimněte si, že na konci každé fáze právě dopočítáme pomocné pole pro hodnoty z předchozí fáze).
Časová složitost našeho algoritmu je O(1) pro zpracování jedné teploty v nejhorším případě a paměťová složitost je O(K).
Zásobník si můžeme simulovat v jednom registru (s pomocí druhého). Písmena a, b, c budou odpovídat číslům 1, 2, 3. Číslo uložené v registru R1 bude představovat náš zásobník - když ho zapíšeme v poziční soustavě o základu 4, jednotlivé cifry budou představovat vložené hodnoty (cifra na místě jednotek bude naposledy vložená hodnota). Například když do prázdného zásobníku vložíme postupně písmena a, c, b, a, bude v R1 hodnota a * 43 + c * 42 + b * 4 + a = 1 * 43 + 3 * 42 + 2 * 4 + 1 = 64 + 48 + 8 + 1 = 121.
Jak ale s takovýmto registrem-zásobníkem pracovat? Vložit novou hodnotu x je jednoduché - pomocí registru R2 vynásobíme obsah R1 čtyřmi a potom ho x-krát zvětšíme o 1. Rovněž odebrání naposledy vložené hodnoty není těžké - je to přesně opačná operace. Vydělíme obsah registru R1 čtyřmi. Zbytek po dělení je naposledy vložená hodnota, podíl (který dostaneme v R2) je obsah zásobníku bez této hodnoty.
Nyní můžeme již přikročit k řešení zadané úlohy. Jednou možností je simulovat (pomocí dvou zásobníků) frontu, v níž si udržujeme ta písmena, jejichž pár jsme ještě neviděli. Toto řešení je poměrně komplikované a jeho základní myšlenka spočívá v tom, že přicházející písmena vkládáme do prvního zásobníku, písmena na kontrolu vybíráme z druhého zásobníku a vždy, když se nám druhý zásobník vyprázdni, do něj přesypeme obsah prvního zásobníku.
Ukážeme si raději jednodušší řešení. Budeme opět
používat dva zásobníky. Do prvního budeme vkládat všechna přicházející malá
písmena (jako hodnoty 1,2,3), do druhého velká (také jako hodnoty 1,2,3). Po
dočtení vstupního slova jednoduše porovnáme obsahy obou zásobníků. Vstupní
slovo bylo správné právě tehdy, je-li jejich obsah stejný. To již snadno
ověříme. var vstup: char;
i,co: byte;
begin
Read(vstup);
while vstup<>'$' do begin
if vstup>='a' then begin
if vstup='a' then co:=1;
if vstup='b' then co:=2;
if vstup='c' then co:=3;
while not Zero(R1) do begin Dec(R1); for i:=1 to 4 do Inc(R0); end;
while not Zero(R0) do begin Dec(R0); Inc(R1); end;
while co>0 do begin Inc(R1); co:=co-1; end;
end else begin
if vstup='A' then co:=1;
if vstup='B' then co:=2;
if vstup='C' then co:=3;
while not Zero(R2) do begin Dec(R2); for i:=1 to 4 do Inc(R0); end;
while not Zero(R0) do begin Dec(R0); Inc(R2); end;
while co>0 do begin Inc(R2); co:=co-1; end;
end;
Read(vstup);
end;
while not Zero(R1) and not Zero(R2) do begin Dec(R1); Dec(R2); end;
if Zero(R1) and Zero(R2) then Accept;
end.
Použijeme myšlenku, kterou znáte již z řešení domácího kola. Zakódujeme obsah všech tří registrů do jediného, druhý registr budeme používat jako pomocný při práci s prvním. Místo tří registrů s obsahem a, b, c budeme mít tedy jeden registr Q1 s obsahem 2a 3b 5c. Při simulování každé operace použijeme Q2 jako pomocný registr. Na začátku i po provedení každé operace v něm bude uložena nula.
Operaci Inc(Rx) v původním programu nahradíme tím, že obsah nového registru Q1 vynásobíme 2, 3, resp. 5. Podobně příkaz Dec(Rx) nahradíme příslušným dělením.
Nahradit podmínku Zero(Rx) bude trochu komplikovanější. Během vyhodnocování nějaké složené podmínky totiž nemůžeme provádět operace s registry - zjistit, zda je v Rx nula, tedy musíme před vyhodnocením příslušné podmínky. Navíc drobné problémy způsobí skutečnost, že tato podmínka se může vyskytovat i v podmínce pro příkaz while, kde bude vyhodnocována při každé iteraci (nejen před prvním voláním while), a že v jedné podmínce můžeme testovat více proměnných.
Definujme si "makro" (kus výpočtu) SpocitejZ, které bude fungovat následovně: Pro každý registr Rx nastaví proměnnou zx tak, aby v ní byla kladná hodnota právě tehdy, je-li v Rx nula, jinak bude zx=0. Výpočet makra začne tím, že obsah Q1 vydělíme příslušným prvočíslem, přičemž si (v proměnné zx) zapamatujeme zbytek, který jsme dostali při tomto dělení. Vrátíme obsah Q1 do původního stavu. Jestliže obsah Q1 byl dělitelný příslušným prvočíslem (tedy neplatí Zero(Rx)), bude v zx nula, jinak tam bude kladný zbytek. Výraz Zero(Rx) má tedy v tomto okamžiku stejnou pravdivostní hodnotu jako výraz (zx>0).
Každý příkaz "if P then příkazy;" nahradíme makrem SpocitejZ a příkazem "if P' then příkazy;", kde podmínka P' vznikla z P tak, že jsme v ní místo všech výskytů výrazu Zero(Rx) dali výraz (zx>0).
Každý příkaz "while P do
příkazy;" nahradíme voláním makra SpocitejZ před cyklem a na konci každé
iterace, tedy následujícím kusem výpočtu: "SpocitejZ;
while P' do begin příkazy; SpocitejZ; end;" Nová "makra" Inc, Dec (jimiž
nahradíme každý výskyt těchto příkazů v původním programu) a SpocitejZ (na
simulaci Zero) budou tedy vypadat následovně: var x,y,z1,z2,z3,i: byte; {nové proměnné, které nebyly v původním programu}
{ Inc(Rx) - x je v proměnné x, předpokládáme, že $Q2=0$ }
if x=1 then y:=2 else if x=2 then y:=3 else y:=5;
{vynásobíme obsah Q1 čislem y}
while not Zero(Q1) do begin
Dec(Q1);
for i:=1 to y do Inc(Q2);
end;
while not Zero(Q2) do begin
Dec(Q2); Inc(Q1);
end;
{ Dec(Rx) - x je v proměnné x, předpokládáme, že $Q2=0$ }
if x=1 then y:=2 else if x=2 then y:=3 else y:=5;
z:=0;
{vydělíme obsah Q1 číslem y}
while not Zero(Q1) do begin
Dec(Q1);
if Zero(Q1) then begin z:=1; break; end; {v Rx byla nula}
for i:=1 to y-1 do Dec(Q1);
Inc(Q2);
end;
if z=1 then begin
{obnovíme původní stav Q1 - nic se nemění}
while not Zero(Q2) do begin
Dec(Q2); for i:=1 to y do Inc(Q1);
end;
Inc(Q1);
end else begin
{přesuneme do Q1 podíl}
while not Zero(Q2) do begin
Dec(Q2); Inc(Q1);
end;
end;
{ SpocitejZ - předpokládáme, že $Q2=0$ }
{nejdříve chceme spočítat z1, čili budeme dělit dvěma}
y:=2;
{vydělíme obsah Q1 číslem y}
z1:=0;
while not Zero(Q1) do begin
Dec(Q1);
z1:=z1+1;
if z1=y then begin z1:=0; Inc(Q2); end;
end;
{vrátíme zpět původní hodnotu do Q1}
while not Zero(Q2) do begin
Dec(Q2); for i:=1 to y do Inc(Q1);
end;
for i:=1 to z1 do Inc(Q1);
{a v proměnné z1 máme hledaný zbytek}
{opakujeme totéž pro z2, y:=3 a z3, y:= 5}
Uvědomte si, že aplikováním tohoto postupu na program používající k>3 registrů dostaneme program používající k-1 registrů. Proto platí poměrně překvapivý výsledek: K libovolné úloze, kterou dokážeme řešit na registrovém počítači, existuje program, jemuž na její řešení stačí dva registry.