nechodím na prednáškyMnožiny
Deviata prednáška
Stiahnuť PDF · 679 kBPreber si túto poznámku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto poznámky.
Náhľad poznámky
Fakulta riadenia a informatiky ŽU
Množiny
Pojmy zavedené v 8. prednáške
N-
rozmerné polia
Dvojrozmerné polia – matica
definícia – typ[][] premenna
inicializácia – new typ[pocetRiadkov][pocetStlpcov]
práca s prvkami – premenna[riadok][stlpec]
Pole polí
inicializácia – new typ[pocetRiadkov][]
inicializácia prvkov
– pole[riadok] = new typ[pocetStlpcov]
1
Pojmy zavedené v 8. prednáške
vnorené cykly
this
sekcie rozhrania
verejné – ľubovoľný objekt v okolí
neverejné – len objekt vo svojom súkromí
2
3
Cieľ
základná práca so súbormi
množinové operácie v jazyku Java
projekt: Sudoku
4
Sudoku
5
Sudoku – metóda nacitajZadanie
public void nacitajZadanie()
{
aMriezka = new int[][] {
{9, 0, 0, 0, 8, 0, 0, 5, 0},
...
{8, 0, 2, 0, 0, 3, 0, 1, 5},
{0, 1, 0, 0, 9, 0, 0, 0, 3}
};
}
6
Sudoku – nová požiadavka
Možnosť načítania zadania zo súboru
Zadania stiahnuté z internetu
Formát: matica čísel
prvky oddelené medzerami
riadky oddelené ukončením riadku
7
Súbor so zadaním
8
Práca so súbormi
čítanie
otvorenie súboru na čítanie
postupné čítanie obsahu
zatvorenie súboru
zápis
otvorenie súboru na zápis
postupný zápis nového obsahu
zatvorenie súboru
Práca so súbormi v jazyku Java
9
10
Sudoku – príkazy import
import java.util.Scanner;
import java.io.File;
import java.io.IOException;
11
Sudoku – metóda nacitajZoSuboru
public void nacitajZoSuboru(String paNazov)
throws IOException
{
...
}
12
Sudoku – metóda nacitajZoSuboru
File subor = new File(paNazov);
Scanner citac = new Scanner(subor);
for (int riadok = 0; riadok < 9; riadok++) {
for (int stlpec = 0; stlpec < 9; stlpec++) {
aMriezka[riadok][stlpec] = citac.nextInt();
}
}
citac.close();
13
Sudoku – nová požiadavka
Možnosť zapísania aktuálneho stavu riešenia do
súboru
Využitie knižničnej triedy java.io.PrintWriter
Formát zhodný s formátom zadania
14
Sudoku – príkazy import
Využívame ďalšiu triedu, treba pridať import
import java.io.PrintWriter;
15
Sudoku – metóda zapisDoSuboru
public void zapisDoSuboru(String paNazov)
throws IOException
{
...
}
16
Sudoku – metóda zapisDoSuboru
File subor = new File(paNazov);
PrintWriter zapisovac = new PrintWriter(subor);
for (int[] riadok : aMriezka) {
for (int policko : riadok) {
zapisovac.print(" " + policko);
}
zapisovac.println();
}
zapisovac.close();
Políčko
inicializácia – prázdne políčko
test, či je prázdne
vkladané číslo – testovanie pravidiel
výpis – bodka alebo číslo z <1, 9>
teraz
– inštancia triedy Sudoku
presun do inštancií triedy Policko
17
Zavedenie triedy Policko
18
Políčko – rozhranie
19
Políčko – vnútorný pohľad
20
21
Policko – trieda
public class Policko
{
private int aCislo;
public Policko()
{
aCislo = 0;
}
...
}
22
Policko – jePrazdne
public boolean jePrazdne()
{
return aCislo == 0;
}
23
Policko – nastavCislo
public void nastavCislo(int paCislo)
{
if (this.jePrazdne()) {
aCislo = paCislo;
}
}
24
Policko – dajCislo
public int dajCislo()
{
return aCislo;
}
25
Policko – toString
public String toString()
{
if (this.jePrazdne()) {
return ".";
} else {
return "" + this.dajCislo();
}
}
26
Metóda toString
automatická konverzia objektov na reťazce
ak trieda nedefinuje svoju metódu toString má
automatickú
vráti reťazcový identifikátor inštancie triedy
System.out.print(policko);
String retazec = "" + policko;
27
Sudoku – trieda – stará
public class Sudoku
{
private int[][] aHraciePole;
...
}
28
Sudoku – trieda – nová
public class Sudoku
{
private Policko[][] aHraciePole;
...
}
29
Sudoku – konštruktor – starý
public Sudoku()
{
aHraciePole = new int[9][9];
}
30
Sudoku – konštruktor – nový
public Sudoku()
{
aHraciePole = new Policko[9][9];
for (int riadok = 0; riadok < 9; riadok++) {
for (int stlpec = 0; stlpec < 9; stlpec++) {
aHraciePole[riadok][stlpec] = new Policko();
}
}
}
31
Sudoku –vykresliMriezku – stará
for (int[] riadok : aMriezka) {
for (int policko : riadok) {
if (policko == 0) {
System.out.print(".");
} else {
System.out.print(policko);
}
}
System.out.println();
}
32
Sudoku –vykresliMriezku – nová
for (Policko[] riadok : aMriezka) {
for (Policko policko : riadok) {
System.out.print(policko);
}
System.out.println();
}
33
Sudoku – nová požiadavka
automatické riešenie Sudoku
Pridajte metódu ries, ktorá sa pokúsi vyriešiť
Sudoku
34
Sudoku
Najjednoduchšie automatické riešenie:
Jednoduché pravidlo
Ak je množina kandidátov políčka jednoprvková,
môžeme kandidáta použiť ako hodnotu políčka
Množina kandidátov – Množina všetkých čísel,
ktoré možno do políčka vpísať
35
Sudoku – kandidáti políčka
2,3,4,
6,9
stĺpcoví
kandidáti
políčka
36
Sudoku – kandidáti políčka
4,6,7,
9
riadkoví
kandidáti
políčka
37
Sudoku – kandidáti políčka
4,5,6,
9
blokoví
kandidáti
políčka
38
Množiny kandidátov
Množina riadkových kandidátov – pre každý
riadok
Množina stĺpcových kandidátov – pre každý
stĺpec
Množina blokových kandidátov – pre každý blok
39
Sudoku – kandidáti políčka
Plat
í:
kandidatiPolicka
=
stlpcoviKandidati
∩
riadkoviKandidati
∩
blokoviKandidati
40
Sudoku – kandidáti políčka
4,6,9
kandidáti
políčka
2, 3, 4, 6, 9
4, 6, 7, 9
4, 5, 6, 9
============
4, 6, 9
Práca s množinami
Generická trieda HashSet<TPrvok>
bez usporiadania
nemožnosť pristúpiť cez index
možnosť prechádzať pomocou foreach
41
Trieda HashSet – rozhranie
42
Matematické operácie s množinami
máme množiny A, B
máme prvok x
43
Prvok množiny
? ∈ ?
44
if (A.contains(x))
...
Množina je prázdna
? = ∅
45
if (A.isEmpty())
...
Množina A je podmnožinou B
? ⊆ ?
46
if (B.containsAll(A))
...
Zjednotenie množín A a B
? ∪ ? → ?
47
HashSet<TPrvok> C = new HashSet<TPrvok>();
C.addAll(A);
C.addAll(B);
Prienik množín A a B
? ∩ ? → ?
48
HashSet<TPrvok> C = new HashSet<TPrvok>();
C.addAll(A);
C.retainAll(B);
Rozdiel množín A a B
? ∖ ? → ?
? − ? → ?
49
HashSet<TPrvok> C = new HashSet<TPrvok>();
C.addAll(A);
C.removeAll(B);
50
Sudoku – trieda
public class Sudoku
{
private Policko[][] aHraciePole;
private HashSet<Integer>[] aRiadkoviKandidati;
private HashSet<Integer>[] aStlpcoviKandidati;
private HashSet<Integer>[][] aBlokoviKandidati;
...
}
51
Sudoku – konštruktor
public Sudoku()
{
aRiadkoviKandidati = new HashSet<Integer>[9];
aStlpcoviKandidati = new HashSet<Integer>[9];
aBlokoviKandidati = new HashSet<Integer>[3][3];
Chyba – generická trieda ako prvok poľa
52
53
Sudoku – konštruktor
public Sudoku()
{
aRiadkoviKandidati = new HashSet[9];
aStlpcoviKandidati = new HashSet[9];
aBlokoviKandidati = new HashSet[3][3];
Varovanie
54
55
Sudoku – konštruktor
@SuppressWarnings({"unchecked"})
public Sudoku()
{
aRiadkoviKandidati = new HashSet[9];
aStlpcoviKandidati = new HashSet[9];
aBlokoviKandidati = new HashSet[3][3];
Sudoku – konštruktor – pokračovanie
naplnenie všetkých množín kandidátov
hodnotami <1, 9>
na doma
56
Práca s kandidátmi
jednoduché riešenie – políčka s jediným
kandidátom
každé políčko má trojicu množín kandidátov
riadok, stĺpec, blok
kandidáti políčka – prienik trojice
poveríme políčko
57
Rozšírenie rozhrania triedy Policko
58
59
Sudoku – konštruktor – pokračovanie
for (int riadok = 0; riadok < 9; riadok++) {
for (int stlpec = 0; stlpec < 9; stlpec++) {
aHraciePole[riadok][stlpec] = new Policko(
aRiadkoviKandidati[riadok],
aStlpcoviKandidati[stlpec],
aBlokoviKandidati[riadok/3][stlpec/3]
);
}
}
60
Policko – trieda
public class Policko
{
private HashSet<Integer> aRiadkoviKandidati;
private HashSet<Integer> aStlpcoviKandidati;
private HashSet<Integer> aBlokoviKandidati;
private int aCislo;
61
Policko – konštruktor
public Policko(
HashSet<Integer> paRiadkoviKandidati,
HashSet<Integer> paStlpcoviKandidati,
HashSet<Integer> paBlokoviKandidati)
{
aCislo = 0;
aRiadkoviKandidati = paRiadkoviKandidati;
aStlpcoviKandidati = paStlpcoviKandidati;
aBlokoviKandidati = paBlokoviKandidati;
}
62
Policko – dajJedinehoKandidata
public Integer dajJedinehoKandidata()
{
HashSet<Integer> kandidati =
new HashSet<Integer>();
kandidati.addAll(aRiadkoviKandidati);
kandidati.retainAll(aStlpcoviKandidati);
kandidati.retainAll(aBlokoviKandidati);
63
Policko – dajJedinehoKandidata
if (kandidati.size() == 1) {
for (Integer cislo: kandidati) {
return cislo;
}
}
return null;
}
64
Sudoku – ries(1)
public void ries()
{
for (Policko[] riadok : aHraciePole) {
for (Policko policko : riadok) {
// riesenie pre policko
}
}
}
65
Sudoku – ries(2)
if (policko.jePrazdne()) {
Integer kandidat = policko.dajJedinehoKandidata();
if (kandidat != null) {
policko.nastavCislo(kandidat);
}
}
Kandidáti ako trieda
66
Kandidati – rozhranie
67
68
Kandidáti – konštruktor
public Kandidati()
{
aKandidati = new HashSet<Integer>();
for (int i = 1; i <= 9; i++) {
aKandidati.add(i);
}
}
69
Kandidáti – dajJednehoKandidata
public int dajJednehoKandidata()
{
for (Integer cislo: aKandidati) {
return cislo;
}
return 0;
}
Ďakujem za pozornosť
Automaticky vygenerovaný textový náhľad. Pre plné formátovanie si stiahnite súbor.