NepřihlášenKSP fórum
Fórum Hlavní stránka Nápověda Hledat Přihlásit
Nahoru Téma KSP / Úložky / 29-1-7 Stromy kolem nás: Úkol 2
- - Od RiHL (Org) Dne 08. 10. 2016 21:43
Ahoj!

> Vymyslete algoritmus, který vytvoří strom z jeho postfixového výpisu bez
> závorek. Vyzkoušejte si to třeba na výrazech.


Můžeme u konstruovaného stromu předpokládat, že jde o strom výrazu? Tj. např.,
že je binární a že dokážeme poznat, které vypisované prvky jsou listy (tedy
čísla) a které ne (operátory)?

Díky,
Ríša
Nadřazený - - Od Tomáš Maleček (Org) Dne 09. 10. 2016 17:24
Disclaimer: Nejsem autor úlohy a seriál nebudu opravovat, vysvětluji obecný
princip bodování a čtení zadání úloh. Když nikdo kompetentnější nereaguje, snad
je tohle lepší než nic.

> Vymyslete algoritmus, který vytvoří strom z jeho postfixového výpisu bez
> závorek.


Píše se o stromu, nic víc o vstupu nevíš. Je každý strom stromem výrazu? Ne.
Takový předpoklad tedy úlohu potenciálně zjednodušuje. Podle toho, jak moc ji
zjednoduší, o takovou část bodů přijdeš. Teprve ze zbylé části bodů nějaké
dostaneš, podle toho, jak dobře funguje tvé řešení pro zjednodušenou úlohu (a
jak dobře je popsané a zanalyzované).

> Vyzkoušejte si to třeba na výrazech.


Zadání nabádá k řešení jednodušší verze problému. Nejspíš proto, že zobecněním
problému se řešení nezmění od základu a jen bude řešení samo potřebovat
zobecnit. Ber to jako nápovědu, protože to není vlastnost každé úlohy. Např.
nejdelší cesta v DAG a nejdelší cesta v obecném grafu jsou úlohy, jejichž dobrá
řešení jsou v principu rozdílná.

> … je binární a že dokážeme poznat, které vypisované prvky jsou listy (tedy
> čísla) a které ne (operátory)?


Nechci autorovi zasahovat do úlohy, tyhle konkrétnosti dost možná máte vymyslet
sami. Zkusím tedy jen obecnou, mírně návodnou otázku: Nedokážeš se těch
předpokladů (aspoň některých z nich) zbavit? A ještě lépe – zvládneš dokázat,
že bez některého z nich to nejde (např. proto, že zápis by byl nejednoznačný)?
Nadřazený - - Od RiHL (Org) Dne 09. 10. 2016 19:50
Ahoj,

díky za odpověď. Já právě věřím, že pokud o výpisu neumím říct vůbec
nic, je nejednoznačný. Dokonce jsem si to i dokázal, ale neumím dokázat,
že mé předpoklady (teď už jiné než v původním dotazu) jsou „nejvolnější
možné“.

Tak doufám, že směr, kterým jsem se ubíral, je dostatečně obecný :-).

Ríša
Nadřazený - Od Medvěd (Org) Dne 09. 10. 2016 21:43
Pardon, tohle je bug v zadání. Je potřeba alespoň vědět, které vrcholy jsou vnitřní, a které listy. Předpokládej prosím, že vstup tuto informaci obsahuje.
Nahoru Téma KSP / Úložky / 29-1-7 Stromy kolem nás: Úkol 2

Powered by mwForum 2.29.7 © 1999-2015 Markus Wichitill