CourseWare Wiki
Switch Term
Winter 2024 / 2025
Winter 2023 / 2024
Winter 2022 / 2023
Winter 2021 / 2022
Winter 2020 / 2021
Winter 2019 / 2020
Winter 2018 / 2019
Older
Search
Log In
b191
courses
b3b33alp
cviceni
t08
Warning
This page is located in archive. Go to the latest version of this
course pages
.
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
2019/11/18 09:14 stepan created
2019/09/21 11:40 stepan removed
2018/11/19 11:43 external edit
Go
Next revision
Previous revision
2019/11/18 09:14 stepan created
2019/09/21 11:40 stepan removed
2018/11/19 11:43 external edit
Go
courses:b3b33alp:cviceni:t08 [2018/11/19 11:43]
127.0.0.1
external edit
courses:b3b33alp:cviceni:t08 [2019/11/18 09:14]
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
př
í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 0 0
+
* priorita operátorů: ''<nowiki>**</nowiki>'' větší než ''*'', ''/'', větší než ''+'', ''-''
-
0
0 0 0 0
+
* operátor mocnění je asociativní zprava
-
-1
0 0 0 0
+
-
-
1
-1 0 0 0
+
* **Příklad
1
(a)**: <code>
-
2
2 2 1 2 0 1 0 0 0 0
1
+
3 + 4 *
2
/ (
1
- 5 )
-
0 0 0 1 1 1 2 1 2 0 2 2
+
</code> výstup <code>
-
3
0 3 1 2 1 1 1 0 1
+
3
4
2
*
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 ) *
2
/ (
1
- 5 )
-
2
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 +
2
*
1
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
>
**
</
nowiki
>
se 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
+
*-
4
2 3
-
{{:courses:b3b33alp:fill.png?100|}}
+
</code>
př
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ě
2
+ -
3
, i 2-+-3 (POZOR unární - má ještě vyšší prioritu než mocnina)
+
-
**Výstup:**
+
-
* Při
př
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 +
4
*
2
/ ( 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
-
5
+
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