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...
[zk] 7.7.05
-
- Matfyz(ák|ačka) level II
- Příspěvky: 63
- Registrován: 19. 11. 2004 21:45
- Typ studia: Informatika Bc.
- Bydliště: Stonava / Troja
Re: [zk] 7.7.05
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 .Kuba píše: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...
Priklad to nebyl tak tezky jako ty minule , ale byl dost pracny.
-
- Matfyz(ák|ačka) level II
- Příspěvky: 63
- Registrován: 19. 11. 2004 21:45
- Typ studia: Informatika Bc.
- Bydliště: Stonava / Troja
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 .MyS píše: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" ?