[successivo] [precedente] [inizio] [fine] [indice generale] [violazione GPL] [translators] [docinfo] [indice analitico] [volume] [parte]
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.
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 282.
Il problema della somma tra due numeri positivi, attraverso l'incremento unitario, è stato descritto nella sezione 282.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. */
/* ----------------------------------------------------------------- */
int 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);
return 0;
}
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;
}
Il problema della moltiplicazione tra due numeri positivi, attraverso la somma, è stato descritto nella sezione 282.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. */
/* ----------------------------------------------------------------- */
int 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);
return 0;
}
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;
}
Il problema della divisione tra due numeri positivi, attraverso la sottrazione, è stato descritto nella sezione 282.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. */
/* ----------------------------------------------------------------- */
int 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);
return 0;
}
Il problema dell'elevamento a potenza tra due numeri positivi, attraverso la moltiplicazione, è stato descritto nella sezione 282.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. */
/* ----------------------------------------------------------------- */
int 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);
return 0;
}
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));
}
}
Il problema della radice quadrata è stato descritto nella sezione 282.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. */
/* ----------------------------------------------------------------- */
int main (int argc, char *argv[])
{
int x;
int z;
sscanf (argv[1], "%d", &x);
z = radice (x);
printf ("radq(%d) = %d\n", x, z);
return 0;
}
Il problema del fattoriale è stato descritto nella sezione 282.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. */
/* ----------------------------------------------------------------- */
int main (int argc, char *argv[])
{
int x;
int z;
sscanf (argv[1], "%d", &x);
z = fatt (x);
printf ("%d! = %d\n", x, z);
return 0;
}
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;
}
}
Il problema del massimo comune divisore, tra due numeri positivi, è stato descritto nella sezione 282.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. */
/* ----------------------------------------------------------------- */
int 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);
return 0;
}
Il problema della determinazione se un numero sia primo o meno, è stato descritto nella sezione 282.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. */
/* ----------------------------------------------------------------- */
int 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);
}
return 0;
}
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 282.
Il problema della ricerca sequenziale all'interno di un array, è stato descritto nella sezione 282.3.1.
/* ================================================================= */
/* ricercaseq <x> <v1>... */
/* Ricerca sequenziale. */
/* ================================================================= */
#include <stdio.h>
#include <stdlib.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. */
/* ----------------------------------------------------------------- */
int main (int argc, char *argv[])
{
/* int lista[argc-2]; */
int *lista = (int *) malloc ((argc - 2) * sizeof (int));
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);
return 0;
}
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);
}
}
Il problema della ricerca binaria all'interno di un array, è stato descritto nella sezione 282.3.2.
/* ================================================================= */
/* ricercabin <x> <v1>... */
/* Ricerca binaria. */
/* ================================================================= */
#include <stdio.h>
#include <stdlib.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. */
/* ----------------------------------------------------------------- */
int main (int argc, char *argv[])
{
/* int lista[argc-2]; */
int *lista = (int *) malloc ((argc - 2) * sizeof (int));
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);
return 0;
}
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 282.
Il problema del Bubblesort è stato descritto nella sezione 282.4.1. Viene mostrata prima una soluzione iterativa e successivamente la funzione bsort in versione ricorsiva.
/* ================================================================= */
/* bsort <valore>... */
/* BubbleSort. */
/* ================================================================= */
#include <stdio.h>
#include <stdlib.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. */
/* ----------------------------------------------------------------- */
int main (int argc, char *argv[])
{
/* int lista[argc-1]; */
int *lista = (int *) malloc ((argc - 1) * sizeof (int));
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");
return 0;
}
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);
}
}
Il problema della torre di Hanoi è stato descritto nella sezione 282.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. */
/* ----------------------------------------------------------------- */
int 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);
return 0;
}
L'algoritmo del Quicksort è stato descritto nella sezione 282.4.3.
/* ================================================================= */
/* qsort <valore>... */
/* QuickSort. */
/* ================================================================= */
#include <stdio.h>
#include <stdlib.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. */
/* ----------------------------------------------------------------- */
int main (int argc, char *argv[])
{
/* int lista[argc-1]; */
int *lista = (int *) malloc ((argc - 1) * sizeof (int));
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");
return 0;
}
L'algoritmo ricorsivo delle permutazioni è stato descritto nella sezione 282.4.4.
/* ================================================================= */
/* permuta <valore>... */
/* Permutazioni. */
/* ================================================================= */
#include <stdio.h>
#include <stdlib.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. */
/* ----------------------------------------------------------------- */
int main (int argc, char *argv[])
{
/* int lista[argc-1]; */
int *lista = (int *) malloc ((argc - 1) * sizeof (int));
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);
return 0;
}
Appunti di informatica libera 2003.01.01 --- Copyright © 2000-2003 Daniele Giacomini -- daniele @ swlibero.orgDovrebbe essere possibile fare riferimento a questa pagina anche con il nome c_esempi_di_programmazione.html
[successivo] [precedente] [inizio] [fine] [indice generale] [violazione GPL] [translators] [docinfo] [indice analitico]