Přednášky KIV/PPA1, A. Netrvalová, 2016 8. přednáška
Obsah 8. přednášky:
Souborový V/V - pokračování
Proudový vstup a výstup
Textové vs. binární soubory
Zpracování textových souborů
Příklad použití txt souborů – součin matic
Zpracování binárních souborů*
Rekurze*
Motivační příklad (k souborům) - řešení
Tato tematika je zpracována v
Záznamy přednášek: str. 167 – 194
Strana 2 (celkem 38)
Souborový vstup a výstup
Poznámka
Široké téma – výklad pouze v rozsahu pro použití v 1. ročníku (více předměty OOP, PT, ...)
Práce se soubory – třída File (viz minulá přednáška)
Proudový vstup a výstup
Java: V/V – pojem proud dat (stream)
- vlastnost proudu dat - spojitý tok vpřed
- zpracování proudu stejné, bez ohledu na směr dat vstup (zdroj) / výstup (cíl) a druh fyzického zařízení (konzola, klávesnice, soubor na disku, síť, ...), rozlišení při inicializaci
Program
Output Stream
Soubor
Input Stream
Strana 3 (celkem 38)
1. Proudový V/V s využitím prostředků OS
- vstup prostřednictvím System.in (klávesnice)
- výstup prostřednictvím System.out (obrazovka)
- přesměrování V/V (již známe) - příkazová řádka
2. Proudový V/V s využitím knihoven Javy
- přesměrování programové
a) Přesměrování vstupu
- prostřednictvím přetížených konstruktorů třídy Scanner stanovením zdroje (klávesnice, soubor)
// klavesnice
Scanner sc = new Scanner(System.in);
// soubor
Scanner sc = new Scanner(new File("vstup.txt"));
java Xyz < vstup.txt přesměrování vstupu
java Xyz > vystup.txt přesměrování výstupu
java Xyz < vstup.txt > vystup.txt vstup i výstup
Strana 4 (celkem 38)
Příklad: přesměrování vstupu (použit Scanner)
Nadbytečné výpisy vstupu možno odstranit: - metoda přidělující vstup ze souboru (pokud
existuje) nebo z klávesnice a ošetřující výjimky
import java.util.*; import java.io.*;
public class PresmerovaniScanner{ private static Scanner sc;
public static void main(String [] args) throws Exception {
sc = new Scanner(new File("vstup.txt")); // src jinak path
System.out.print("Zadej pocet cisel:"); int pocet = sc.nextInt(); int pole[] = new int[pocet];
System.out.println("Zadavej cisla"); for(int i=0; i<pocet; i++){ pole[i]= sc.nextInt(); }
int suma = 0; for(int i=0; i<pole.length; i++){ suma += pole[i]; } double prumer = (double) suma/pocet; System.out.println("Prumer = " + prumer); } }
Zadej pocet cisel:Zadavej cisla Prumer = 3.0
Strana 5 (celkem 38)
Metoda nastavZdrojVstupu() zároveň ošetří i
výjimky
import java.util.*; import java.io.*;
public class PresmerovaniScannerVolba {
static final String JMENO = "vstup.txt"; // path
static Scanner sc;
static boolean nastavZdrojVstupu () {
boolean klavesnice = true;
try { File f = new File(JMENO); if (f.exists()){ sc = new Scanner(f); // ze souboru klavesnice = false; } else { sc = new Scanner(System.in); // klavesnice = true; …. z klavesnice uz nastaveno } } catch (Exception e){ e.printStackTrace(); } return klavesnice; } // pokracovani na dalsim slidu - main()
Strana 6 (celkem 38)
Poznámka
Čteme-li data ze souboru a neznáme-li jeho velikost, tj. počet dat, je možno použít následujících metod (typu boolean):
- hasNext() - je na vstupu další řetězec?
- hasNextInt() - je na vstupu další celé číslo?
- hasNextDouble() - je na vstupu další reálné číslo?
- hasNextLine() - je na vstupu další řádka?
public static void main(String [] args){
boolean klavesnice = nastavZdrojVstupu(); if(klavesnice){ System.out.print("Zadej pocet cisel:"); } int pocet = sc.nextInt(); int pole[] = new int[pocet]; if(klavesnice){ System.out.println("Zadavej cisla"); } for(int i=0; i<pocet; i++){ pole[i]= sc.nextInt(); } int suma = 0; for(int i=0; i<pole.length; i++){ suma += pole[i]; } double prumer = (double) suma/pocet; System.out.println("Prumer = " + prumer); } }
Strana 7 (celkem 38)
Příklad: použití metody boolean hasNextInt()
Spočtěte aritmetický průměr čísel uložených v souboru vstup.txt
b) Přesměrování výstupu
- trochu složitější, nepoužijeme známou konstrukci System.out, ale jinou:
předdefinovaný objekt typu PrintStream a již
známou metodu println(), a jelikož je to práce
se souborem, je nutno soubor zavřít metodou close()
import java.util.*; import java.io.*;
public class IlustraceHasNextInt{
public static void main(String [] args) throws Exception {
Scanner sc = new Scanner(new File("vstup.txt")); // path
int suma =0; int pocet = 0; while (sc.hasNextInt()) { // dokud je na vstupu cele cislo
suma += sc.nextInt(); // nacteni a soucet
pocet++; } double prumer = (double) suma/pocet; System.out.println("Prumer = " + prumer); } } //pro data v souboru: 1 2 3 4 5 6 7 8 9 10 Prumer = 5.5
Strana 8 (celkem 38)
V aktuálním adresáři vytvořen soubor vystup.txt.
public class PresmerovaniVystupu {
static boolean obrazovka = false; private static Scanner sc;
public static void main(String [] args) throws Exception {
sc = new Scanner(new File("vstup.txt")); // v src, jinak path
int pocet = sc.nextInt(); int pole[] = new int[pocet]; for(int i=0; i<pocet; i++){ pole[i]= sc.nextInt(); }
int suma = 0; for(int i=0; i<pole.length; i++){ suma += pole[i]; } double prumer = (double) suma/pocet;
PrintStream p; if (obrazovka){ p = System.out; // nastaveni vystupu na obrazovku } else { p = new PrintStream("vystup.txt"); // do souboru v src, path
} p.println("Prumer = " + prumer); p.close(); // uzavreni vystupniho souboru
} }
Strana 9 (celkem 38)
Textové vs. binární soubory
Textové soubory
„čitelné“, připomínají V/V na konzolu - přípona .txt + jiné - dle specializace (xml, csv) - organizace po řádcích obecně různé délky - ukončení řádky závislé na platformě
Výhody: úprava textovým editorem, srozumitelnost
Nevýhody: pomalejší zpracování a větší délka souboru oproti binárnímu souboru
Binární soubory
četnější (obrázky, hudba, filmy, spread sheet) - vnitřní organizace závisí na daném formátu
(.jpg, .mp3, .avi)
Výhody: paměťově úspornější, rychlejší zpracování
Nevýhody: speciální prohlížeč formátu, nečitelnost
Důležitá poznámka
Dále se omezíme pouze na proudově orientované postupy zpracování souborů.
Java – zpracování souborů
- soubory je nutno otevírat a zavírat - odlišné zpracování txt a binárních souborů - nutnost ošetření výjimek
Strana 10 (celkem 38)
Zpracování textových souborů
Poznámka – načítání se provádí po bytech, které se
v implicitním kódování (OS) převádějí na Unicode znaky (více v OOP, PT, ZOS)
A. Primitivní způsob
Čtení - třída FileReader
- instance třídy (otevření souboru) – 2 možnosti:
- čtení jednotlivých znaků int read()
- čtení pole znaků int read(char [] pole) – nepoužívat - test konce souboru – návratová hodnota -1
- uzavření souboru close()
- ošetření výjimky IOException
Příklad:
Čtení souboru po znacích a výpis na obrazovku, dokud se neobjeví znak '.'
Poznámka Tento postup je nevhodný pro formátovaný vstup čísel
FileReader fr = new FileReader("cti.txt");
FileReader fr = new FileReader(new File("cti.txt"));
int precteno; while((precteno = fr.read()) != -1){ System.out.print((char)precteno); }
Strana 11 (celkem 38)
Zápis - třída FileWriter
- instance třídy (otevření souboru) – 2 možnosti:
- zápis jednotlivých znaků void write(int c) - zápis řetězce void write (String s) - nutnost odřádkování - uzavření souboru close() - ošetření výjimky IOException
FileWriter fw = new FileWriter ("zapis.txt");
FileWriter fw = new FileWriter (new File("zapis.txt"));
import java.io.*;
public class CteniSouboruPoZnacich {
public static void main (String [] args){ try { FileReader fr = new FileReader("cti.txt"); // path int nacti; while ((nacti = fr.read()) != '.'){ // '.' --> -1
System.out.print((char) nacti); } System.out.println(); fr.close(); } catch (IOException e){ e.printStackTrace(); System.exit(1); } } }
Ahoj, jak se mas? Ja se mam dobre
Strana 12 (celkem 38)
Příklad: zápis znaku a řetězce do souboru
B. Řešení vhodné i pro zápis čísel - viz dále
Zavedeme nadstavbu – doplňkové třídy tzv. filtry, v konstruktorech tvoří objekty tříd
bufferování - třídy BufferedReader, BufferedWriter
- urychlení zpracování užitím vyrovnávací paměti
výstupní formátování - print(), format()
import java.io.*;
public class ZapisDoSouboruZnaky {
public static void main (String [] args){ try { FileWriter fw = new FileWriter("zapis.txt"); char znak = 'A'; fw.write(znak); fw.write("hoj,\n"); // win editor – nezobrazi ok String s = "jak se mas?\r\n"; // ok fw.write(s); fw.close(); } catch (IOException e){ e.printStackTrace(); System.exit(1); } } }
Ahoj, jak se mas?
Strana 13 (celkem 38)
BufferedReader
- umožňuje čtení po řádcích, znaky konce řádků automaticky ořezává
- metoda String readLine() - konec souboru null
- rychlejší zpracování než pomocí Scanner
BufferedWriter
konec řádky dle platformy!
void newLine()
Příklad: čtení souboru celých čísel a zápis do souboru jejich mocnin (pomalejší - Scanner)
public static void main (String [] args){ try { Scanner sc = new Scanner(new File("cisla.txt")); //path PrintWriter pw = new PrintWriter( new BufferedWriter( new FileWriter("mocniny.txt"))); //path
while(sc.hasNextInt()){ int cislo = sc.nextInt(); pw.print(cislo*cislo + " "); } pw.println(); sc.close(); pw.close(); } catch (IOException e){ e.printStackTrace(); // vstup soubor 1 2 3 4 5 6 System.exit(1); }}}
1 4 9 16 25 36
Strana 14 (celkem 38)
Příklad: totéž, ale rychlejší zpracování (bez Scanneru)
import java.io.*; import java.util.*;
public class CteniAZapisCiselRychle {
public static void main (String [] args){ try { BufferedReader bfr = new BufferedReader( new FileReader("cisla.txt"));//path
PrintWriter pw = new PrintWriter( new BufferedWriter( new FileWriter("mocniny.txt"))); //path String radka; while((radka = bfr.readLine())!= null){ String []cisla = radka.split(" "); // rozdeleni na podretezce
for(int i=0; i<cisla.length;i++){ int cislo = Integer.parseInt(cisla[i]); pw.print(cislo*cislo + " "); } } pw.println(); bfr.close(); pw.close(); } catch (IOException e){ e.printStackTrace(); System.exit(1); } } // vstupni soubor 1 2 3 4 5 6 }
1 4 9 16 25 36
Strana 15 (celkem 38)
Vzhledem k tomu, že čísla jsou oddělena mezerou, je nutno je získat rozdělením původního řetězce radka na podřetězce – metoda split()
Upozornění: metoda split() funguje pouze při oddělení
jedinou mezerou!
Podřetězce je pak nutno ještě převést (parsování) na čísla metoda Integer.parseInt()
Příklad: totéž, ale pro čísla double, budeme
počítat odmocniny, a navíc vyřešíme chybu ve vstupním souboru, kde je u jednoho z čísel jako desetinný oddělovač čárka (. vs. ,). Uvedena je pouze úprava sekvence kódu. Podrobnější informace (pro zájemce) – viz Záznamy přednášek.
String radka; while((radka = bfr.readLine())!= null){ radka = radka.replace(',', '.'); // uprava String [] cisla = radka.split(" "); for(int i=0; i<cisla.length;i++){ double cislo = Double.parseDouble(cisla[i]); pw.print(Math.sqrt(cislo) + " "); } } // vstupni soubor 1.0 2,0 3.0 4.0 5.0 6.0
1.0 1.4142135623730951 1.7320508075688772 2.0 2.23606797749979 2.449489742783178
Strana 16 (celkem 38)
Textové soubory – přehled V/V
Příklad použití txt souborů – součin matic
Vygenerujte náhodně dvě celočíselné matice řádu n (řád je zadán z klávesnice) a uložte matice do textových souborů matA.txt a matB.txt.
Z textových souborů přečtěte matici A a matici B, proveďte součin AxB, výsledek - matici C uložte do textového souboru matC.txt. Proveďte rovněž
výpis matic A, B, a C na obrazovku.
txt soubor
ReadLine()
BufferedWriter PrintWriter FileWriter
pw.println()
FileReader BufferedReader
txt soubor
Strana 17 (celkem 38)
import java.io.*; import java.util.*; public class TextFilesExample { static void writeMatrix(String nazev, int[][] matrix) { System.out.println(nazev); for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { System.out.format("%3d ", matrix[i][j]); } System.out.println(); } } static int [][] soucinMatic(int[][] a, int [][] b){
int [][] c = new int[a.length][b[0].length]; for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b[i].length; j++) { int s=0; for (int k = 0; k < a[i].length ; k++){ s += a[i][k] * b[k][j]; } c[i][j] = s; } } return c; }
Strana 18 (celkem 38)
static void writeMatrixToFile (String jmeno, int[][] matrix) { try { final String SOUBOR_OUT = "src\\P08priklady\\example\\" + jmeno; /* pouzijeme-li k oddeleni \ (backslash), pak musi byt zdvojene (viz escape sekvence), v retezci s path lze pouzit i / (slash) */
PrintWriter pw = new PrintWriter( new BufferedWriter( new FileWriter(SOUBOR_OUT))); System.out.print(" File writting - please wait ... "); for(int i=0; i<matrix.length; i++) { for(int j=0; j<matrix[i].length; j++){ pw.print(matrix[i][j] + " "); } pw.println(); } System.out.println(" done."); pw.close(); } catch (IOException e) { System.out.println(jmeno +": Write-File Error."); System.exit(1); } }
static int[][] loadRandomMatrix (int n) { int [][] mat = new int[n][n]; Random r = new Random(); for (int i=0; i<mat.length; i++){ for (int j=0; j<mat[i].length; j++){ mat[i][j] = r.nextInt(10); } } return mat; }
Strana 19 (celkem 38)
static int[][] readMatrixFromFile (String jmeno, int n) {
try {
final String SOUBOR_IN = "src/P08priklady/example/" + jmeno; // priklad pouziti / (slash)
BufferedReader bfr = new BufferedReader( new FileReader(SOUBOR_IN));
int[][] mat = new int[n][n]; System.out.print(" File reading - please wait ...");
String radka; int i=0;
while((radka = bfr.readLine())!= null){ String radkaMat[] = radka.split(" "); for(int j=0; j<radkaMat.length;j++){ mat[i][j] = Integer.parseInt(radkaMat[j]); } i++; }
System.out.println("done."); bfr.close(); return mat; } catch (Exception e) { System.out.println(jmeno + ": Read-file Error."); return null; } }
Strana 20 (celkem 38)
public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Zadej rad matice: "); int n = sc.nextInt(); int [][] matrix = new int[n][n];
matrix = loadRandomMatrix (matrix.length); writeMatrixToFile ("matA.txt", matrix); // zakomentovat matrix = loadRandomMatrix (matrix.length); writeMatrixToFile ("matB.txt", matrix); int [][] a = new int[n][n]; int [][] b = new int[n][n]; if(a = readMatrixFromFile ("matA.txt", n) == null) System.exit(1); // chyba: matA.txt neexistuje
if((b = readMatrixFromFile ("matB.txt", n)) == null) System.exit(1);
writeMatrix("A", a); writeMatrix("B", b); int [][] c = new int[n][n]; c = soucinMatic(a, b);
writeMatrix("C", c); writeMatrixToFile ("matC.txt", c); } }
Strana 21 (celkem 38)
Pokud by byl zakomentován tmavožlutě označený příkaz (viz výše), nevytvoří se soubor matA.txt a
následně vznikne chyba při pokusu o jeho čtení:
Zpracování binárních souborů*
pro zájemce (doporučeno oboru Informatika)
- načítají se byty, bez konverze - omezíme se pouze na primitivní typy (ne objekty) - data jsou v pořadí big-endian (viz přednáška 11)
Zadej rad matice: 3 File writting - please wait ... done. File writting - please wait ... done. File reading - please wait ... done. File reading - please wait ... done. A 1 7 1 2 8 4 1 8 3 B 2 8 5 1 6 4 1 3 5 C 10 53 38 16 76 62 13 65 52 File writting - please wait ... done.
Zadej rad matice: 3 File writting - please wait ... done. File reading - please wait ... matA.txt: Read-file Error.
Strana 22 (celkem 38)
Základní třídy
Čtení - FileInputStream
- instance (otevření souboru) – 2 způsoby
- čtení byty int read() - čtení pole bytů int read(byte [] pole) - uzavření souboru close() - ošetření výjimky IOException
Zápis - FileOutputStream
- instance třídy (otevření souboru) – 2 možnosti:
- zápis jednotlivých bytů void write(int b) - uzavření souboru close() - ošetření výjimky IOException
Třídy vlastností – bufferování BufferedInputStream BufferedOutputStream
FileInputStream fis = new FileInputStream("inData.bin"); FileInputStream fis = new FileInputStream ( new File("inData.bin"));
FileOutputStream fos = new FileOutputStream ("outData.bin"); FileOutputStream fos = new FileOutputStream (
new File("outData.bin"));
Strana 23 (celkem 38)
Důležité třídy
DataInputStream metody
- int readInt() - double readDouble() - test konce – EOFException
DataOutputStream metody
- void writeInt(int i) - void writeDouble (double d)
Práce se soubory (txt, bin) – tabulka
úroveň Txt (char) Bin (byte) abstraktní Reader InputStream fyzická FileReader FileInputStream logická (vlastnosti, filtry)
BufferedReader BufferedInputStream
úroveň Txt (char) Bin (byte) abstraktní Writer OutputStream fyzická FileWriter FileOutputStream logická (vlastnosti, filtry)
BufferedWriter BufferedOutputStream
Strana 24 (celkem 38)
Příklad – zápis a opětovné načtení binárních dat
import java.io.*;
public class RWData {
public static void main(String [] args) throws IOException {
DataOutputStream dataOut; DataInputStream dataIn; int i =10; double d = 1234.56; boolean b = true; try{ // zapis dat dataOut = new DataOutputStream( new FileOutputStream("outData.bin")); // path } catch (IOException e){ System.out.println("Soubor nelze otevrit!"); return; } try { System.out.println("zapis " + i); dataOut.writeInt(i); System.out.println("zapis " + d); dataOut.writeDouble(d); System.out.println("zapis " + b); dataOut.writeBoolean(b); System.out.println("zapis " + 12.2 * 7.4); dataOut.writeDouble(12.2 * 7.4); } catch(IOException e){ System.out.println("Chyba pri zapisu."); } dataOut.close();
System.out.println(); // nasleduje cteni dat
Strana 25 (celkem 38)
Rekurze* (znát základ techniky a použití, více v PPA2!)
try { dataIn = new DataInputStream( new FileInputStream("outData.bin")); // path } catch (IOException e){ System.out.println("Soubor nelze otevrit!"); return; } try { i = dataIn.readInt(); System.out.println("cteni " + i); d = dataIn.readDouble(); System.out.println("cteni " + d); b = dataIn.readBoolean(); System.out.println("cteni " + b); d = dataIn.readDouble(); System.out.println("cteni " + d); } catch (IOException e){ System.out.println("Chyba pri cteni."); } dataIn.close(); } }
zapis 10 zapis 1234.56 zapis true zapis 90.28 cteni 10 cteni 1234.56 cteni true cteni 90.28
Rekurzivní metoda
- opakované vnořené volání metody (podprogramu)
- obsahuje podmínku ukončení (zastavení vnořování)
Chyba v rekurzi může způsobit vyčerpání zásobníku, „zacyklení programu“.
Strana 26 (celkem 38)
Rozlišujeme rekurzi
- přímou (vnitřní) – metoda volá sama sebe
- nepřímou (vnější) – metoda volá jinou metodu a volaná metoda volá metodu volající
Ilustrační příklad programu s rekurzivní metodou:
Obrácený výpis zadaných číslic
Důležité!
import java.util.*; /** Nacita cislice, dokud neni zadana 0, pak vypise zadane cislice v obracenem poradi (bez 0) */
public class RekurzivniVypis { static private Scanner sc = new Scanner(System.in);
static void obrat() { // rekurzivni metoda
int x = sc.nextInt(); // vstup dat if (x!=0){ // podminka zastaveni !!!
obrat(); // rekurze: volání „sama sebe“ System.out.print(x + " "); // vypis } }
public static void main(String[] args) { obrat(); System.out.println(); } }
1 2 3 4 5 0 5 4 3 2 1
Rekurzivní metodu používáme jen tehdy, vede-li na ni algoritmus, který nelze snadno obejít.
Rekurzi lze často snadno nahradit iteračním přepisem či použitím zásobníku.
Strana 27 (celkem 38)
Motivační příklad (k dalšímu výkladu)
Šachové věže
Představte si čtvercovou šachovnici o počtu políček N2,
pro N platí, že 0 < N < 13. Na šachovnici je rozestaveno N šachových věží tak, že se žádné dvě z nich navzájem neohrožují (tj. v každém řádku a každém sloupci je právě jedna věž). Vaším úkolem je pro zadané N zjistit, kolika různými způsoby lze věže na šachovnici takto rozmístit.
Další způsoby řešení úlohy:
00, 11, 22, 33, 44, 55, 66, 77
01, 12, 23, 34, 45, 56, 67, 70
....
07, 16, 25, 34, 43, 52, 61, 70
.... 70, 61, 52, 43, 34, 25, 16, 07
Řešení?
N!
Strana 28 (celkem 38)
static long faktorialRekurzivne(int n) { if (n == 0) // podminka zastaveni
return 1; else return n* faktorialRekurzivne (n-1); // rekurzivni volani
}
Iterační výpočet N!:
Rekurzivní výpočet N!:
Jiné způsoby výpočtu N!:
static long faktorialBezRekurze(int n) { long f = 1; for (int i = 2; i <= n; i++) { f *= i; } return f; }
static double faktorialLogaritmem(int n) { double s = 0; if (n >=0) { for (int i =1; i <= n; i++) { s += Math.log(i); } }
return Math.pow(Math.E,s); } //=================================================
static double StirlinguvVzorec (int n) {
return
Math.sqrt(2*Math.PI*n)*Math.pow(n,n)*Math.exp(-n)); }
Strana 29 (celkem 38)
Jednou z nejhorších aplikací je rekurzivní algoritmus pro Fibonacciho posloupnost (*ukázka porovnání algoritmů).
Leonardo Fibonacci (okolo 1180? - 1250) - známý jako Leonardo z Pisy,
Leonardo Pisano, Leonardo Bigollo, Leonardo Bonacci, Fibonacci
- středověký italský matematik - rozšíření používání arabských číslic v Evropě
[zdroj: Wiki]
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
F2 = F0 + F1
Použít iterační výpočet (viz dále + přednáška č. 3)
Proč nepoužít předchozí rekurzi? Ukázka*: použití metody „rozděl a panuj“ (Divide and Conquer)
Výpočet pro hodnotu 5:
hodnotu 3 spočítáme 2x, hodnotu 2 spočítáme 3x a na triviální hodnoty (0, 1) dokonce 8x.
Není efektivní!
static int fibRekurze(int n) { // REKURZE if(n==0 || n==1){ return n; } else { return fibRekurze(n-1) + fibRekurze(n-2); } }
!!!NE
Strana 30 (celkem 38)
Praktický příklad použití rekurze
Hanojské věže - matematický hlavolam
autorem francouzský matematik Édouard Lucas (1883)
François Édouard Anatole Lucas
(4. duben 1842 Amiens - 3. říjen 1891)
- studium Fibonacciho posloupnosti (Lucasovy posl.)
- vzorec udávající hodnotu n-tého členu Fibonacciho posloupnosti.
[zdroj: Wiki]
static long fibIterace(long n){ // ITERACE
if(n==0 || n==1){ return n; } else{ long f0 = 0; long f1 = 1; for(int i=2; i<=n; i++){ long f2 = f0 + f1; f0 = f1; f1 = f2; } return f1; }}
ANO!
Strana 31 (celkem 38)
Úkolem - přemístění všech disků umístěných na jedné z věží na jinou věž, prostřednictvím další věže
Strana 32 (celkem 38)
Poznámka Podmínka zastavení je důležitá, jinak rekurze pokračuje dokud nedojde k chybě „přetečení zásobníku“ (více informací v PPA2).
Vypráví se legenda, že ve Vietnamu stojí chrám, v němž jsou hanojské věže se 64 zlatými kotouči. Mniši (kněží) každý den v poledne za zvuku zvonů slavnostně přemístí jeden kotouč (v jiných verzích probíhá přemisťování nepřetržitě).
V okamžiku, kdy bude přemístěn poslední kotouč, nastane konec světa.
Vyřešení tohoto hlavolamu pro 64 kotoučů však vyžaduje
264
−1=18 446 744 073 709 551 615 tahů,
takže
i kdyby mniši stihli provést jeden tah každou vteřinu (a i kdyby postupovali nejkratším možným způsobem), trvalo by jim vyřešení celého hlavolamu přibližně 600 miliard let.
import java.util.*;
public class HanojskeVeze {
static private Scanner sc = new Scanner(System.in);
public static void presunDisky(int n, char zVeze, char naVez, char presVez) {
if (n==1) // podminka zastaveni !! System.out.println("Presun disk "+n+" z veze "+zVeze+" na " +naVez);
else { presunDisky(n-1, zVeze, presVez, naVez); System.out.println("presun disk "+n+" z "+zVeze+" na " + naVez);
presunDisky(n-1, presVez, naVez, zVeze); } }
public static void main(String[] args) { System.out.print("Zadej pocet disku: "); int n = sc.nextInt(); System.out.println("Presouvani:"); presunDisky(n, 'A', 'B', 'C'); } }
// Cisla disku: 1 az n
// 1 nejmenší disk
Zadej pocet disku: 3 Presouvani: Presun disk 1 z veze A na B presun disk 2 z A na C Presun disk 1 z veze B na C presun disk 3 z A na B Presun disk 1 z veze C na A presun disk 2 z C na B Presun disk 1 z veze A na B
Strana 33 (celkem 38)
Motivační příklad (k použití souborů)
(předváděný na předchozí přednášce)
Zadání: Výsledky rozsáhlého měření, ve kterém byla zkoumána kvalita přenosu harmonického signálu, jsou zapsány v jednotlivých souborech archivu mereni.zip. Část měření byla ovlivněna
poruchami, takže jen v několika souborech se nachází nezkreslený přijatý signál, který představuje sinusovku. Amplitudy signálu jsou velmi různorodé, stejně jako počet přijatých vzorků, tj. hodnot v souboru. Napište program v Javě, který umožní tato naměřená data uložená v souborech předzpracovat, čímž se rozumí vypsat do souboru relevantni-vysledky.txt jména pouze těch
souborů, které obsahují nezkreslenou sinusovku. Postupujte tak, že program vždy přečte jeden soubor, vykreslí jeho hodnoty v přepočteném měřítku na obrazovku a nechá uživatele vizuálně rozhodnout, zda naměřená data představují sinusovku či nikoliv. Uživatel jednoduchým potvrzením na klávesnici rozhodne o platnosti či neplatnosti dat a současně dá pokyn ke čtení dalšího souboru.
Vstup:
adresář mereni s textovými soubory s naměřenými daty
Výstup:
soubor relevantni-vysledky.txt, zobrazení dat
grafem
Strana 34 (celkem 38)
Strana 35 (celkem 38)
package P08priklady.prikladPredzpracovaniDat;
/** Vysledky mereni: v souborech mereni001.txt až merenixyz.txt. */
import java.io.*; import java.util.*; import ppa1.*;
/** * @author besoft (doc. Ing. Josef Kohout, Ph.D.) */
public class PredzpracovanaMereni { private static final int cx = 800; private static final int cy = 600; // TODO: zmenit tak, aby ukazovalo na prislusny vstupni soubor // takto na urovni src
private static final String VYSTUPNI_SOUBOR = "data\\relevantni-vysledky.txt"; private static final String VSTUPNI_ADRESAR = "data\\mereni\\";
/** * precte pole dvojic cisel ze zadaneho souboru * vyhodi vyjimku, pokud soubor neexistuje, ci pri cteni doslo k chybe * @param pathname jmeno souboru * @return pole celych cisel * @throws IOException */ private static double[][] readData(File f) throws IOException { //nejprve zjistit, kolik tam mame radek
FileReader fr = new FileReader(f); BufferedReader r = new BufferedReader(fr);
Strana 36 (celkem 38)
int n = 0;
while (null != r.readLine()){ n++; }
r.close();
//a ted precist data
fr = new FileReader(f); Scanner sc = new Scanner(fr); sc.useLocale(Locale.US); //desetina tecka
double[][] pole = new double[n][2]; //alokace prostoru
for (int i = 0; i < n; i++) { pole[i][0] = sc.nextDouble(); pole[i][1] = sc.nextDouble(); }
fr.close(); return pole; }
/** * @param pole data * @return minimum v poli */
private static double getMin(double[][] pole, int souradnice) { double min = pole[0][souradnice]; for (int i = 1; i < pole.length; i++) { if (pole[i][souradnice] < min) min = pole[i][souradnice]; } return min; } /** * @param pole data * @return maximum v poli */
Strana 37 (celkem 38)
private static double getMax(double[][] pole, int souradnice) { double max = pole[0][souradnice]; for (int i = 1; i < pole.length; i++) { if (pole[i][souradnice] > max) max = pole[i][souradnice]; } return max; } /** * @param dt kreslici zarizeni * @param pole pole hodnot k vykresleni */
private static void plotSimpleGraph(DrawingTool dt, int cx, int cy, double[][] pole) { //zjisti zakladni informace o datech double minX = getMin(pole, 0); double maxX = getMax(pole, 0); double minY = getMin(pole, 1); double maxY = getMax(pole, 1); //potrebujeme vykreslit plochu [minX, maxX] x [minY, maxY] do //oblasti [0, cx] x [0, cy] => budeme potrebovat body prevzorkovat
double scaleX = maxX == minX ? 1.0 : cx / ((double)(maxX - minX)); double scaleY = maxY == minY ? 1.0 : cy / ((double)(maxY - minY)); int lastX = (int)(scaleY*(pole[0][0] - minX)); int lastY = cy - (int)(scaleY*(pole[0][1] - minY)); for (int i = 1; i < pole.length; i++) { int x = (int)(scaleX*(pole[i][0] - minX)); int y = cy - (int)(scaleY*(pole[i][1] - minY));
if (x != lastX || y != lastY) { dt.line(lastX, lastY, x, y); lastX = x; lastY = y; } }
//jeste vykreslit, pro jistotu, posledni bod
dt.line(lastX, lastY, lastX, lastY); }
Strana 38 (celkem 38)
/** * entry point * @param args */
public static void main(String[] args) { //vytvor kreslici plochu
DrawingTool dt = new DrawingTool(cx, cy); Scanner sc = new Scanner(System.in); try { FileWriter wr = new FileWriter(VYSTUPNI_SOUBOR); int cislo = 1; while (true) { String filename = String.format("mereni%03d.txt", cislo); File f = new File(VSTUPNI_ADRESAR + filename); if (!f.exists()) { break; } //zadny dalsi soubor neexistuje System.out.println("Nacitam soubor " + filename + "."); //nacti data
double[][] pole = readData(f); // System.out.println("Zobrazuji '" + filename + "'."); // zobrazujeme data
plotSimpleGraph(dt, cx, cy, pole); System.out.print("Je signal v poradku? [A/N]: "); char c = (char)sc.next().charAt(0); sc.nextLine(); if (c == 'a' || c == 'A') { wr.write(filename + "\n"); } System.out.println(); dt.clear(); cislo++; } wr.close(); System.out.println("Done."); } catch (IOException e) { System.out.println("Chyba pri zapisu vysledku."); } } // soubor } // relevantni-vysledky:
mereni023.txt mereni031.txt mereni052.txt mereni059.txt