[inizio] [indice generale] [precedente] [successivo] [indice analitico] [contributi]


173. Java: esempi di programmazione

Questo capitolo raccoglie solo alcuni esempi di programmazione, in parte gi descritti in altri capitoli. Lo scopo di questi esempi solo didattico, utilizzando forme non ottimizzate per la velocit di esecuzione.

173.1 Problemi elementari di programmazione

In questa sezione vengono mostrati alcuni algoritmi elementari portati in Java. Per la spiegazione degli algoritmi, se non sono gi conosciuti, occorre leggere quanto riportato nel capitolo 152.

173.1.1 Somma tra due numeri positivi

Il problema della somma tra due numeri positivi, attraverso l'incremento unitario, stato descritto nella sezione 152.2.1.

//=====================================================================
// java SommaApp <x> <y>
// Somma esclusivamente valori positivi.
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class SommaApp {

    //-----------------------------------------------------------------
    static int somma(int x, int y) {

        int i;
	int z = x;

	for ( i = 1; i <= y; i++ ) {

	    z ++;
	}

	return z;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int x;
	int y;

	x = Integer.valueOf(args[0]).intValue();
	y = Integer.valueOf(args[1]).intValue();

	System.out.println( x + "+" + y + "=" + somma( x, y ) );
    }

}
//=====================================================================

In alternativa si pu tradurre il ciclo `for' in un ciclo `while'.

    static int somma(int x, int y) {

	int z = x;
        int i = 1;

	while ( i <= y ) {

	    z ++;
	    i ++;
	}

	return z;
    }

173.1.2 Moltiplicazione di due numeri positivi attraverso la somma

Il problema della moltiplicazione tra due numeri positivi, attraverso la somma, stato descritto nella sezione 152.2.2.

//=====================================================================
// java MoltiplicaApp <x> <y>
// Moltiplica esclusivamente valori positivi.
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class MoltiplicaApp {

    //-----------------------------------------------------------------
    static int moltiplica(int x, int y) {

        int i;
	int z = 0;

	for ( i = 1; i <= y; i++ ) {

	    z = z + x;
	}

	return z;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int x;
	int y;

	x = Integer.valueOf(args[0]).intValue();
	y = Integer.valueOf(args[1]).intValue();

	System.out.println( x + "*" + y + "=" + moltiplica( x, y ) );
    }

}
//=====================================================================

In alternativa si pu tradurre il ciclo `for' in un ciclo `while'.

    static int moltiplica(int x, int y) {

	int z = 0;
        int i = 1;

	while ( i <= y ) {

	    z = z + x;
	    i ++;
	}

	return z;
    }

173.1.3 Divisione intera tra due numeri positivi

Il problema della divisione tra due numeri positivi, attraverso la sottrazione, stato descritto nella sezione 152.2.3.

//=====================================================================
// java DividiApp <x> <y>
// Divide esclusivamente valori positivi.
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class DividiApp {

    //-----------------------------------------------------------------
    static int dividi(int x, int y) {

	int z = 0;
        int i = x;

	while ( i >= y ) {

	    i = i - y;
	    z ++;
	}

	return z;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int x;
	int y;

	x = Integer.valueOf(args[0]).intValue();
	y = Integer.valueOf(args[1]).intValue();

	System.out.println( x + ":" + y + "=" + dividi( x, y ) );
    }

}
//=====================================================================

173.1.4 Elevamento a potenza

Il problema dell'elevamento a potenza tra due numeri positivi, attraverso la moltiplicazione, stato descritto nella sezione 152.2.4.

//=====================================================================
// java ExpApp <x> <y>
// Elevamento a potenza di valori positivi interi.
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class ExpApp {

    //-----------------------------------------------------------------
    static int exp(int x, int y) {

	int z = 1;
        int i;

	for ( i = 1; i <= y; i ++ ) {

	    z = z * x;
	}

	return z;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int x;
	int y;

	x = Integer.valueOf(args[0]).intValue();
	y = Integer.valueOf(args[1]).intValue();

	System.out.println( x + "**" + y + "=" + exp( x, y ) );
    }

}
//=====================================================================

In alternativa si pu tradurre il ciclo `for' in un ciclo `while'.

    static int exp(int x, int y) {

	int z = 1;
        int i = 1;

	while ( i <= y ) {

	    z = z * x;
	    i ++;
	}

	return z;
    }

Infine, si pu usare anche un algoritmo ricorsivo.

    static int exp(int x, int y) {

	if ( x == 0 ) {
	    return 0;
	} else if ( y == 0 ) {
	    return 1;
	} else {
	    return ( x * exp( x, y-1 ) );
	}
    }

173.1.5 Radice quadrata

Il problema della radice quadrata stato descritto nella sezione 152.2.5.

//=====================================================================
// java RadiceApp <x>
// Estrazione della parte intera della radice quadrata.
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class RadiceApp {

    //-----------------------------------------------------------------
    static int radice(int x) {

	int z = 0;
        int t = 0;

	while ( true ) {

	    t = z * z;

            if ( t > x ) {
                //  stato superato il valore massimo.
                z --;
                return z;
            }

            z ++;
	}
        // Teoricamente, non dovrebbe mai arrivare qui.
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int x;

	x = Integer.valueOf(args[0]).intValue();

	System.out.println( "radq(" + x + ")=" + radice( x ) );
    }

}
//=====================================================================

173.1.6 Fattoriale

Il problema del fattoriale stato descritto nella sezione 152.2.6.

//=====================================================================
// java FattorialeApp <x>
// Calcola il fattoriale di un valore intero.
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class FattorialeApp {

    //-----------------------------------------------------------------
    static int fattoriale(int x) {

	int i = x - 1;

	while ( i > 0 ) {

	    x = x * i;
	    i --;

	}

	return x;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int x;

	x = Integer.valueOf(args[0]).intValue();

	System.out.println( x + "! = " + fattoriale( x ) );
    }

}
//=====================================================================

In alternativa, l'algoritmo si pu tradurre in modo ricorsivo.

    static int fattoriale(int x) {

        if ( x > 1 ) {
            return ( x * fattoriale( x - 1 ) );
        } else {
            return 1;
        }

        // Teoricamente non dovrebbe arrivare qui.
    }

173.1.7 Massimo comune divisore

Il problema del massimo comune divisore, tra due numeri positivi, stato descritto nella sezione 152.2.7.

//=====================================================================
// java MCDApp <x> <y>
// Determina il massimo comune divisore tra due numeri interi positivi.
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class MCDApp {

    //-----------------------------------------------------------------
    static int mcd(int x, int y) {

        int i;
	int z = 0;

        while ( x != y ) {

            if ( x > y ) {
                x = x - y;
            } else {
                y = y - x;
            }
        }

        return x;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int x;
	int y;

	x = Integer.valueOf(args[0]).intValue();
	y = Integer.valueOf(args[1]).intValue();

	System.out.println( "Il massimo comune divisore tra " + x +
	    " e " + y + "  " + mcd( x, y ) );
    }

}
//=====================================================================

173.1.8 Numero primo

Il problema della determinazione se un numero sia primo o meno, stato descritto nella sezione 152.2.8.

//=====================================================================
// java PrimoApp <x>
// Determina se un numero sia primo o meno.
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class PrimoApp {

    //-----------------------------------------------------------------
    static boolean primo(int x) {

        boolean primo = true;
        int i = 2;
        int j;

        while ( ( i < x ) && primo ) {

            j = x / i;
            j = x - ( j * i );

            if ( j == 0 ) {
                primo = false;
            } else {
                i++;
            }
        }

        return primo;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int x;

	x = Integer.valueOf(args[0]).intValue();

	if ( primo( x ) ) {
	    System.out.println( x + "  un numero primo" );
	} else {
	    System.out.println( x + " non  un numero primo" );
	}
    }

}
//=====================================================================

173.2 Scansione di array

In questa sezione vengono mostrati alcuni algoritmi, legati alla scansione degli array, portati in Java. Per la spiegazione degli algoritmi, se non sono gi conosciuti, occorre leggere quanto riportato nel capitolo 152.

173.2.1 Ricerca sequenziale

Il problema della ricerca sequenziale all'interno di un array, stato descritto nella sezione 152.3.1.

//=====================================================================
// java RicercaSeqApp.java
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class RicercaSeqApp {

    //-----------------------------------------------------------------
    static int ricercaseq(int[] lista, int x, int a, int z) {

	int i;

	//-------------------------------------------------------------
	// Scandisce l'array alla ricerca dell'elemento.
	//-------------------------------------------------------------
	for ( i = a; i <= z; i++ ) {

	    if ( x == lista[i] ) {

		return i;
	    }
	}

	//-------------------------------------------------------------
	// La corrispondenza non  stata trovata.
	//-------------------------------------------------------------
	return -1;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int[] lista = new int[args.length-1];
	int x;
	int i;

	//-------------------------------------------------------------
	// Conversione degli argomenti della riga di comando in
	// numeri.
	//-------------------------------------------------------------
	x = Integer.valueOf(args[0]).intValue();

	for ( i = 1; i < args.length; i ++ ) {
	    lista[i-1] = Integer.valueOf(args[i]).intValue();
	}

	//-------------------------------------------------------------
	// Esegue la ricerca.
	// In Java, gli array sono oggetti, e come tali vengono passati
	// per riferimento.
	//-------------------------------------------------------------
	i = ricercaseq( lista, x, 0, lista.length-1);

	//-------------------------------------------------------------
	// Visualizza il risultato.
	//-------------------------------------------------------------
	System.out.println( x + " si trova nella posizione " +
	    i + "." );
    }

}
//=====================================================================

Esiste anche una soluzione ricorsiva che viene mostrata nella subroutine seguente:

    static int ricercaseq(int[] lista, int x, int a, int z) {

	if ( a > z ) {

	    //---------------------------------------------------------
	    // La corrispondenza non  stata trovata.
	    //---------------------------------------------------------
	    return -1;

	} else if ( x == lista[a] ) {

	    return a;

	} else {

	    return ricercaseq ( lista, x, a+1, z );
	}
    }

173.2.2 Ricerca binaria

Il problema della ricerca binaria all'interno di un array, stato descritto nella sezione 152.3.2.

//=====================================================================
// java RicercaBinApp.java
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class RicercaBinApp {

    //-----------------------------------------------------------------
    static int ricercabin(int[] lista, int x, int a, int z) {

	int m;

	//-------------------------------------------------------------
	// Determina l'elemento centrale.
	//-------------------------------------------------------------
	m = ( a + z ) / 2;

	if ( m < a ) {
	    //---------------------------------------------------------
	    // Non restano elementi da controllare: l'elemento cercato
	    // non c'.
	    //---------------------------------------------------------
	    return -1;

	} else if ( x < lista[m] ) {
	    //---------------------------------------------------------
	    // Si ripete la ricerca nella parte inferiore.
	    //---------------------------------------------------------
	    return ricercabin( lista, x, a, m-1 );

	} else if ( x > lista[m] ) {
	    //---------------------------------------------------------
	    // Si ripete la ricerca nella parte superiore.
	    //---------------------------------------------------------
	    return ricercabin( lista, x, m+1, z );

	} else {
	    //---------------------------------------------------------
	    // m rappresenta l'indice dell'elemento cercato.
	    //---------------------------------------------------------
	    return m;
	}
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int[] lista = new int[args.length-1];
	int x;
	int i;

	//-------------------------------------------------------------
	// Conversione degli argomenti della riga di comando in
	// numeri.
	//-------------------------------------------------------------
	x = Integer.valueOf(args[0]).intValue();

	for ( i = 1; i < args.length; i ++ ) {
	    lista[i-1] = Integer.valueOf(args[i]).intValue();
	}

	//-------------------------------------------------------------
	// Esegue la ricerca.
	// In Java, gli array sono oggetti, e come tali vengono passati
	// per riferimento.
	//-------------------------------------------------------------
	i = ricercabin( lista, x, 0, lista.length-1);

	//-------------------------------------------------------------
	// Visualizza il risultato.
	//-------------------------------------------------------------
	System.out.println( x + " si trova nella posizione " +
	    i + "." );
    }

}
//=====================================================================

173.3 Algoritmi tradizionali

In questa sezione vengono mostrati alcuni algoritmi tradizionali portati in Java. Per la spiegazione degli algoritmi, se non sono gi conosciuti, occorre leggere quanto riportato nel capitolo 152.

173.3.1 Bubblesort

Il problema del Bubblesort stato descritto nella sezione 152.4.1. Viene mostrata prima una soluzione iterativa, e in seguito il metodo `bsort' in versione ricorsiva.

//=====================================================================
// java BSortApp.java
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class BSortApp {

    //-----------------------------------------------------------------
    static int[] bsort(int[] lista, int a, int z) {

	int scambio;
	int j;
	int k;

	//-------------------------------------------------------------
	// Inizia il ciclo di scansione dell'array.
	//-------------------------------------------------------------
	for ( j = a; j < z; j++ ) {

	    //---------------------------------------------------------
	    // Scansione interna dell'array per collocare nella
	    // posizione j l'elemento giusto.
	    //---------------------------------------------------------
	    for ( k = j+1; k <= z; k++ ) {

		if ( lista[k] < lista[j] ) {

		    //-------------------------------------------------
		    // Scambia i valori
		    //-------------------------------------------------
		    scambio = lista[k];
		    lista[k] = lista[j];
		    lista[j] = scambio;
		}
	    }
	}
	//-------------------------------------------------------------
	// In Java, gli array sono oggetti, e come tali vengono passati
	// per riferimento. Qui si restituisce ugualmente un
	// riferimento all'array ordinato.
	//-------------------------------------------------------------
	return lista;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int[] lista = new int[args.length];
	int i;

	//-------------------------------------------------------------
	// Conversione degli argomenti della riga di comando in
	// numeri.
	//-------------------------------------------------------------
	for ( i = 0; i < args.length; i ++ ) {
	    lista[i] = Integer.valueOf(args[i]).intValue();
	}

	//-------------------------------------------------------------
	// Ordina l'array.
	// In Java, gli array sono oggetti, e come tali vengono passati
	// per riferimento.
	//-------------------------------------------------------------
	 bsort( lista, 0, args.length-1);

	//-------------------------------------------------------------
	// Visualizza il risultato.
	//-------------------------------------------------------------
	for ( i = 0; i < lista.length; i ++ ) {
	    System.out.println( "lista[" + i + "] = " +
		lista[i] );
	}
    }

}
//=====================================================================

Segue il metodo `bsort' in versione ricorsiva.

    static int[] bsort(int[] lista, int a, int z) {

	int scambio;
	int k;

	if ( a < z ) {

	    //---------------------------------------------------------
	    // Scansione interna dell'array per collocare nella
	    // posizione a l'elemento giusto.
	    //---------------------------------------------------------
	    for ( k = a+1; k <= z; k++ ) {
		if ( lista[k] < lista[a] ) {

		    //-------------------------------------------------
		    // Scambia i valori
		    //-------------------------------------------------
		    scambio = lista[k];
		    lista[k] = lista[a];
		    lista[a] = scambio;
		}
	    }

	    bsort( lista, a+1, z );
	}

	return lista;
    }

173.3.2 Torre di Hanoi

Il problema della torre di Hanoi stato descritto nella sezione 152.4.2.

//=====================================================================
// java HanoiApp <n-anelli> <piolo-iniziale> <piolo-finale>
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class HanoiApp {

    //-----------------------------------------------------------------
    static void hanoi(int n, int p1, int p2) {

	if ( n > 0 ) {

	    hanoi( n-1, p1, 6-p1-p2 );
	    System.out.println(
		"Muovi l'anello " + n +
		" dal piolo " + p1 +
		" al piolo " + p2 + "."
	    );
	    hanoi( n-1, 6-p1-p2, p2 );

	}
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int n;
	int p1;
	int p2;

	n = Integer.valueOf(args[0]).intValue();
	p1 = Integer.valueOf(args[1]).intValue();
	p2 = Integer.valueOf(args[2]).intValue();

	hanoi( n, p1, p2 );
    }

}
//=====================================================================

173.3.3 Quicksort

L'algoritmo del Quicksort stato descritto nella sezione 152.4.3.

//=====================================================================
// java QSortApp.java
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class QSortApp {

    //-----------------------------------------------------------------
    static int part(int[] lista, int a, int z) {

	int scambio;

	//-------------------------------------------------------------
	// Si assume che a sia inferiore a z.
	//-------------------------------------------------------------
	int i = a + 1;
	int cf = z;

	//-------------------------------------------------------------
	// Inizia il ciclo di scansione dell'array.
	//-------------------------------------------------------------
	while ( true ) {

	    while ( true ) {

		//-----------------------------------------------------
		// Sposta i a destra.
		//-----------------------------------------------------
		if ( (lista[i] > lista[a]) || (i >= cf) ) {
		    break;
		} else {
		    i ++;
		}

	    }
	
	    while ( true ) {

		//-----------------------------------------------------
		// Sposta cf a sinistra.
		//-----------------------------------------------------
		if (lista[cf] <= lista[a]) {
		    break;
		} else {
		    cf --;
		}

	    }

	    if ( cf <= i ) {
		//-----------------------------------------------------
		//  avvenuto l'incontro tra i e cf.
		//-----------------------------------------------------
		break;
	    } else {
		//-----------------------------------------------------
		// Vengono scambiati i valori.
		//-----------------------------------------------------
		scambio = lista[cf];
		lista[cf] = lista[i];
		lista[i] = scambio;

		i ++;
		cf --;
	    }
	}

	//-------------------------------------------------------------
	// A questo punto lista[a..z]  stata ripartita e cf  la
	// collocazione di lista[a].
	//-------------------------------------------------------------
	scambio = lista[cf];
	lista[cf] = lista[a];
	lista[a] = scambio;

	//-------------------------------------------------------------
	// A questo punto, lista[cf]  un elemento (un valore) nella
	// giusta posizione.
	//-------------------------------------------------------------
	
	return cf;
    }

    //-----------------------------------------------------------------
    static int[] quicksort(int[] lista, int a, int z) {

	int cf;

	if ( z > a ) {
	    cf = part ( lista, a, z);
	    quicksort ( lista, a, cf-1);
	    quicksort ( lista, cf+1, z);
	}

	//-------------------------------------------------------------
	// In Java, gli array sono oggetti, e come tali vengono passati
	// per riferimento. Qui si restituisce ugualmente un
	// riferimento all'array ordinato.
	//-------------------------------------------------------------
	return lista;
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int[] lista = new int[args.length];
	int i;

	//-------------------------------------------------------------
	// Conversione degli argomenti della riga di comando in
	// numeri.
	//-------------------------------------------------------------
	for ( i = 0; i < args.length; i ++ ) {
	    lista[i] = Integer.valueOf(args[i]).intValue();
	}

	//-------------------------------------------------------------
	// Ordina l'array.
	// In Java, gli array sono oggetti, e come tali vengono passati
	// per riferimento.
	//-------------------------------------------------------------
	quicksort( lista, 0, args.length-1);

	//-------------------------------------------------------------
	// Visualizza il risultato.
	//-------------------------------------------------------------
	for ( i = 0; i < lista.length; i ++ ) {
	    System.out.println( "lista[" + i + "] = " +
		lista[i] );
	}
    }

}
//=====================================================================

173.3.4 Permutazioni

L'algoritmo ricorsivo delle permutazioni stato descritto nella sezione 152.4.4.

//=====================================================================
// java PermutaApp.java
//=====================================================================

import java.lang.*; // predefinita

//---------------------------------------------------------------------
class PermutaApp {

    //-----------------------------------------------------------------
    static void permuta(int[] lista, int a, int z) {

	int scambio;
	int k;
	int i;

	//-------------------------------------------------------------
	// Se il segmento di array contiene almeno due elementi, si
	// procede.
	//-------------------------------------------------------------
	if ( (z - a) >= 1 ) {

	    //---------------------------------------------------------
	    // Inizia un ciclo di scambi tra l'ultimo elemento e uno
	    // degli altri contenuti nel segmento di array.
	    //---------------------------------------------------------
	    for ( k = z; k >= a; k-- ) {

		//-----------------------------------------------------
		// Scambia i valori
		//-----------------------------------------------------
		scambio = lista[k];
		lista[k] = lista[z];
		lista[z] = scambio;

		//-----------------------------------------------------
		// Esegue una chiamata ricorsiva per permutare un
		// segmento pi piccolo dell'array.
		//-----------------------------------------------------
		permuta( lista, a, z-1 );

		//-----------------------------------------------------
		// Scambia i valori
		//-----------------------------------------------------
		scambio = lista[k];
		lista[k] = lista[z];
		lista[z] = scambio;

	    }
	} else {

	    //---------------------------------------------------------
	    // Visualizza la situazione attuale dell'array.
	    //---------------------------------------------------------
	    for ( i = 0; i < lista.length; i ++ ) {
		System.out.print( " " + lista[i] );
	    }
	    System.out.println( "" );
	}
    }

    //=================================================================
    // Inizio del programma.
    //-----------------------------------------------------------------
    public static void main(String[] args) {

	int[] lista = new int[args.length];
	int i;

	//-------------------------------------------------------------
	// Conversione degli argomenti della riga di comando in
	// numeri.
	//-------------------------------------------------------------
	for ( i = 0; i < args.length; i ++ ) {
	    lista[i] = Integer.valueOf(args[i]).intValue();
	}

	//-------------------------------------------------------------
	// Esegue le permutazioni.
	//-------------------------------------------------------------
	permuta( lista, 0, args.length-1);
    }

}
//=====================================================================

---------------------------

Appunti Linux 2000.04.12 --- Copyright 1997-2000 Daniele Giacomini -- daniele@pluto.linux.it


[inizio] [indice generale] [precedente] [successivo] [indice analitico] [contributi]