Cvičný midterm

Najneskorší termín odovzdania: 8.4.2020 (streda) o 18:00
Odovzdávané súbory: SpajanyZoznam.java, Osoba.java, PocitadloPostupnosti.java

Táto sada zadaní slúži ako cvičný praktický polsemestrálny test v čase dištančnej výučby na overenie zvládnutia obsahu prvej polovice semestra. Odporúčaný prístup je riešiť úlohy za 80 minút. Po uplynutí času sa môžete rozhodnúť dopracovať úlohy, ak je potrebné.

Cyklický prefix (5b)

Uvažujme triedu SpajanyZoznam z prednášky o spájaných zoznamoch. Do triedy SpajanyZoznam pridajte metódu odstranCyklickyPrefix, ktorá ako parameter dostane nenullovú referenciu na pole čísel (potenciálne aj prázdne). Toto pole definuje nekonečnú cyklickú postupnosť čísel. Konkrétne, ak obsah poľa je [3, 8, 3], tak táto postupnosť je [3, 8, 3, 3, 8, 3, 3, 8, 3, 3, 8, …]. Po zavolaní metódy nech sa zo začiatku spájaného zoznamu odstráni čo najviac hodnôt tak, aby platilo, že odstraňovaná postupnosť je prefixom (=má rovnaký začiatok) uvedenej nekonečnej cyklickej postupnosti čísel.

public void odstranCyklickyPrefix(int[] prefix)
[$[Get Code]]

Metóda nech pracuje v lineárnom čase vzhľadom k dĺžke zoznamu, t.j. 𝑂(𝑛), kde 𝑛 je dĺžka zoznamu, a s pamäťou 𝑂(1). Za opakovaný prechod spájaným zoznamom je bodový zisk znížený o 1 bod.

Uvažujme zoznam [3, 4, 5, 3, 4, 3, 4, 5, 2]. Metóda zmení obsah tohto zoznamu takto:

  • odstranCyklickyPrefix([3, 4, 8]) → [5, 3, 4, 3, 4, 5, 2], odstránená časť v pôvodnom zozname: [3, 4, 5 ,3, 4, 3, 4, 5, 2]
  • odstranCyklickyPrefix([3, 4, 5]) → [3, 4, 5, 2], odstránená časť v pôvodnom zozname:[3, 4, 5, 3, 4, 3, 4, 5, 2]
  • odstranCyklickyPrefix([3, 4, 5, 3, 4, 3, 4, 5, 2, 2]) → [], odstránená časť v pôvodnom zozname: [3, 4, 5, 3, 4, 3, 4, 5, 2]
  • odstranCyklickyPrefix([]) → [3, 4, 5, 3, 4, 3, 4, 5, 2]

Uvažujme zoznam [3, 8, 3, 3, 8, 3, 3, 8, 8, 3, 2]. Metóda zmení obsah tohto zoznamu takto:

  • odstranCyklickyPrefix([3, 8, 3]) → [8, 3, 2], odstránená časť v pôvodnom zozname: [3, 8, 3, 3, 8, 3, 3, 8, 8, 3, 2]
  • odstranCyklickyPrefix(3, 8, 3, 3, 8) → [3, 8, 8, 3, 2], odstránená časť v pôvodnom zozname:[3, 8, 3, 3, 8, 3, 3, 8, 8, 3, 2]

Rovnaký počet detí (5b)

Do triedy Osoba z prednášky o stromoch pridajte metódu, ktorá vráti, či všetky osoby v strome potomkov, ktoré nie sú listami (t.j. majú aspoň jedno dieťa), majú rovnaký počet detí. Strom potomkov zahŕňa aj osobu v koreni. Inými slovami zaujíma nás, či pre každý uzol v strome platí, že má 0 detí alebo taký počet detí ako koreň.

public boolean rovnakyPocetDeti()
[$[Get Code]]

Vybraná podpostupnosť (5b)

Uvažujme postupnosť (pole) nezáporných celých čísel indexovanú od nuly. Každý výber indexov tejto postupnosti definuje nejakú vybranú podpostupnosť. Majme postupnosť [4, 8, 4, 9]. Výberom indexov 0, 2, 3 dostávame vybranú podpostupnosť [4, 4, 9]. Výberom indexov 0, 3 dostaneme vybranú podpostupnosť [4, 9]. Ak má postupnosť dĺžku 𝑛, existuje 2𝑛 rôznych výberov indexov (vrátane prázdneho výberu). Vytvorte program, ktorý pre zadanú postupnosť čísel (pole cisla) vypočíta počet rôznych výberov indexov, pre ktoré platí, že tomuto výberu prislúchajúca vybraná podpostupnosť je:

  • je rastúca (𝑎[𝑖] < 𝑎[𝑖 + 1]) a
  • má dĺžku aspoň 𝑑.

Predpokladajte, že 𝑑 > 0.

public class PocitadloPostupnosti {
   public PocitadloPostupnosti(int[] cisla) {
   }

   public int pocetRastucichPostupnostiDlzkyAspon(int d) {
   }
}
[$[Get Code]]

Rada: Na overenie, či postupnosť je rastúca potrebujete overiť, že každé vybrané číslo (okrem prvého) je ostro väčšie ako predošlé vybrané číslo