Warning
This page is located in archive.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
courses:b3b33alp:cviceni:t08 [2019/09/21 11:40]
stepan removed
courses:b3b33alp:cviceni:t08 [2019/11/18 09:14] (current)
stepan created
Line 91: Line 91:
  
 ==== Lehká varianta ==== ==== Lehká varianta ====
- * Napište program **assemble.py**, který ​si ze souboru se jménem zadaným jako první argumentu na íkazové řádce, přečte rozměr pole a díly, kterými má to pole zaplnit +  ​* Napište program **postfix.py**, který převede výraz z [[https://cs.wikipedia.org/wiki/Infixov%C3%A1_notace|infixového zápisu]] (standardní zápis výrazůjak jste zvyklí ze školy) do postfixového zápisu (tzv. [[https://cs.wikipedia.org/wiki/Postfixov%C3%A1_notace|reverzní polské notace]]) s využitím algoritmu [[https://cs.wikipedia.org/wiki/Shunting-yard_%28algoritmus%29|shunting yard]]
-    * první řádek obsahuje dvě čísla ​//S// //R//, kde //R// je počet řádků a //S// je počet sloupců obdélníkového pole +
-    * dále násluduje //R// řádků, kde  +
-      * 0 definují volná pole v matici, která se mají vyplnit zadanými dílky +
-      * -1 - definují obsazená pole, kam dílky nesmí zasahovat  +
-      * čísla na jednom řádku jsou oddělena jednou nebo více mezerami (použijte funkci "​split()"​ bez parametrů). +
-    * každý další řádek obsahuje popis jednoho dílku: +
-      * jedna řádka obsahuje souřadnice čtverečků (x y), ze kterých je sestaven celý dílek +
-      * souřadnice jsou uvedeny za sebou bez oddělovacích čárek a závorek +
-      * dílek může být libovolně posunut, nemusí obsahovat čtverec se souřadnicemi (0,0)  +
-  * Program v souboru **assemble.py** nalezne libovolné pokrytí volných polí matice dílky, které se použijí tak, jak jsou zadány - nesmíte je natáčet ani převracet, pouze posouvat. Námi zadané příklady mají právě jedno řešení. +
-  * Výstupem programu je pokrytí matice dílky, kdy plocha prvního dílku (zadaný v souboru hned za maticí volného místa) je vyplněna číslem 1, plocha druhého dílku (na další řádce za prvním dílkem) číslem 2, atd.+
  
-  * Notace pro popis dílkůje to seznam x y souřadnic. +  * **Vstup**: 
-  Pro T-dílek na obrázku je jeho popis: 0 0 1 0 2 0 1 1 +    * textový řetězec, přes standardní vstup 
-{{:​courses:​b3b33alp:​cviceni:​blokus1.eps.png?​200|}}+    obsahuje pouze celá kladná čísla, kulaté závorky a operace ''​ + * / <​nowiki>​**</​nowiki>​ ''​ 
 +    * mezi dvěma členy je vždy právě jedna mezera
  
-  * Pro obsah zadan0ho souboru:  +  * **Výstup**
-<​code>​ +    * pokud je vstupní řetězec ve správném formátu, pak je výstup textový řetězec reprezentující vstupní výraz v postfixové notaci. Mezi každými dvěma členy výstupu vytiskněte právě jednu mezeru 
-5 5 +    * jinak ''​ERROR''​ 
-  0 0 0 0 +   
-  0 0 0 0 +  ​* priorita operátorů:​ ''<​nowiki>​**</​nowiki>''​ větší než ''​*'',​ ''/'',​ větší než ''​+'',​ ''​-''​ 
-  0 0 0 0 +  ​* operátor mocnění je asociativní zprava 
--1  0 0 0 0 + 
---1 0 0 0 +  ​* **Příklad ​1(a)**: <​code>​ 
-2 2 1 2 0 1 0 0 0 0 +3 + 4 * / ( - 5 ) 
-0 0 0 1 1 1 2 1 2 0 2 2 +</​code>​ výstup <​code>​ 
-0 3 1 2 1 1 1 0 1 +5 - / +
-0 0 0 1 0 2 1 1 2 1+
 </​code>​ </​code>​
  
-Příklad ​dílku ​1: +  * **Příklad 1(b)**: <​code>​ 
-<​code>​ +( 3 + 4 ) * / ( - 5 ) 
-2 2 1 2 0 1 0 0 0 0 1+</​code>​ výstup (všimněte si, jak se oproti předchozímu příkladu projeví přidání závorky)<​code>​ 
 +3 4 + 5 - /
 </​code>​ </​code>​
  
-<​code>​ +  * **Příklad 2** <​code>​  
-souřadnice ​ +9 * 3 ** 5  
-y+</​code>​ Výstup: <​code>​ 
 +9 3 5 ** * 
 +</​code>​
  
-2  ​* +  ​* **Příklad 3**: <​code>​ 
-1* * +( 3 ( 4 - 5 ) ) + ( 8 * ( 10 + 2 ) / 9 ) 
-0*** +</​code>​ výstup <​code>​ 
- 012 souřadnice x+3 4 5 - * 8 10 2 + * 9 / +
 </​code>​ </​code>​
  
 +  * **Příklady chybných vstupů** ​
 +    * ''​2 + ( 4 ( * 5 ) )''​
 +    * ''​3 - * 5''​
 +    * ''​( 2 * ( 1 - 3 )''​
  
  
-Graficky znázorněné všechny dílky+==== Těžká varianta ====
  
-1:​{{:​courses:​b3b33alp:​cviceni:​ubongo-0e.png?​100|}} +  * Napište program **pretoin.py**, který převede výraz z [[https://​cs.wikipedia.org/​wiki/​Prefixov%C3%A1_notace|prefixové notace]] do [[https://cs.wikipedia.org/​wiki/​Infixov%C3%A1_notace|infixového zápisu]] ​ 
-2:{{:​courses:​b3b33alp:​cviceni:​ubongo-1.png?100|}} +  * **Vstup**  
-3:{{:​courses:​b3b33alp:​cviceni:​ubongo-2e.png?100|}} +    * textový řetězec přes standardní vstup 
-4:​{{:​courses:​b3b33alp:​cviceni:​ubongo-3e.png?​100|}}+    * řetězec obsahuje pouze kladná celá čísla, operátory ''​+ / * <​nowiki>​**</​nowiki>'',​ případně mezeru mezi dvěma členy, pokud je to pro jednoznačnost výrazu nutné ( dvě hvězdičky bez mezery ''<​nowiki>​**</​nowiki>''​ je operátor mocnění, dvě hvězdičky oddělené mezerou ''​* *''​ jsou dvě po sobě jdoucí operace násobení),​ dva numerické členy jsou vždy oddělené mezerou
  
  
-program vytiskne:+  * **Výstup** 
 +    * pokud je na vstupu platný řetězec v prefixové notaci, pak řetězec převedený na infixovou notaci, vytiskněte bez mezer 
 +    * jinak ''​ERROR''​
  
-<code> +  * Operace +,-,*,/ se vyhodnocují zleva, operace ​<nowiki>**</nowikise vyhodnocuje zprava (stejně jako je to v Pythonu) 
-4 3 3 3 3 +  * Složitost této úlohy je ve správném doplnění závorek, které musí zaručit správné vyhodnocení zleva doprava, ale nesmíte závorky používat zbytečně
-4 4 4 2 3 +
-4 2 2 2 1 +
--1 2 1 2 1 +
--1 -1 1 1 1 +
-</code>+
  
-Nápověda možného řešení:​ +  ​* **Příklady:**  
-  ​Postupně se snažím vyplnit prázné místo, např odshora zleva +    * Vstup <​code>​ 
-  ​Na první volné políčko se snažím umístit dílek tak, že toto volné pole zaplní svou nejhořejší levou částí (protože vše nad a vlevo od volného políčka je zaplněno, viz obrázek) a rekurzivně zavolám plnění se seznamem dílků, ze kterých odstraním právě použitý dílek +*-2 3 
-{{:​courses:​b3b33alp:​fill.png?​100|}} +</​code> ​evede na výstup: <​code>​ 
-  * Pokud to nevyjde a políčko nelze žádným dílkem zaplnit tak, aby tento dílek nepřekrýval jiné dílky, nebo nepřesahoval přes okraj matice), pak se vrátím z rekurze +(4-2)*3
-  ​* Při návratu z rekurze, zkusím obsadit volné pole jiným dílkem +
-  ​Pro správné fungování rekurze buď vytvořím nové pole s nově vloženým dílkem, nebo při návratu z rekurze musím odstranit z matice starý dílek +
-  ​Pokud již nemám dílky a celá matice je obsazená - mám řešení a mohu skončit ​ +
- +
-==== Těžká varianta ==== +
- +
-  * Napište program **three.py**,​ který převede výraz z [[https://​cs.wikipedia.org/​wiki/​Infixov%C3%A1_notace|infixového zápisu]] (standarní zápis výrazů, jak jste zvyklí ze školy) do reprezentace [[https://​en.wikipedia.org/​wiki/​Three-address_code|tří-adresného módu]]. Tento tří-adresový kód je využíván překladačem,​ jako mezistupeň mezi programem a strojovým jazykem. +
-**Vstup:** +
-  Výraz je zadán na jedné řádce standardního vstupu +
-  * Vstupní výraz může obsahovat pouze celá kladná celá čísla (záporné číslo je unární operátor ​a kladné číslo), mezery, závorky (, ) a operace +,-,*,/,^. (Operace ^ je mocnina a má nejvyšší prioritu, nejnižší prioritu mají operace +,-, prostřední prioritu *,/) +
-  * Oproti lehké variantě výraz umožňuje unární + a -, tedy je správně ​+ - 3, i 2-+-3 (POZOR unární - má ještě vyšší prioritu než mocnina) +
-**Výstup:​** +
-  * Při evodu musíte otestovat správnost zadaného výrazu a pokud je formát chybný, pak vytisknete ERROR +
-  * formát výstupu: +
-    * první trojice má číslo 1, každá další trojice o jedno větší číslo +
-    * trojice tiskněte bez mezer, tak jak je uvedeno níže +
-    * unární - se přeloží jako trojice, např -5 bude tXX:=0-5 +
-    * unární + se vypustí, ve výrazu je vlastně zbytečné +
-    * výraz se vyhodnocuje zleva doprava (všechny operace i mocniny) a toto vyhodnocování určuje pořadí trojic. V příkladu níže není tedy možné nejdříve vypočítat rozdíl 1-5 a teprve potom součin 4*2 +
- +
-Příklad:​ +
- +
-  * Vstup  +
-<​code>​ +
-3 + / ( 1 - 5 )+
 </​code>​ </​code>​
-  ​* převede na výstup: +    ​Vstup <​code>​ 
-<​code>​ ++-4 2 3 
-t1:=4*2 +</​code> ​převede na výstup: <​code>​ 
-t2:=1-+4-2+3
-t3:=t1/t2 +
-t4:=3+t3+
 </​code>​ </​code>​
- +    ​* Vstup <​code>​ 
-Příklad:​ +*4-2 3 
-  ​* Vstup  +</code> převede na výstup: <​code>​ 
-<​code>​ +4*(2-3)
-(1+2)*(3+4)/(5+6)+
 </​code>​ </​code>​
-  * převede na výstup: 
-<​code>​ 
-t1:=1+2 
-t2:=3+4 
-t3:=t1*t2 
-t4:=5+6 
-t5:=t3/t4 
-</​code>​ 
- 
- 
-Příklad: 
-  * Vstup  
-<​code>​ 
-1+2/(*4+5) 
-</​code>​ 
-  * převede na výstup: 
-<​code>​ 
-ERROR 
-</​code>​ 
- 
- 
courses/b3b33alp/cviceni/t08.txt · Last modified: 2019/11/18 09:14 by stepan