V praktických úlohách P-I-1 a P-I-3 je třeba k řešení připojit odladěný program zapsaný v jazyce Pascal, C nebo C++. Program se odevzdává v písemné formě (jeho výpis je tedy součástí řešení) i na disketě, aby bylo možno otestovat jeho funkčnost. Slovní popis řešení musí být ovšem jasný a srozumitelný i bez toho, že by bylo nutno nahlédnout do zdrojového textu programu.
V úloze P-I-2 se požaduje slovní popis zvoleného postupu řešení včetně použitých programů, na disketu uložte jako přílohu k řešení této úlohy pouze výsledný textový soubor s nalezeným řetězcem.
V úloze P-I-4 je třeba nakreslit také schémata programů pro Minského registrové stroje.
Majitelé továrny chtějí výrobu zorganizovat tak, aby bylo možné dokončit první nový výrobek v co nejkratším čase. V továrně lze současně provádět libovolný počet výrobních operací, každou operaci je však možné zahájit až po dokončení všech jí předcházejících operací. Jinak mohou být jednotlivé výrobní operace prováděny v jakémkoliv pořadí. Můžete předpokládat, že výroba podle zadaného technologického plánu je možná.
Napište program, který ze vstupního textového souboru TOVARNA.IN
přečte technologický plán výroby nového výrobku a do výstupního
textového souboru TOVARNA.OUT
vypíše nejkratší čas,
v jakém lze vyrobit první nový výrobek.
Soubor TOVARNA.IN
obsahuje na prvním řádku počet výrobních
operací N (N <= 100). Na dalších N řádcích se nacházejí
informace o jednotlivých výrobních operacích, na i-tém řádku
o operaci číslo i. Informace o každé výrobní operaci se skládá
z několika čísel oddělených mezerou. První číslo udává, jak dlouho
operace trvá, dále následují čísla předcházejících operací.
Řádek je ukončen číslem -1. Pro zhotovení nového výrobku je třeba
vykonat všech N zadaných výrobních operací. Jednotlivé operace je
možné provádět v libovolném pořadí, každá operace však může být
zahájena až po dokončení všech jí předcházejících operací.
Soubor TOVARNA.OUT
bude obsahovat jediný řádek, na kterém bude
zapsán čas, za jak dlouho od zahájení výroby lze dokončit první
nový výrobek.
TOVARNA.IN
TOVARNA.OUT
RETEZEC.TXT
.
Jedna agentura chce zjistit, která ze stran v zemi má nejvyšší a která nejnižší preference. Bude postupovat tak, že pro různé dvojice stran provede výše popsaný průzkum veřejného mínění. Chce přitom vykonat co nejméně průzkumů.
Napište program, který bude řídit činnost agentury. Tento program nejprve přečte počet stran N (1 <= N <= 100). Strany si pro jednoduchost očíslujeme čísly 1,2...,N. Program potom v cyklu vždy vypíše, pro které dvě strany se má provést průzkum, a následně přečte ze vstupu výsledek tohoto průzkumu - číslo strany s většími preferencemi. Když program tímto způsobem získá dostatek údajů potřebných k tomu, aby určil politické strany s nejvyššími a s nejnižšími preferencemi, vypíše odpověď a skončí.
Dbejte zejména na to, aby váš program dal vždy správnou odpověď a aby použil co nejméně průzkumů. Odhadněte, kolik nejvíce průzkumů může váš program potřebovat pro N stran.
>
.
Minského registrový stroj může mít jeden nebo více vstupů, jejichž hodnoty jsou na začátku výpočtu uloženy v registrech R1,...,Rk, kde k je počet těchto vstupů. Ostatní registry jsou na začátku výpočtu inicializovány na hodnotu nula. Po skončení výpočtu Minského registrového stroje je výsledkem hodnota uložená v registru R0.
Každý Minského registrový stroj je řízen pevně daným programem.
V programu se mohou vyskytovat tyto příkazy:
Programy budeme zakreslovat do schémat, přičemž zvýšení hodnoty registru Ri budeme značit obdélníkem s nápisem Ri++, snížení hodnoty registru Ri budeme značit obdélníkem s nápisem Ri--, test na nulu v registru Ri značíme oválem s nápisem Ri?. Začátek programu označujeme písmenem Z v kroužku a konec programu písmenem K v kroužku (program může mít i více konců, ale jen jeden začátek). Jednotlivé příkazy jsou pospojovány šipkami, které určují tok řízení programu. Z obdélníka vychází vždy jediná šipka. Z oválu vycházejí dvě šipky, přičemž jedna z nich je označena nulou (po ní pokračuje výpočet tehdy, když byla v testovaném registru nula, v opačném případě výpočet sleduje druhou šipku). Jestliže v programu za sebou následuje několik příkazů zvýšení nebo snížení, můžeme je napsat pod sebe do jednoho obdélníku.
Podívejme se nyní na to, jak se provádí přičtení čísla y k R0. Opět v cyklu snižujeme hodnotu registru R2 a zvyšujeme hodnotu registru R0, dokud nemáme v registru R2 nulu. Tehdy jsme do R0 přidali přesně y. Problém však spočívá v tom, že v registru R2 máme nyní nulu, ale pro další průběh výpočtu tam potřebujeme vložit zpět hodnotu y. Proto v cyklu kromě snížení R2 a zvýšení R0 ještě zvýšíme R3. Tím si zajistíme, že po skončení cyklu máme hodnotu y uloženou v registru R3. Nyní ji musíme odtamtud přenést zpět do registru R2. To provedeme v dalším cyklu, v němž současně snižujeme R3 a zvyšujeme R2, dokud v R3 není nula. V tom okamžiku máme v R2 opět původní hodnotu y a můžeme začít s dalším kolem výpočtu.