První série druhého ročníku KSP

Tyto úlohy pocházejí z desetileté ročenky KSP. Jejich řešení bohužel nemáme v elektronické podobě, takže na ně budete muset přijít sami.

Zadání úloh

2-1-1 Bohgayský Bukaj

V království Bohgay mají měnovou jednotku jeden Bukaj bohgayský. Každý rok tam ale probíhá měnová reforma. Základní jednotka 1 Bukaj vždy zůstává, ale vyšší bankovky již dávno nejsou násobky dvou, pěti či deseti, jak bývá ve světě zvykem, ale jsou to libovolné celočíselné násobky Bukaje, pokaždé jiné. Například vloni byly v oběhu tyto bankovky: 1BB, 4BB, 13BB, 74BB, 301BB a 302BB. Napište program, který bude pomáhat bohgayskému královskému pokladnímu vyplácet libovolný obnos. Program po zadání hodnot jednotlivých bankovek, jejich množství v královské pokladně a velikosti vyplácené částky zjistí, jakým nejmenším počtem bankovek lze uvedenou částku vyplatit (pokud to vůbec jde) a vypíše hodnoty a počty vyplácených bankovek.

Příklad: Pro výše uvedené hodnoty bankovek při dostatečné zásobě ve státní pokladně program doporučí vyplatit částku 379BB bankovkami 301BB (1 ks), 74BB (1 ks) a 4BB (1 ks).

2-1-2 Součtová posloupnost I.

Posloupnost kladných celých čísel nazveme součtovou, jestliže začíná číslem 1 a každý další její člen lze vyjádřit jako součet dvou čísel takových, že se v posloupnosti vyskytla před tímto členem. Například posloupnost 1 2 4 5 3 je součtová, neboť 2=1+1, 4=2+2, 5=1+4 a 3=1+2. Úlohy:

  1. Napište program, který o zadané posloupnosti kladných celých čísel zjistí, zda je součtová.
  2. Navrhněte algoritmus (není třeba ho programovat), který o zadané posloupnosti kladných celých čísel zjistí, zda lze nějakou změnou pořadí jejích prvků získat součtovou posloupnost. Například přeuspořádáním posloupnosti 3 5 1 3 2 4 3 lze získat součtovou posloupnost 1 2 3 5 3 4 3.

2-1-3 Plody

Řekneme, že řetězec P je plodem řetězce S, jestliže se P dá vytvořit z S použitím následujících dvou pravidel:

  1. každý znak ? (otazník) v S se nahradí libovolným znakem různým od otazníku a hvězdičky
  2. každý znak * (hvězdička) v S se nahradí libovolnou (třeba i prázdnou) posloupností znaků různých od otazníku a hvězdičky.

Úloha: Napište program, který přečte ze vstupu řetězce S a P a zjistí, zda P je plodem S.

Příklad: Řetězce FRANTA, FRANTARANTA, FERON jsou plodem řetězce F*R?N*, zatímco řetězce FRNAK, FREON nejsou.

2-1-4 Zlomková aritmetika

Zlomkem nazveme každou uspořádanou dvojici celých čísel (a,b), kde b>0. Hodnotou zlomku (a,b) nazvěme reálné číslo a/b. Definujeme sčítání, odčítání, násobení a dělení zlomků (a,b) a (c,d) následujícími vztahy:

(a,b) + (c,d) = (ad+bc,bd)
(a,b) - (c,d) = (ad-bc,bd)
(a,b) * (c,d) = (ac,bd)
(a,b) / (c,d) = (ad,bc)     pro c≠ 0

Nechť MaxNum ≥ 16383 je celočíselná konstanta odpovídající choutkám vašeho počítače. PN-zlomkem (přípustným normalizovaným zlomkem) nazveme každý zlomek (a,b) takový, že čísla a, b nemají žádného společného dělitele většího než 1 a platí -MaxNum≤ a,b≤ MaxNum.

Navrhněte datové struktury vhodné pro reprezentaci PN-zlomků a napište následující podprogramy pro práci s PN-zlomky:

slož Vstup: celá čísla a, b taková, že -MaxNum≤ a,b≤ MaxNum
Výstup: chyba při b=0, jinak PN-zlomek s hodnotou a/b
rozlož Vstup: PN-zlomek (a,b)
Výstup: celá čísla a, b
porovnej Vstup: PN-zlomky (a,b) a (c,d)
Výstup: -1 je-li hodnota (a,b) - (c,d)<0,
1 je-li hodnota (a,b)- (c,d)>0,
0 je-li hodnota (a,b)- (c,d)=0
sečti Vstup: PN-zlomky (a,b) a (c,d)
Výstup: chyba, je-li hodnota (a,b) + (c,d) mimo rozsah -MaxNum až MaxNum
PN-zlomek s hodnotou rovnou hodnotě (a,b) + (c,d), je-li -MaxNum ≤ ad+bc, bd ≤ MaxNum
ve zbývajícím případě „zaokrouhlený“ PN-zlomek s hodnotou blízkou hodnotě (a,b)+(c,d)
(návod: uřízněte dolní bity)
odečti obdoba podprogramu sečti pro odčítání,
vynásob násobení,
vyděl dělení. V případě dělení je při c=0 výstupem chyba.