Cvičení z Programování I (PRG030)

skupina I31 a I32, pondělí 12:20 v S7/SW2

Co bylo na cvičení

12.2.2009 - 3. písemka

1. příklad

Máme následující reprezentaci řidkých matic:

	PRow = ^TRow;
	TRow = record
		index: Integer;
		items: PItem;
		next: PRow;
	end;
	PItem = ^TItem;
	TItem = record
		index: Integer;
		value: Double;
		next: PItem;
	end;

Řádky i sloupce jsou setříděné vzestupně podle indexu. Nulové prvky ani prázdné řádky se v matici nevyskytují.

Napište "function Add(M1, M2: PRow): PRow;", která sečte dvě dané matice a výslednou matici vrátí. Původní matice musí zůstat zachovány a výsledek nově zaalokován. [vzorové řešení]

2. příklad

Máme klasický jednosměrný spojový seznam bez hlavy.

	PItem = ^TItem;
	TItem = record
		value: Integer;
		next: PItem;
	end;

Napište "procedure Sort(var P: PItem);", která setřídí spojový seznam vzestupně podle hodnot. Třídění musí pracovat (alespoň v průměrném případě) s časovou složitostí O(N log N). Hint: Zkuste Quicksort, nebo Mergesort. [vzorové řešení]

12.1.2009 - 2. písemka

1. příklad

Je dán kruhový lineární seznam (poslední prvek není zakončen ukazatelem na nil, ale ukazuje na první prvek).

	PItem = ^TItem;
	TItem = record
		value: Integer;
		next: PItem;
	end;

Napište proceduru, která otočí směr ukazatelů v kruhu (první prvek zůstává stále první, ale poslední prvek se stane druhým atd.). [vzorové řešení]

2. příklad

Reprezentujeme řídké polynomy jako klasický lineární spojový seznam bez hlavy:

	PItem = ^TItem;
	TItem = record
		exp: Integer;
		coef: Double;
		next: PItem;
	end;

Seznam je setříděný sestupně podle exponentu a nejsou v něm žádné členy s nulovým koeficientem (0 je reprezentována jako nil). Napište funkci "function divide(P1, P2: PItem; var Rem: PItem): PItem;", která vydělí dva dané polynomy, nastaví Rem na zbytek po dělení a vrátí výsledek. Výsledek i zbytek jsou nově zaalokované polynomy (dodržující výše popsané konvence) a vstupní seznamy musí být zachovány. [vzorové řešení]

5.1.2009

Rekurze

Zopakovali jsme pojem rekurze a naprogramovali jsme několik menších příkládků.

Na závěr jsme nakousli problém generování všech permutací dané množiny prvků. Tento problém jsme nestihli naprogramovat. Zkuste si sami doma. [vzorové řešení]

15.12.2008 - 1. písemka

1. příklad

Mějme definovaný klasický lienární spojový seznam (bez hlavy) jako:

	PItem = ^TItem;
		TItem = record
		value: Integer;
		next: PItem;
	end;

Napište funkci "function isPalindrom(P: PItem): boolean;", která zjistí, zda je daný spojový seznam palindrom. Seznam nesmíte kopírovat a smíte použít max. O(1) paměti. Seznam je možné přepojovat, ale na konci musí být uveden do původního stavu. [vzorové řešení]

2. příklad

Reprezentujeme řídké polynomy jako klasický lineární spojový seznam bez hlavy:

	PItem = ^TItem;
	TItem = record
		exp: Integer;
		coef: Double;
		next: PItem;
	end;

Seznam je setříděný sestupně podle exponentu a nejsou v něm žádné členy s nulovým koeficientem (0 je reprezentována jako nil). Napište funkci "function multiply(P1, P2: PItem): PItem;", která vynásobí dva dané polynomy a vrátí výsledek. Výsledek je nově zaalokovaný polynom (dodržující výše popsané konvence) a původní seznamy musí být zachovány. [vzorové řešení]

8.12.2008

Lineární spojové seznamy

Celé cvičení jsme se intenzivně připravovali na příští písemnou práci. Vyřešili jsme následující úlohy:

Další funkce, které si můžete zkusit napsat doma:

1.12.2008

Řešení úloh z CodExu

Rozebrali jsme řešení úloh Hledání v setříděném poli, Faktorizace, Cenzura a Byrokratický aparát. Ostatní úlohy jsou až do konce přednáškového. Po 19.1. už nebude možné získat další body na zápočet.

Úlohy

Rozebrali jsme úlohu data na šachovnici včetně důkazu, že nejde přenést více, než 6 bitů. Ostatní úlohy zůstávají na rozmyšlenou doma. Vzhledem k našlápnutému rozvrhu se k nim již pravděpodobně nestihneme znovu vrátit.

Lineární spojové seznamy

Zbytek cvičení jsme věnovali LSS. Stihli jsme dodělat pouze jednu úlohu: Napište funkci, která otestuje, zda je daný seznam ukončený nilovým ukazatelem, nebo je zacyklen sám do sebe. Nesmíte používat aritmetiku ani jiné pomocné struktury (jen konstantní množství ukazatelů). Očekává se lineární čas. složitost.

Pokud jste měli se seznamy problémy, věnujte jim extra péči v domácí přípravě. Písemka bude jen o nich. Další problémy, které si můžete zkusit (všechy řešte pouze přepojováním ukazatelů bez alokace a dealokace):

24.11.2008

Úvod

Na začátku jsme se věnovali zápočtovým pracem. Pokud ještě nemáte vybranou práci, měli byste si pospíšit.

k-tý nejmenší pomocí LSS

Zopakovali jsme dynamickou alokaci paměti a lineární spojové seznamy. Následně jsme si zkusili přepsat program na hledání k-tého nejmenšího pomocí LSS. Nestihli jsme to dokončit, doporučuji zkusit si doimplementovat doma. [vzorové řešení]

10.11.2008

Úložky

Rozebrali jsme úlohu lámání čokolády a hru s kameny ve varinatě se 2 kameny. Ostatní úlohy a varianty zůstávají na příště. Nově jsme si přidali:

Stříhání pásky

Máme konečnou pásku se sudým počtem políček. Na každém políčku je napsáno celé kladné číslo. Políčka jsou napsána vedle sebe (tedy na každém okraji pásky je jedno políčko). Hráči střídavě odstříhávají políčka z pásky, přičemž hráč, který je na tahu, smí odstřihnout pouze jedno ze dvou krajních políček. Vítězí hráč, který nastříhá větší součet čísel. Navrhněte herní strategii.

XOR ze 4 NANDů

Máme 4 hradla NAND (každé se 2 ma vstupy a jedním výstupem). Jejich vzájemným propojením sestavte dvouvstupové hradlo XOR. Hradlo NAND se chová jako logický AND s negovaným výstupem.

Procesory na kruhové sběrnici

Máte N procesorů, které jsou zapojeny do kruhu. Každý procesor je přímo připojen pouze ke dvěma sousedním. Sousední procesory si mezi sebou mohou posílat zprávý (tzn. každý procesor může svému kolegovi nalevo i napravo odeslat zprávu a stejně tak od nich zprávu přijmout). Paměť pro program je pro všechny procesory společná, paměť pro data (a zásobník) má každý procesor vlastní. Všechny procesory jsou stejně rychlé a každý má unikátní identifikační číslo.

Aby mohly procesory něco počítat, musí mít jeden procesor řídící (ten se nazývá koordinátor). Procesory startují najednou se stejným programem a následně se musí domluvit, kdo z nich bude koordinátor. Napište algoritmus, který vybere koordinátora (nezapomeňte, že alg. je pro všechny procesory stejný).

Praktická část

Nakousli jsme problém počítání s dlouhými čísly. Reprezentovali jsme dlouhá čísla pomocí pole a naimplementovali jsme nad nimi operaci sčítání.

3.11.2008

Celé cvičení jsme prakticky programovali v Delphách.

Suma

Vyřešili jsme společně úložku Suma z CodExu. Těm, kteří nebyli na cvičení doporučuji vyřešit si doma.

2. nejmenší z N

Naprogramovali jsme řešení problému hledání 2. nejmenšího prvku z posloupnosti N čísel. Zároveň jsme se na tom naučili používat textové soubory. [vzorové řešení]

k-tý nejmenší z N

Následně jsme si úlohu rozšířili na obecné hledání k-tého nejmenšího prvku. Řešení jsme nestihli dokončit – zkuste si doma. [vzorové řešení]

27.10.2008

Úvod

Na cvičení jsme rozebrali Metro, 2. z N a Kuličky v pytlíku. Ostatní úlohy zůstávají na příště a navíc ještě přibyly:

Oblet Země - vyřešeno na cvičení (na 3 letadla)

Armáda velmoci A má letadla typu B. Letadlo typu B je schopno na jedno natankování obletět polovinu Země. Letadlo typu B je také schopno přijímat i vydávat palivo za letu (tzn. 2 letadla B si mohou vyměňovat palivo). Na světě existuje pouze jedno letiště, na kterém mohou letadla B přistávat (a tedy i vzlétat). Kolik letadel typu B potřebuje velmoc A, aby bylo jedno letadlo schopno obletět Zemi?

Pozn: Žádné letadlo nesmíte obětovat.

Hra s kameny

Máme pásku, která se skládá z políček umístěných vedle sebe. Páska má počátek, ale na druhém konci pokračuje do nekonečna (jako např. polopřímka). Na pásce leží dva kameny (každý na jiném políčku). Dva hráči se střídají v tazích. V každém tahu může hráč posunout libovolný kámen o libovolný počet políček směrem k počátku pásky. Kameny nelze pokládat na sebe ani přeskakovat. Hráč, který nemůže táhnout, prohrál. Vymyslete herní strategii.

Varianty:

Vězni a žárovka

Ve věznici je 100 vězňů. Každý bydlí na samotce a nemá vůbec žádný kontakt s ostatními vězni. Vězni jsou po jednom přiváděni k výslechu. V místnosti, kde výslech probíhá je žárovka. Vyslíchaný vězeň vidí, zda je žárovka rozsvícená, nebo zhasnutá a může v průběh výslechu její stav libovolně změnit. Vězni jsou vyslícháni v náhodném pořadí, ale tak, že pokud by byli vyslícháni nekonečný počet dní, byli by všichni vyslechnuti nekonečněkrát. Za určitý konečný počet výslechů T, tedy nastane okamžik, kdy jsou všichni vězni vyslechnuti alesoň jednou. Pokud po tomto okamžiku kterýkoli z vězňů řekne při výslechu: "Nyní už jsme byli všichni vyslechnuti alespoň jednou," budou všichni vězni propuštěni. Řekne-li někdo tuto větu dříve, než nastane T, budou všicni vězni popraveni. Vězni byli ještě před začátkem výslechů půl hodiny na vězeňském dvoře, kde si mohli domluvit strategii rozsvěcení a zhasínání žárovky. Navrhněte tuto strategii, aby byli vězni propuštěni.

Pozn: Po zahájení výslechů si mohou vězni pomocí žárovky předávat pouze 1 bit informace (žádné další informace nemají).

20.10.2008

Úvod

Na cvičení jsme rozebrali důkaz, že 1. z N nejde lépe, než na N-1 vážení a úlohy Velbloud a Kulový blesk. Ostatní úlohy zůstávají na příště a navíc ještě jedna přibyla:

Data na šachovnici

Alice potřebuje přenést Bobovi co největší množství informace. Komunikace probíhá tak, že Alice dostane šachovnici 8x8, jejíž políčka jsou zcela náhodně obarvena černou a bílou barvou. Alice musí změnit jedno políčko (přebarvit ho na z jedné barvy na druhou) a následně pošle šachovnici Bobovi. Jak velké množství informace (kolik bitů) si takto můžou maximálně přenést, když se předtím směli domluvit na kódování?

Pozn: Políčka jsou jednoznačně očíslována, takže se nemůže stát, že by se šachovnice nějak nevhodně otočila, což by mohlo Boba jistě zmást.

Praktická část

Na zbytku cvičení jsme se seznámili s vývojovým prostředím delphi a naprogramovali jsme si jednoduchou aplikaci na hledání kořenů kvadratické rovnice. [příklad]

13.10.2008

Úvod

Cvičení pro kruhy I31 a I32 byla sloučena. Sjednotili jsme také úložky a dořešili Tunel a 1. z N (zatím bez Dk). Ostatní úložky (Kulový blesk a Velbloud) zůstávají na příště. Dále přibyly následující úložky:

Metro

Jeden roztritý matfyzák jezdí do školy metrem. On však nemá hodinky a tak chodí na metro naprosto v náhodných časech. Metro má oběma směry interval 10 minut, ale 9 z 10 případů se matfyzákovi stane, že nejdřív přijede metro, kterým nechce jet (tj. ve směru ze školy). Vysvěltete, jak je možné, že má chudák takovou smůlu a pouze v 1 z 10 případů mu přijede nejdřív metro ve správném směru.

2. z N

Na kolik porovnání lze nalézt druhý nejmenší prvek z N. Podmínky jsou stejné, jako u 1. z N.

Hra "Lámání čokolády"

Máme tabulku čokolády o rozměrech MxN, kde BUNO M je sudé, N je liché a čokoláda je alespoň v jednom rozměru větší, než 2x1. Hru hrají dva hráči, kteří se pravidelně střídají v tazích. Během každého tahu vezme hráč libovolný kousek čokolády (na počátku je jen jeden) a rozlomí ho. Oba vzniklé kousky čokolády vrátí a pokračuje druhý hráč. Pokud při lámání zůstane některému z hráčů alespoň v jedné ruce kousek o rozměrech 1x1, tak daný hráč prohrál. Navrhněte výherní strategii pro začínajícího hráče.

Pozn: vítěz může čokoládu sníst :o)

Tahání kuliček z pytlíku

V pytlíku je 86 černých a 72 bílých kuliček. V každém tahu vytáhnu náhodně 2 kuličky. Pokud vytáhnu dvě stejné kuličky, vložím jednu bílou. Pokud vytáhnu dvě různé, vložím 1 černou kuličku. Která kulička zůstane v pytlíku jako poslední?

Varianta: řeště obecně pro b bílých a c černých kuliček.

6.10.2008

Úvod

Potřebné informace o průběhu cvičení a o požadavcích na zápočet naleznete na těchto stránkách. Po vzájemném seznámení jsme se věnovali jednoduchým úložkám...

Koza, zelí, vlk (hotovo)

Na břehu postává koza, zelí a vlk. Farmář je potřebuje přepravit přes řeku, ale do loďky s sebou může vzít nejvýše jednoho. Pokud ovšem nechá na břehu bez dozoru kozu a zelí, koza zelí sežere. Stejně tak pokud zůstane sama koza s vlkem, vlk kozu slupne. Vymyslete pořadí přepravy tak, aby nikdo nikoho nesežral.

Provázky (hotovo)

Mám naolejovaný provázek. Když ho na jednom konci zapálím, bude postupně odhořívat, až za 1 hodinu dohoří na druhý konec (a zhasne). Provázek však není všude stejně široký, a proto ani nehoří stále stejně rychle. Nelze tedy tvrdit, že např. polovina provázku shoří za půl hodiny.

Úkoly:

Pozn: okamžik, od kdy začínám měření, si mohu zvolit sám

Tunel

Tatínek, maminka, dcerka a syn sojí u vchodu do tunelu. Všichni potřebují projít tunelem na druhou stranu. Celá rodina má k dispozici jedinou svíčku, která vydrží hořet 12 minut. V tunelu je úpná tma, takže je zhola nemožné, aby se jej někdo pokusil projít bez svíčky. Tunel je zároveň velmi úzký a tak v něm mohou jít nejvýše dva lidé zároveň. Tatínkovi trvá cesta tunelem 1 minutu, mamince 2 minuty, synáčkovi 4 minuty a nejmenší dcerce 5 minut. Pokud jdou tunelem dva lidé, je jejich rychlost rovná pomalejšímu z nich (např. tatínkovi se synáčkem to bude trvat 4 minuty). Vymyslete pořadí v jakém má rodinka projít tunelem tak, aby to stihla dřív, než jim dohoří svíčka.

Minimum (1. z N)

Na kolik porovnání lze nalézt nejmenší prvek z N. Porovnání je operace definovaná vždy právě na dvou prvcích. Zároveň dokažte, že neexituje lepší řešení, než vaše.

Čokoláda (hotovo)

Mějme tabulkovou čokoládu, která má MxN čtverečků. Chceme ji rozlámat na jednotlivé čterečky, ale nesmíme položit několik kousků na sebe a rozlomit je zároveň. Kolikrát musíme čokoládu rozlomit? Také dokažte, že to lépe nejde (tj. že je vaše řešení nejlepší možné).

Kulový blesk

Máme N bytů očíslovaných 1..N. Nájemníci Bytu č.1 by se rádi přestěhovali do bytu č.2, ti z bytu č.2 by rádi do trojky atd. až ti z bytu N by se chtěli dostat do 1čky. Problém je, že byty lze vyměňovat pouze dvojsměnou. To znamená, že pokud se nájemníci z bytu A stěhují do bytu B, pak se nájemníci z B musí stěhovat do A a nikam jinam nemohou. Jedna dvojsměna trvá jeden den a nájemníci, kteří ji provádějí, se tento den nemohou účastnit žádné jiné směny. V jeden den však může probíhat více dvojsměn paralelně. Kolik dní bude potřeba (a jakým způsobem budou probíhat dvojsměny), aby se všichni nájemníci dostali tam, kam chtějí?

Velbloud a banány

Máme 3000 banánů uprostřed pouště a velblouda, který uveze 1000 banánů. Velbloud musí za každý ujetý kilometr dostat 1 banán, jinak pojde hlady. Kolik banánů můžeme max. dovézt do 1000km vzdálené oázy?
Navíc dokažte, že je vaše řešení nejlepší možné. Pozn: Velbloud nesmí chcípnout.

Varianty: