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


159. C: 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.

159.1 Problemi elementari di programmazione

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

159.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.

/* ================================================================= */
/* somma <x> <y>						     */
/* Somma esclusivamente valori positivi.			     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* somma ( <x>, <y> )						     */
/* ----------------------------------------------------------------- */
int somma( int x, int y ) {

    int z = x;
    int i;

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

    return z;
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int x;
    int y;
    int z;

    /* Converte le stringhe ottenute dalla riga di comando in
       numeri interi e li assegna alle variabili x e y. 	     */
    sscanf( argv[1], "%d", &x );
    sscanf( argv[2], "%d", &y );

    z = somma( x, y );

    printf( "%d + %d = %d\n", x, y, z );
}

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

int somma( int x, int y ) {

    int z = x;
    int i = 1;

    while ( i <= y ) {
        z++;
	i++;
    };

    return z;
}

159.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.

/* ================================================================= */
/* moltiplica <x> <y>						     */
/* Moltiplica esclusivamente valori positivi.			     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* moltiplica ( <x>, <y> )					     */
/* ----------------------------------------------------------------- */
int moltiplica( int x, int y ) {

    int z = 0;
    int i;

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

        z = z + x;
    }

    return z;
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int x;
    int y;
    int z;

    /* Converte le stringhe ottenute dalla riga di comando in
       numeri interi e li assegna alle variabili x e y. 	     */
    sscanf( argv[1], "%d", &x );
    sscanf( argv[2], "%d", &y );

    z = moltiplica( x, y );

    printf( "%d * %d = %d\n", x, y, z );
}

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

int moltiplica( int x, int y ) {

    int z = 0;
    int i = 1;

    while ( i <= y ) {

        z = z + x;
	i++;
    }

    return z;
}

159.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.

/* ================================================================= */
/* dividi <x> <y>						     */
/* Divide esclusivamente valori positivi.			     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* dividi ( <x>, <y> )						     */
/* ----------------------------------------------------------------- */
int dividi( int x, int y ) {

    int z = 0;
    int i = x;

    while ( i >= y ) {

        i = i - y;
        z++;
    }

    return z;
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int x;
    int y;
    int z;

    /* Converte le stringhe ottenute dalla riga di comando in
       numeri interi e li assegna alle variabili x e y. 	     */
    sscanf( argv[1], "%d", &x );
    sscanf( argv[2], "%d", &y );

    z = dividi( x, y );

    printf( "Divisione intera - %d:%d = %d\n", x, y, z );
}

159.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.

/* ================================================================= */
/* exp <x> <y>							     */
/* Eleva a potenza.						     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* exp ( <x>, <y> )						     */
/* ----------------------------------------------------------------- */
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.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int x;
    int y;
    int z;

    /* Converte le stringhe ottenute dalla riga di comando in
       numeri interi e li assegna alle variabili x e y. 	     */
    sscanf( argv[1], "%d", &x );
    sscanf( argv[2], "%d", &y );

    z = exp( x, y );

    printf( "%d ** %d = %d\n", x, y, z );
}

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

int exp( int x, int y ) {

    int z = 1;
    int i = 1;

    while ( i <= y ) {
        z = z * x;
	i++;
    };

    return z;
}

possibile usare anche un algoritmo ricorsivo.

int exp( int x, int y ) {

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

159.1.5 Radice quadrata

Il problema della radice quadrata stato descritto nella sezione 152.2.5.

/* ================================================================= */
/* radice <x>							     */
/* Radice quadrata.						     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* radice ( <x> )						     */
/* ----------------------------------------------------------------- */
int radice( int x ) {

    int z = 0;
    int t = 0;

    while ( 1 ) {

        t = z * z;

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

        z++;
    }

    /* Teoricamente, non dovrebbe mai arrivare qui. */
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int x;
    int z;

    sscanf( argv[1], "%d", &x );

    z = radice( x );

    printf( "radq(%d) = %d\n", x, z );
}

159.1.6 Fattoriale

Il problema del fattoriale stato descritto nella sezione 152.2.6.

/* ================================================================= */
/* fatt <x>							     */
/* Fattoriale.							     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* fatt ( <x> )							     */
/* ----------------------------------------------------------------- */
int fatt( int x ) {

    int i = ( x - 1 );

    while ( i > 0 ) {

        x = x * i;
        i--;
    }

    return x;
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int x;
    int z;

    sscanf( argv[1], "%d", &x );

    z = fatt( x );

    printf( "%d! = %d\n", x, z );
}

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

int fatt( int x ) {

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

159.1.7 Massimo comune divisore

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

/* ================================================================= */
/* mcd <x> <y>							     */
/* Massimo comune divisore.					     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* mcd ( <x>, <y> )						     */
/* ----------------------------------------------------------------- */
int mcd( int x, int y ) {

    while ( x != y ) {

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

    return x;
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int x;
    int y;
    int z;

    sscanf( argv[1], "%d", &x );
    sscanf( argv[2], "%d", &y );

    z = mcd( x, y );

    printf( "Il massimo comune divisore di %d e %d  %d\n", x, y, z );
}

159.1.8 Numero primo

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

/* ================================================================= */
/* primo <x>							     */
/* Numero primo.						     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* primo ( <x> )						     */
/* ----------------------------------------------------------------- */
unsigned int primo( int x ) {

    unsigned int primo = 1;
    int i = 2;
    int j;

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

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

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

    return primo;
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int x;

    sscanf( argv[1], "%d", &x );

    if ( primo( x ) ) {
	printf( "%d  un numero primo\n", x );
    } else {	
	printf( "%d non  un numero primo\n", x );
    }
}

159.2 Scansione di array

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

159.2.1 Ricerca sequenziale

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

/* ================================================================= */
/* ricercaseq <x> <v1>...					     */
/* Ricerca sequenziale.						     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* ricercaseq ( <lista>, <x>, <ele-inf>, <ele-sup> )		     */
/* ----------------------------------------------------------------- */
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.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int lista[argc-2];
    int x;
    int i;

    /* Acquisisce il primo argomento come valore da cercare.	     */
    sscanf( argv[1], "%d", &x );

    /* Considera gli argomenti successivi come gli elementi	     */
    /* dell'array da scandire.					     */
    for ( i = 2; i < argc; i++ ) {
	    sscanf( argv[i], "%d", &lista[i-2] );
    }

    /* Esegue la ricerca.					     */
    i = ricercaseq( lista, x, 0, argc-2);

    /* Emette il risultato.					     */
    printf( "%d si trova nella posizione %d\n", x, i );
}

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

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 );
    }
}

159.2.2 Ricerca binaria

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

/* ================================================================= */
/* ricercabin <x> <v1>...					     */
/* Ricerca binaria.						     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* ricercabin ( <lista>, <elemento>, <inizio>, <fine> )		     */
/* ----------------------------------------------------------------- */
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.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int lista[argc-2];
    int x;
    int i;

    /* Acquisisce il primo argomento come valore da cercare.	     */
    sscanf( argv[1], "%d", &x );

    /* Considera gli argomenti successivi come gli elementi	     */
    /* dell'array da scandire.					     */
    for ( i = 2; i < argc; i++ ) {
	    sscanf( argv[i], "%d", &lista[i-2] );
    }

    /* Esegue la ricerca.					     */
    i = ricercabin( lista, x, 0, argc-2);

    /* Emette il risultato.					     */
    printf( "%d si trova nella posizione %d\n", x, i );
}

159.3 Algoritmi tradizionali

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

159.3.1 Bubblesort

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

/* ================================================================= */
/* bsort <valore>...						     */
/* BubbleSort.							     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* bsort ( <lista>, <inizio>, <fine> )				     */
/* ----------------------------------------------------------------- */
void 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;
            }
        }
    }
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int lista[argc-1];
    int i;

    /* Considera gli argomenti come gli elementi		     */
    /* dell'array da ordinare.					     */
    for ( i = 1; i < argc; i++ ) {
	sscanf( argv[i], "%d", &lista[i-1] );
    }

    /* Esegue il riordino.					     */
    bsort( lista, 0, argc-2);

    /* Emette il risultato.					     */
    for ( i = 0; i < (argc-1); i++ ) {
	printf( "%d ", lista[i] );
    }
    printf( "\n" );
}

Segue la funzione `bsort' in versione ricorsiva.

void 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 );
    }
}

159.3.2 Torre di Hanoi

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

/* ================================================================= */
/* hanoi <n-anelli> <piolo-iniziale> <piolo-finale>		     */
/* Torre di Hanoi.						     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* hanoi ( <n-anelli>, <piolo-iniziale>, <piolo-finale> )	     */
/* ----------------------------------------------------------------- */
void hanoi( int n, int p1, int p2 ) {

    if (n > 0) {
	hanoi (n-1, p1, 6-p1-p2);
	printf( "Muovi l'anello %d dal piolo %d al piolo %d\n", n, p1, p2 );
	hanoi (n-1, 6-p1-p2, p2);
    }
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int n;
    int p1;
    int p2;

    sscanf( argv[1], "%d", &n );
    sscanf( argv[2], "%d", &p1 );
    sscanf( argv[3], "%d", &p2 );

    hanoi( n, p1, p2 );
}

159.3.3 Quicksort

L'algoritmo del Quicksort stato descritto nella sezione 152.4.3.

/* ================================================================= */
/* qsort <valore>...						     */
/* QuickSort.							     */
/* ================================================================= */

#include <stdio.h>

/* ================================================================= */
/* part ( <lista>, <inizio>, <fine> )				     */
/* ----------------------------------------------------------------- */
int part( int lista[], int a, int z ) {

    /* Viene preparata una variabile per lo scambio di valori.	     */
    int scambio = 0;

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

    /* Inizia il ciclo di scansione dell'array.			     */
    while (1) {
	while (1) {

	    /* Sposta i a destra.				     */
	    if ( (lista[i] > lista[a]) || ( i >= cf) ) {
		break;
	    } else {
		i += 1;
	    }
	}
	while (1) {
	    /* Sposta cf a sinistra.				     */
	    if (lista[cf] <= lista[a]) {
		break;
	    } else {
		cf -= 1;
	    }
	}
	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 += 1;
	    cf -= 1;
	}
    }

    /* 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;
}

/* ================================================================= */
/* quicksort ( <lista>, <inizio>, <fine> )			     */
/* ----------------------------------------------------------------- */
void quicksort( int lista[], int a, int z ) {

    /* Viene preparata la variabile cf.				     */
    int( cf ) = 0;

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

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int lista[argc-1];
    int i;

    /* Considera gli argomenti come gli elementi		     */
    /* dell'array da ordinare.					     */
    for ( i = 1; i < argc; i++ ) {
	sscanf( argv[i], "%d", &lista[i-1] );
    }

    /* Esegue il riordino.					     */
    quicksort( lista, 0, argc-2);

    /* Emette il risultato.					     */
    for ( i = 0; i < (argc-1); i++ ) {
	printf( "%d ", lista[i] );
    }
    printf( "\n" );
}

159.3.4 Permutazioni

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

/* ================================================================= */
/* permuta <valore>...						     */
/* Permutazioni.						     */
/* ================================================================= */

#include <stdio.h>

/* Variabile globale.						     */
int iDimArray;

/* ================================================================= */
/* visualizza ( <array>, <dimensione> )				     */
/* ----------------------------------------------------------------- */
void visualizza( int lista[], int dimensione ) {

    int i;

    for ( i = 0; i < dimensione; i++ ) {
	printf( "%d ", lista[i] );
    }
    printf( "\n" );
}

/* ================================================================= */
/* permuta ( <lista>, <inizio>, <fine> )			     */
/* ----------------------------------------------------------------- */
void permuta( int lista[], int a, int z ) {

    int scambio;
    int k;

    /* 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 l'array e utilizza una variabile dichiarata    */
	/* globalmente.						     */
	visualizza( lista, iDimArray );
    }
}

/* ================================================================= */
/* Inizio del programma.					     */
/* ----------------------------------------------------------------- */
main( int argc, char *argv[] ) {

    int lista[argc-1];
    int i;

    /* Considera gli argomenti come gli elementi		     */
    /* dell'array da permutare.					     */
    for ( i = 1; i < argc; i++ ) {
	sscanf( argv[i], "%d", &lista[i-1] );
    }

    /* Salva la dimensione dell'array nella variabile globale.	     */
    iDimArray = argc-1;

    /* Esegue le permutazioni.					     */
    permuta( lista, 0, argc-2);
}

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

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


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