[zk] 7.7.05

Malé příklady jako obvykle
Velký příklad byl dnes trochu jiného rázu. Vyžadovalo se ho "skoro dodělat" čili když tam bude špatně nějaká "ptákovina" tak to prý nevadí.

Definice: Řeknu, že posloupnost čísel je k-rostoucí, pokud po vyhození nejvýše k prvků je rostoucí.

Na vstupu je **libovolně dlouhá **(délka se vejde do longintu) posloupnost čísel (jde třeba z linky - vyžaduje se sekvenční algoritmus) a k <= 5 (s malou ztrátou bodů může být k=3). Najděte nejdelší k-rostoucí úsek tak, že vypíšete kde začíná a kterých k čísel se vynechává (tak, aby někdo, kdo dostane stejný vstup, mohl úsek bez většího počítání vypsat).

Na ústní jdu zítra, ale předpokládám že to neudělam, jelikož jsem pořádně neudělal ani algoritmus, natož nějaký kód...
Kdyby někdo měl rozumné řešení, tak ho sem prosím napište...

Kuba wrote:Malé příklady jako obvykle
Velký příklad byl dnes trochu jiného rázu. Vyžadovalo se ho "skoro dodělat" čili když tam bude špatně nějaká "ptákovina" tak to prý nevadí.

Definice: Řeknu, že posloupnost čísel je k-rostoucí, pokud po vyhození nejvýše k prvků je rostoucí.

Na vstupu je **libovolně dlouhá **(délka se vejde do longintu) posloupnost čísel (jde třeba z linky - vyžaduje se sekvenční algoritmus) a k <= 5 (s malou ztrátou bodů může být k=3). Najděte nejdelší k-rostoucí úsek tak, že vypíšete kde začíná a kterých k čísel se vynechává (tak, aby někdo, kdo dostane stejný vstup, mohl úsek bez většího počítání vypsat).

Na ústní jdu zítra, ale předpokládám že to neudělam, jelikož jsem pořádně neudělal ani algoritmus, natož nějaký kód...
Kdyby někdo měl rozumné řešení, tak ho sem prosím napište...

Nejprve si vyres jak reprezentovat podposloupnost . Staci ti pole 8 prvku - zacatek , konec , pocet vyjimek a indexy vyjimky . V programu ti staci 2 - nejdelsi prozatim nalezena a aktualni posloupnost. V programu si take musis uchovavat k cisel pred vyjimkou a k poslednich cisel . ( abys osetril pripady posloupnosti kdy musis vynechat prvky patrici do jine posloupnosti ) . Nactes cislo a porovnas ho jestli patri do dane poslounosti , pokud ano , nacitas dalsi . Pokud ne tak zkoumas jestli ho muzes zanest do vyjimek , jestli ano udelas to a nacitas dalsi . Jestli ne tak zkoumas jestli muzes vynechat predchazejici cisla , jestli ano tak je vynechas a jdes na dalsi , jestli ne tak si posunes zacatek posloupnisti a 1. vyjimku vynechas .
Priklad to nebyl tak tezky jako ty minule , ale byl dost pracny.

2saff: ja sice teda pisemku nepsal...ale ("tutchekova past")...kdyz zadam "1 2 3 1000 5 6", najde ti to fakt "1 2 3 5 6" a ne "1 2 3 1000" ?

lehce OT, ale jednickaaaaaa, praaaaaazniny ;)

kryl v poho... konecne jsem se naucil dyn. prog... neni nad to kdyz vam to nekdo vysvetli za pochodu ;) - treba kryl u zkousky :lol:

MyS wrote:2saff: ja sice teda pisemku nepsal...ale ("tutchekova past")...kdyz zadam "1 2 3 1000 5 6", najde ti to fakt "1 2 3 5 6" a ne "1 2 3 1000" ?

Chtel jsem mu popsat zakladni myslenku problemu a ne do detailu vyresit problem . Jinak to funkuje , ale na ustnim jsem se s krylem stratili na posloupnosti se 3 vyjimkami za sebou , proto me dal z velkeho prikladu 2-3 .