Esercizi del corso di Programmazione Internet

Esercizio 1a

Scrivere un programma Java che accetti dall'utente una sequenza di numeri interi (di lunghezza richiesta precedentemente all'utente), memorizzi ogni valore della sequenza in un array, scandisca l'array per determinare il valore dell'elemento massimo e dell'elemento minimo e li visualizzi.

Esercizio 1b

Riscrivere il programma dell'esercizio 1a in modo che la ricerca dell'elemento massimo, e dell'elemento minimo siano realizzate da due distinti metodi (che opereranno sull'array tramite una reference passata come parametro e che restituiranno il valore cercato).

Esercizio 2a

Facendo uso di un metodo in grado di determinare l'indice dell'elemento di valore massimo in una parte di un array di interi (che quindi accettera' come parametro una reference all'array e l'indice inferiore e superiore fra i quali cercare l'elemento massimo) implementare un programma che accetti input dall'utente e lo memorizzi come per l'esercizio 1a, che ordini gli elementi dell'array in maniera crescente e visualizzi l'array dopo l'ordinamento.

Esercizio 2b

Riscrivere il programma dell'esercizio 2a in modo che gli elementi dell'array non siano digitati dall'utente ma siano numeri casuali fra 0 e 10000.
Visualizzare poi l'array sia prima sia dopo l'ordinamento.

Esercizio 3

Completare il metodo stringToInt della seguente classe:

package pi.util;
/** * A class containing methods to convert * string to numbers and numbers to strings * * @author Davide Rossi * @version 1.0 */ public class Conversions { /** * A method to convert a string to an int * It assumes the string to convert contains * only decimal digits * * @param s the string to convert * @return the value of the conversion */ public static int stringToInt(String s) { return 0; } /** * A method to convert an int to a string * * @param i the int to convert * @return the value of the conversion */ public static String intToString(int i) { String number = ""; boolean isNegative = false; if(i == 0) { number = "0"; } else if(i < 0) { isNegative = true; i = -i; } while(i != 0) { int value = i % 10; char[] chars = new char[1]; chars[0] = (char)('0'+value); String digit = new String(chars); number = digit+number; i /= 10; } if(isNegative) { number = "-"+number; } return number; }
}

Esercizio 4

Completare il seguente codice (che va ovviamente posto in due distinti file sorgenti) in modo che il programma ordini tre array di reference di tipo Coord, String e Employee.

public class Sort {
    public static void main(String[] args) {
        final int len = 10;
        Coord[] elements = new Coord[len];

        initArray(elements);

        showArray(elements);

        System.out.println();
        
        sort(elements);

        showArray(elements);
    }

    public static void initArray(Coord[] elements) {
        for(int i = 0; i < elements.length; i++) {
            elements[i] = new Coord();
            elements[i].setX(5-10*Math.random());
            elements[i].setY(5-10*Math.random());
        }
    }

    public static void showArray(Coord[] elements) {
        for(int i = 0; i < elements.length; i++) {
            System.out.println(i+" - "+elements[i].getX()+", "+elements[i].getY()+" d= "+elements[i].distance());
        }
    }

    protected static int maxElement(Comparable[] elements, int inf, int sup) {
        int idx = inf;
        for (int i = inf+1; i < sup; i++) {
            if (elements[i].compareTo(elements[idx]) > 0) {
                idx = i;
            }
        }
        return idx; 
    }

    public static void sort(Comparable[] elements) {
        Comparable tmp;
        int indMax;
        int len = elements.length;
        for(int i = 0; i < len; i++) {
            indMax = maxElement(elements, 0, len-i);
            tmp = elements[len-1-i];
            elements[len-1-i] = elements[indMax];
            elements[indMax] = tmp;
        }
    }
}

public class Coord implements Comparable {
    private double x, y;
    public Coord() {
        x = y = 0;
    }
    public Coord(double x, double y) {
        this.x = x;
        this.y = y;
    }
    public void setX(double x) {
        this.x = x;
    }
    public void setY(double y) {
        this.y = y;
    }
    public double getX() {
        return x;
    }
    public double getY() {
        return y;
    }
    public double distance() {
        return Math.sqrt(x*x+y*y);
    }
    public int compareTo(Object o) {
        Coord other = (Coord)o;
        double d1 = this.distance(),
               d2 = other.distance();
        if(d1 < d2) {
            return -1;
        } else if(d1 == d2) {
            return 0;
        } else {
            return 1;
        }
    }
}

Esercizio 4a (per solutori piu' che abili)

Modificare il programma dell'esercizio 4 in modo che sort implementi l'algoritmo quicksort.

Esercizio 5

Scrivere un programma che produca un serie di oggetti di tipo Employee a partire da dati contenuti in un file.
Questi oggetti devono essere memorizzati all'interno di una lista.
Tale lista deve essere ordinata e visualizzata rispetto a nome, indirizzo e pay rate.
Utilizzare le interfacce e le classi delle collection classes standard di Java (in particolare il metodo public static void sort(List list, Comparator c) in Collections. Per utilizzare in maniera sensata questo metodo si devono creare degli oggetti a partire da delle classi, che vanno scritte, che implementino l'interfaccia Comparator. I metodi compare di queste classi serviranno per comparare fra di loro gli impiegati rispetto al nome, all'indirizzo e al reddito).
Per ogni ulteriore informazione fare riferimento alla documentazione delle API standard di Java.

Esercizio 6

Considerato il seguente programma (ricerca del percorso in un labirinto fra ingresso e uscita):

import java.io.*;
import java.util.*;

public class Maze {
    final static int BRICK = 1;
    final static int EMPTY = 2;
    final static int VISITED = 3;
    final static int EXIT = 4;

    List rows;
    int enterX, enterY, sizeX, sizeY;
    
    public Maze(String fileName) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader(fileName));
        String line;
        rows = new ArrayList();
        int lineCnt = 0;
        do {
            do {
                line = br.readLine();
            } while("".equals(line));
            if(line != null) {
                sizeX = line.length();
                int[] a = new int[line.length()];
                for(int i = 0; i < line.length(); i++) {
                    switch(line.charAt(i)) {
                        case '#': a[i] = BRICK;
                                  break;
                        case ' ': a[i] = EMPTY;
                                  break;
                        case '0': a[i] = VISITED;
                                  enterX = i;
                                  enterY = lineCnt;
                                  break;
                        case '1': a[i] = EXIT;
                                  break;
                    }
                }
                rows.add(a);
                lineCnt++;
            }
        } while(line != null);
        sizeY = lineCnt;
    }

    public boolean isBrick(int x, int y) {
        int[] a = (int[])rows.get(y);
        if(a[x] == BRICK) {
            return true;
        } else {
            return false;
        }
    }

    public boolean isVisited(int x, int y) {
        int[] a = (int[])rows.get(y);
        if(a[x] == VISITED) {
            return true;
        } else {
            return false;
        }
    }

    public boolean isExit(int x, int y) {
        int[] a = (int[])rows.get(y);
        if(a[x] == EXIT) {
            return true;
        } else {
            return false;
        }
    }

    public void markVisited(int x, int y, boolean visited) {
        int[] a = (int[])rows.get(y);
        if(visited) {
            a[x] = VISITED;
        } else {
            a[x] = EMPTY;
        }
    }

    public boolean solve() {
        return visit(enterX, enterY);
    }

    protected boolean visit(int x, int y) {
        if(isExit(x, y)) {
            markVisited(x, y, true);
            return true;
        }
        markVisited(x, y, true);
        <codice mancante>
} public String toString() { String out = ""; for(int y = 0; y < rows.size(); y++) { int[] a = (int[])rows.get(y); for(int x = 0; x < a.length; x++) { char c = ' '; switch(a[x]) { case EMPTY: c = ' '; break; case BRICK: c = '#'; break; case VISITED: c= '.'; break; } out += c; } out += '\n'; } return out; } public static void main(String args[]) { try { Maze maze = new Maze(args[0]); if(!maze.solve()) { System.out.println("Not solvable!"); } else { System.out.println(maze); } } catch(Exception e) { e.printStackTrace(); } } }

a) capirlo;
b) completare il metodo visit. (Nota: ho modificato il programma in modo da marcare visitato un nodo non prima di visitarlo ma mentre lo si visita. Questo permette anche di gestire molto piu' facilmente la "smarcatura" dei nodi);
c) testarlo anche con il seguente file di input:

##0################
#    #   #    #   #
#### # ### ## # # #
#    # # ##   # # #
# ##        ### # #
# ####### #     # #
#       # # ##### #
### ## ######     #
#    #   #    # # #
# #### # # #### ###
#    # # #    #   #
#################1#

d) se proprio non capite come funziona fategli stampare il labirinto ad ogni ingresso nel metodo visit.

Esercizio 7

Sulla falsa riga della alla seguente classe realizzare una classe che implementi le funzionalita' di uno stack (con operazioni push, pop e isEmpty) e una che implementi le funzionalita' di una coda (con operazioni get e put).

package pi.containers;

public class List {

    private class Node {

        Object element;
        Node next;

        public Node(Object element) {
            this.element = element;
        }
        public void setNext(Node next) {
            this.next = next;
        }
        public Node getNext() {
            return next;
        }
        public Object getElement() {
            return element;
        }
    }

    protected Node head;
    protected int size;

    public List() {
        head = null;
        size = 0;
    }

    private Node getNode(int index) {
        if(index < 0) {
            throw new IndexOutOfBoundsException();
        }
        Node curr = head;
        for(int i = 0; i < index; i++) {
            if(curr == null) {
                throw new IndexOutOfBoundsException();
            }
            curr = curr.getNext();
        }
        return curr;
    }

    public void add(Object element) {
        Node node = new Node(element);
        node.setNext(head);
        head = node;
        size++;
    }

    public Object get(int index) {
        return getNode(index).getElement();
    }

    public void add(Object element, int index) {
        Node node = new Node(element);
        Node prevNode;
        if(index == 0) {
            node.setNext(head);
            head = node;
        } else {
            prevNode = getNode(index-1);
            Node nextNode = prevNode.getNext();
            prevNode.setNext(node);
            node.setNext(nextNode);
        }
        size++;
    }

    public void remove(int index) {
        if(index < 0 || head == null) {
            throw new IndexOutOfBoundsException();
        }
        if(index == 0) {
            head = head.getNext();
        } else {
            Node prevNode = getNode(index-1);
            Node node = prevNode.getNext();
            prevNode.setNext(node.getNext());
        }
        size--;
    }

    public int size() {
        return size;
    }
    
    public String toString() {
        String out = "[ ";
        Node currNode = head;
        while(currNode != null) {
            out += currNode.getElement();
            currNode = currNode.getNext();
            if(currNode != null) {
                out += ", ";
            }
        }
        return out+"]";
    }
}

Realizzare poi dei programmi di test che facciano uso delle due classi di cui sopra.

Esercizio 8

Scrivere un programma che legga un file XML avente il formato visto a lezione in baseballstats.xml e scriva un file XML con le stesse informazioni ma facendo in modo che le varie voci relative ad ogni giocatore non siano memorizzate in elementi figli dell'elemento player ma come suoi attributi.
Quindi, ad esempio, l'elemento:

<player>
  <first_name>Garret</first_name> 
  <surname>Anderson</surname> 
  <games_played>156</games_played> 
  <at_bats>622</at_bats> 
...
</player>

diventera':

<player first_name="Garret" surname="Anderson" games_played="156" at_bats="622" ...></player> 

Esercizio 9

Scrivere un DTD per il file prodotto dall'esercizio 8