Čtvrtá série první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


1-4-1 PC substituce


Řetězec je posloupnost znaků různých od apostrofu uzavřená v apostrofech (např. 'Pilif'). Komentář je posloupnost znaků začínající znakem { a končící znakem }, v níž se znaky { a } vyskytují pouze na začátku a na konci (např. {Caforal}). Napište program, který přečte ze vstupu dvě posloupnosti znaků P a R a poté zkopíruje vstupní text do výstupního, přičemž nahradí ve vstupním textu každý výskyt P posloupností R, kromě těch výskytů P, které jsou v řetězci, jehož počáteční apostrof není v komentáři, a kromě těch výskytů P, které jsou v komentáři, jehož počáteční znak { není v řetězci.


1-4-2 Největší díra


Napište program, který k zadanému kladnému celému číslu n a zadané posloupnosti reálných čísel délky n (posloupnost se vejde do paměti) vytiskne taková dvě čísla z posloupnosti, že žádné číslo z posloupnosti neleží „mezi nimi“ (tj. není menší než jedno a větší než druhé z nich) a že absolutní hodnota jejich rozdílu je maximální. Příklad: Pro n=4 a posloupnost 2 5.3 2.7 -20.1 program vytiskne 2 -20.1.

Poznámka: Rychlejší algoritmus = lepší algoritmus.


1-4-3 Chutnější výrazy


Chutný výraz je tvořen nezápornými celými čísly a znaky +, -, *, /, ( a ) (viz zadání úlohy 1-2-3). Chutnější výraz odpovídající danému chutnému výrazu V bez lomítek je chutný výraz W bez závorek a se stejnou hodnotou jako výraz V takový, že ve výrazu W jsou právě všechna nezáporná celá čísla z výrazu V. Napište program, který přečte ze vstupu chutný výraz neobsahující lomítka a vypíše jemu odpovídající chutnější výraz. Příklad: Pro vstup 1+2*(3-4) program vypíše 1+2*3-2*4.


1-4-4 Renumber


Představte si zjednodušenou verzi jazyka Basic, tzv. R8-Basic, s těmito omezeními:

  • Pracuje pouze s čísly, ne s řetězci
  • Každý příkaz je na zvláštním řádku
  • Identifikátory všech proměnných jsou jednopísmenné
  • V příkazech GOTO, GOSUB a za THEN v příkazu IF smí být pouze číslo řádku (nelze tedy psát GOTO R+O+P+A ani IF A=1 THEN PRINT A) a v jiných příkazech se číslo řádku nevyskytuje.

Napište program, který načte ze vstupu kladná celá čísla baze a krok a program v jazyku R8-Basic (který se vejde do paměti), přečísluje jeho řádky a odkazy na ně tak, aby první řádek měl číslo baze, další baze+krok, baze+2·krok, … atd. (vyskytne-li se v programu odkaz na neexistující řádek, ohlásí chybu) a přečíslovaný program vytiskne na výstup.

Příklad: Pro baze=10, krok=5 a vstupní program

     3 INPUT A
     5 IF A=0 THEN 110
     7 GOSUB 9
     8 END
     9 RETURN
     110 GOTO 3
     120 GOTO 120
vydá výstup
     10 INPUT A
     15 IF A=0 THEN 35
     20 GOSUB 30
     25 END
     30 RETURN
     35 GOTO 10
     40 GOTO 40