Zadanie 3
Najneskorší termín odovzdania: 10.3.2024 (nedeľa) o 18:00
Odovzdávaný súbor: SpajanyZoznam.java
Doplňujúce požiadavky:
- riešenia, ktoré nebude možné skompilovať (t.j. riešenia so syntaktickými chybami) nebudú hodnotené,
- zdrojový kód správne naformátujte (CTRL+SHIFT+F),
- komentovaný zdrojový kód
Obe metódy musia pracovať v čase O(n) a pamäťou O(1), kde n je počet hodnôt (uzlov) v spájanom zozname. Ak metódy budú potrebovať viac ako jeden prechod spájaným zoznamom, bodový zisk bude znížený o 30%.
Metódy pridajNaZaciatok a toString nemodifikujte, keďže sú využívané evaluátorom.
Zduplikuj (3 body)
Do triedy SpajanyZoznam pridajte metódu zduplikuj(double dh, double hh) , ktorá za každý výskyt čísla v intervale <dh, hh> hodnota vloží jeho duplikát. Vzájomné poradie ostatných uzlov (hodnôt) v zozname musí ostať zachované.
Príklad: zo zoznamu s hodnotami [5, 7, 1, 9, 3, 30, 6, 4] po volaní zduplikuj(6, 20) vznikne zoznam s hodnotami [5, 7, 7, 1, 9, 9, 3, 30, 6, 6, 4].
Rastúca podpostupnosť (3 body)
Do triedy SpajanyZoznam pridajte metódu rastucaPodpostupnost() , ktorá v spájanom zozname ponechá prvú hodnotu (ak existuje) a pre každú inú ponechanú hodnotu platí, že:
- je väčšia ako predošlá ponechaná hodnota
- medzi ňou a predošlou ponechanou hodnotou nie je v pôvodnom zozname žiadna iná väčšia hodnota ako predošlá ponechaná hodnota.
Príklady:
- zo zoznamu s hodnotami
[5, 1, 2, 7, 1, 9, 3, 30, 6, 4]po volanírastucaPodpostupnost()vznikne zoznam s hodnotami[5, 7, 9, 30], - zo zoznamu s hodnotami
[1, 2, 3, 4]po volanírastucaPodpostupnost()vznikne zoznam s hodnotami[1, 2, 3, 4], - zo zoznamu s hodnotami
[10, 10, 10, 9, 11, -5, -2, 12, 7, 12]po volanírastucaPodpostupnost()vznikne zoznam s hodnotami[10, 11, 12],
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
* Trieda zapuzdrujuca spajany zoznam a manipulaciu s nim
*/
public class SpajanyZoznam {
/**
* Sukromna trieda reprezentujuca jeden uzol spajaneho zoznamu
*/
private static class Uzol {
double hodnota;
Uzol dalsi;
}
/**
* Referencia na prvy uzol spajaneho zoznamu
*/
private Uzol prvy = null;
/**
* Prida novu hodnotu na zaciatok spajaneho zoznamu
*
* @param hodnota
* pridavana hodnota
*/
public void pridajNaZaciatok(double hodnota) {
Uzol pridavany = new Uzol();
pridavany.hodnota = hodnota;
pridavany.dalsi = prvy;
prvy = pridavany;
}
@Override
public String toString() {
String vysledok = "[";
Uzol aktualny = prvy;
while (aktualny != null) {
if (aktualny != prvy)
vysledok += ", ";
vysledok += aktualny.hodnota;
aktualny = aktualny.dalsi;
}
return vysledok + "]";
}
public void zduplikuj(double dh, double hh) {
// TODO implementovat
}
public void rastucaPodpostupnost() {
// TODO implementovat
}
public static void vlozNahodneHodnoty(SpajanyZoznam zoznam, int pocet) {
for (int i = 0; i < pocet; i++) {
zoznam.pridajNaZaciatok((int) (500 - Math.random() * 1000) / 10.0);
}
}
public static void vlozNahodneUsporiadaneHodnoty(SpajanyZoznam zoznam, int pocet) {
int hodnota = (int) (500 + Math.random() * 1000);
for (int i = 0; i < pocet; i++) {
zoznam.pridajNaZaciatok(hodnota / 10.0);
hodnota -= (int) (Math.random() * 100);
}
}
public static void main(String[] args) {
// Demo
SpajanyZoznam zoznam = new SpajanyZoznam();
vlozNahodneHodnoty(zoznam, 20);
System.out.println("Pred: " + zoznam);
System.out.println("zduplikuj(...)");
zoznam.zduplikuj(10, 20);
System.out.println("Po: " + zoznam);
System.out.println();
zoznam = new SpajanyZoznam();
vlozNahodneUsporiadaneHodnoty(zoznam, 20);
System.out.println("Pred: " + zoznam);
System.out.println("rastucaPodpostupnost()");
zoznam.rastucaPodpostupnost();
System.out.println("Po: " + zoznam);
}
}