Programování I

Zimní semestr 2009/10

Na těchto stránkách naleznete informace týkající se předmětu Programování I. Mimo jiné tu naleznete co se dělalo na cvičeních, jaké jsou podmínky pro obdržení zápočtu, zadání domácích úkolů a informace o zápočtových programech.

Obecné info:
Jak používat FreePascal s editorem PSPad.

Co se dělalo na cvičeních

1. cvičení: kliknutím sbalit/rozbalit

1. Rodinka a tunel

Rodinka stojí před tunelem - chtěla by přes něj projít. Tato rodinka má k dispozici jednu svíčku, která hoří právě 12 minut.

Převeďte rodinku přes tunel, jestliže víte, že:

tatínek projde tunelem za 1 minutu
maminka projde tunelem za 2 minuty
dcerka projde tunelem za 4 minuty
syn projde tunelem za 5 minut

A dále že:

do tunelu se vejdou maximálně dva lidé
dvojice jde tak rychle jako ten pomalejší
není možno projít tunelem bez svíčky

2. Koza, vlk a zelí

Na jednom břehu řeky je farmář, vlk, koza, zelí a lodička. Vlk by rád sežral kozu, koza si dělá zálusk na zelí. Do lodičky může farmář vzít jen jedno zvíře nebo zelí. Dvě zvířata nebo zvíře a zelí se na lodičku najednou nevejdou. Koza ani vlk pádlovat neumí, na lodi musí být farmář. Jak dostane farmář vlka, kozu i zelí na druhou stranu tak, aby na jednom břehu nikdy nebyla koza s vlkem nebo se zelím bez dohledu pasáčka?

3. Provázky

Máte naolejovaný provázek, o kterém víte, že když ho na jednom konci zapálíte, hoří přesně hodinu. Bohužel, provázek nehoří rovnoměrně, nelze tedy říct, že když provázek přepůlíte, tak jeho polovina budou hořet půl hodiny. Jak pomocí takového provázku naměříte půl hodinu? A co když máte dva takové provázky a chcete naměřit 15 minut?

4. Přímky

Uvažujme, že v rovině je N přímek, o kterých víte, že:

žádné dvě přímky nejsou rovnoběžné
žádné tři přímky se neprotínají v jednom bodě

Na kolik částí tyto přímky rozdělí rovinu? Jak jste k tomu číslu došli?

5. Matfyzák a metro

Jeden roztržitý 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.

6. XOR z NAND hradel

Představte si, že máte nonendovou krabičku - krabičku se dvěma binárními vstupy a jedním binárním výstupem, kde výstup odpovídá booleovskému operátoru NAND (viz. tabulka). Sestavte ze 4 takových krabiček soustavu, která se chová jako operátor XOR (viz tabulka).

A	B	A xor B	A nand B
0	0	0	1
0	1	1	1
1	0	1	1
1	1	0	0

7. 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í?

2. cvičení: kliknutím sbalit/rozbalit

Dořešili jsme si non-andové krabičky z minula.

1. Velbloud a banány

Máme 3000 banánů v poušti a velblouda. Velbloud uveze max. 1000 banánů a za každý ujetý kilometr musí dostat 1 banán. Kolik banánů můžeme max. dovézt do 1000km vzdáleného místa (fabrika na banánové jogurty)?

2. Terorista a kabel

Jste členem teroristické sítě a váš nadřízený má pro vás další záškodnickou misi: O čtvercovém území 1x1km víte, že skrz něj někde vede kabel (rovný, datový). Vašim úkolem je vykopat na území kanálek tak, abyste měli jistotu, že jste kabel překopali (například obkopat území kolem dokola) a to tak, aby délka kanálku byla co nejmenší (nemusí to být kolem dokola, stačí 3 strany, zlepšovat jde i dále)...

3. Množiny a podmnožiny

Kolik podmnožin má N-prvková množina? Kolik 6-ti prvkových podmnožin má N-prvková množina (N je alespoň 6)?

4. Jednoduché prográmky v Pascalu

Test sudosti:

var i: integer;
begin
readln(i);
if i mod 2 = 0 then
  writeln('sude')
else
  writeln('liche');
end.

Test sudosti opakovaně (dokud nezadám zápornou hodnotu):

var i: integer;
begin
readln(i);
while (i > -1) do
  begin
  if i mod 2 = 0 then
    writeln('sude')
  else
    writeln('liche');
  readln(i);
  end;
end.

Výpis minima a maxima z N čísel, ukončení přes záporné číslo (řešení poté, co se cvičící nadýchal vzduchu):

var
  i, max, min: integer;
begin
readln(i);
if (i < 0) then {should terminate now...}
  begin
  writeln('No numbers entered');
  halt;
  end;
{initialize min and max}
{note: no boolean variable is needed in such a simple case...}
max := i;
min := i;
while (i > 0) do
  begin
  {'else' is correct because min and max start}
  {at the same value in the beginning, then max}
  {can only increase and min only decrease...}
  if (i > max) then max := i else
  if (i < min) then min := i;
  readln(i);
  end;
writeln('Max: ', max);
writeln('Min: ', min);
end.

3. cvičení: kliknutím sbalit/rozbalit

4. cvičení: kliknutím sbalit/rozbalit

5. cvičení: kliknutím sbalit/rozbalit

Během hodiny jsme zopakovali základy jazyka Pascal. Na příkladě násobení matic jsme si ukázali rozdíl mezi předáváním parametru hodnotou a referencí:

procedure f(a: integer);
begin
a := a + 1;
end;
 
procedure g(var a: integer);
begin
a := a + 1;
end;
 
var
  i, j: integer;
 
begin
i := 0;
j := 0;
f(i);
g(j);
writeln(i); { 0 }
writeln(j); { 1 }
readln;
end.

Dále jsme si ukázali, jak Pascal řeší vstup ze souboru. Jmenovali jsme si datvý typ file a text ("file of char"), dále pak následující procedury:

assign(F, "file.txt"); { assign file address to the file var }
reset(F); { open file for reading }
rewritre(F); { open file for rewriting - content gets lost }
append(F); { open file for appending }
close(F); { free resources, finish writing to the disk }

http://www.soom.cz/index.php?name=articles/show&aid=10

6. cvičení: kliknutím sbalit/rozbalit