Reparát

Příklady dle vlastního vyběru počtu dle následujicí tabulky: Nejasnosti posílejte mailem, vysvětlení budu průběžne dopisovat sem.

Řešení zdar.

2 58,Zykán Pavel
2 48,Wojnar Aleš
2 44,Šupalová Ivana
2 42,Žember Martin
3 39,Zoulek Aleš
3 34,Žák Petr
3 21,Šefčíková Jana
4 7, Stoček Ondřej

2 53,Vyhnanovská Julie
2 41,Glasová Ester
3 39,Šimek Jan
^ ^ ^
| | `- id
| `--- počet bodů
`----- počet přikadů

ok -- 2 57,Tobolíková Petra
ok -- 1 63,Vykypěl Michal

1. Oddech

Na vstupu jsou čísla N, a1,.., aN. Určete maximální délku nejdelší vybrané 1-udýchaně-rostoucí podposloupnosti. Posloupnost b1..bN je k-udýchaně-rostoucí posloupnost pokud b[i]<b[i+1], pro všechny 0<i<N až na maximalně k indexů i. Jde to (=naprogramujte to) v O(N). Obecně O(N*k). Program.

2. Permutíci

Na vstupu jsou čísla N, k, a1, a2, ..., aN. Čísla a1..aN definují permutaci p. Spočítejte k-tou mocninu této permutace. Jde to (=naprogramujte to) v O(N). Program.

3. Sheduler

Je třeba dobře naplánovat úlohy. Každá úloha má čas začátku, čas konce (Deadline) a čas, který stačí k jejímu vyřešení. Pro seznam úloh máte rozhodnout zda-li jde úlohy naplánovat tak, abych je všechny stihnul ve stanovených časech. V jeden okamžik mohu dělat jen jednu úlohu, mohu však vykonávání úlohy přerušit a dokončit ji později (ale musí být dokončena před Deadline). Pouze popis algoritmu.

4. Brutální vyvažování

Napište program, který z daného binárního stromu udělá AVL strom, a to tím způsobem, že některé prvky vymaže. Ale aby nebyl zas tak brutální tak to udělá tak, aby vymazaných prvků bylo co nejméně. Můžete si rozšířit strukturu t_node o potřebné datové položky. O(N). Procedura (nebo více procedur) + diskuze o správnosti algoritmu.

5. Hvězdičky

Spočítejte přesně kolik hvězdiček (v závislosti na N) vytiskne následující program

	for i := 1 to N do
		for j := 1 to i*2 do 
			for k := 1 to j*3 do 
				write('*');