[successivo]
[precedente]
[inizio]
[fine]
[indice generale]
[indice ridotto]
[indice analitico]
[volume]
[parte]
Capitolo 549. Perl: 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.
549.1
Problemi elementari di programmazione
In questa sezione vengono mostrati alcuni algoritmi elementari portati in Perl. Per la spiegazione degli algoritmi, se non sono già conosciuti, occorre leggere quanto riportato nel capitolo 531.
549.1.1
Somma tra due numeri positivi
Il problema della somma tra due numeri positivi, attraverso l'incremento unitario, è descritto nella sezione 531.2.1.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/somma.pl>.
#!/usr/bin/perl
##
## somma.pl <x> <y>
## Somma esclusivamente valori positivi.
##
#
# &somma (<x>, <y>)
#
sub somma
{
local ($x) = $_[0];
local ($y) = $_[1];
#
local ($z) = $x;
local ($i);
#
for ($i = 1; $i <= $y; $i++)
{
$z++;
}
#
return $z;
}
#
# Inizio del programma.
#
$x = $ARGV[0];
$y = $ARGV[1];
#
$z = &somma ($x, $y);
#
print "$x + $y = $z\n";
#
|
|
In alternativa si può tradurre il ciclo for in un ciclo while:
sub somma
{
local ($x) = $_[0];
local ($y) = $_[1];
#
local ($z) = $x;
local ($i) = 1;
#
while ($i <= $y)
{
$z++;
$i++;
}
#
return $z;
}
|
|
549.1.2
Moltiplicazione di due numeri positivi attraverso la somma
Il problema della moltiplicazione tra due numeri positivi, attraverso la somma, è descritto nella sezione 531.2.2.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/moltiplica.pl>.
#!/usr/bin/perl
##
## moltiplica.pl <x> <y>
##
#
# &moltiplica (<x>, <y>)
#
sub moltiplica
{
local ($x) = $_[0];
local ($y) = $_[1];
#
local ($z) = 0;
local ($i);
#
for ($i = 1; $i <= $y; $i++)
{
$z = $z + $x;
}
#
return $z;
}
##
## Inizio del programma.
##
$x = $ARGV[0];
$y = $ARGV[1];
#
$z = &moltiplica ($x, $y);
#
print "$x * $y = $z\n";
#
|
|
In alternativa si può tradurre il ciclo for in un ciclo while:
sub moltiplica {
local ($x) = $_[0];
local ($y) = $_[1];
#
local ($z) = 0;
local ($i) = 1;
#
while ($i <= $y)
{
$z = $z + $x;
$i++;
}
#
return $z;
}
|
|
549.1.3
Divisione intera tra due numeri positivi
Il problema della divisione tra due numeri positivi, attraverso la sottrazione, è descritto nella sezione 531.2.3.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/dividi.pl>.
#!/usr/bin/perl
##
## dividi.pl <x> <y>
## Divide esclusivamente valori positivi.
##
#
# &dividi (<x>, <y>)
#
sub dividi
{
local ($x) = $_[0];
local ($y) = $_[1];
#
local ($z) = 0;
local ($i) = $x;
#
while ($i >= $y)
{
$i = $i - $y;
$z++;
}
#
return $z;
}
##
## Inizio del programma.
##
$x = $ARGV[0];
$y = $ARGV[1];
#
$z = &dividi ($x, $y);
#
print "Divisione intera - $x:$y = $z\n";
#
|
|
549.1.4
Elevamento a potenza
Il problema dell'elevamento a potenza tra due numeri positivi, attraverso la moltiplicazione, è descritto nella sezione 531.2.4.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/exp.pl>.
#!/usr/bin/perl
##
## exp.pl <x> <y>
## Eleva a potenza.
##
#
# &exp (<x>, <y>)
#
sub exp
{
local ($x) = $_[0];
local ($y) = $_[1];
#
local ($z) = 1;
local ($i);
#
for ($i = 1; $i <= $y; $i++)
{
$z = $z * $x;
}
#
return $z;
}
##
## Inizio del programma.
##
$x = $ARGV[0];
$y = $ARGV[1];
#
$z = &exp ($x, $y);
#
print "$x ** $y = $z\n";
#
|
|
In alternativa si può tradurre il ciclo for in un ciclo while:
sub exp
{
local ($x) = $_[0];
local ($y) = $_[1];
#
local ($z) = 1;
local ($i) = 1;
#
while ($i <= $y)
{
$z = $z * $x;
$i++;
}
#
return $z;
}
|
|
È possibile usare anche un algoritmo ricorsivo:
sub exp
{
local ($x) = $_[0];
local ($y) = $_[1];
#
if ($x == 0)
{
return 0;
}
elsif ($y == 0)
{
return 1;
}
else
{
return ($x * &exp ($x, $y-1));
}
}
|
|
549.1.5
Radice quadrata
Il problema della radice quadrata è descritto nella sezione 531.2.5.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/radice.pl>.
#!/usr/bin/perl
##
## radice.pl <x>
## Radice quadrata.
##
#
# &radice (<x>)
#
sub radice
{
local ($x) = $_[0];
#
local ($z) = 0;
local ($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.
##
$x = $ARGV[0];
#
$z = &radice ($x);
#
print "radq ($x) = $z\n";
#
|
|
549.1.6
Fattoriale
Il problema del fattoriale è descritto nella sezione 531.2.6.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/fatt.pl>.
#!/usr/bin/perl
##
## fatt.pl <x>
##
#
# &fatt (<x>)
#
sub fatt
{
local ($x) = $_[0];
#
local ($i) = ($x - 1);
#
while ($i > 0)
{
$x = $x * $i;
$i--;
}
#
return $x;
}
##
## Inizio del programma.
##
$x = $ARGV[0];
#
$fatt = &fatt ($x);
#
print "$x! = $fatt\n";
#
|
|
In alternativa, l'algoritmo si può tradurre in modo ricorsivo:
sub fatt {
local ($x) = $_[0];
#
if ($x > 1)
{
return ($x * &fatt ($x - 1));
}
else
{
return 1;
}
}
|
|
549.1.7
Massimo comune divisore
Il problema del massimo comune divisore, tra due numeri positivi, è descritto nella sezione 531.2.7.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/mcd.pl>.
#!/usr/bin/perl
##
## mcd.pl <x> <y>
##
#
# &mcd (<x>, <y>)
#
sub mcd
{
local ($x) = $_[0];
local ($y) = $_[1];
#
while ($x != $y)
{
if ($x > $y)
{
$x = $x - $y;
}
else
{
$y = $y - $x;
}
}
#
return $x;
}
##
## Inizio del programma.
##
$x = $ARGV[0];
$y = $ARGV[1];
#
$z = &mcd ($x, $y);
#
print "Il massimo comune divisore di $x e $y è $z\n";
#
|
|
549.1.8
Numero primo
Il problema della determinazione se un numero sia primo o meno, è descritto nella sezione 531.2.8.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/primo.pl>.
#!/usr/bin/perl
##
## primo.pl <x>
##
#
# &primo (<x>)
#
sub primo
{
local ($x) = $_[0];
#
local ($primo) = 1;
local ($i) = 2;
local ($j);
#
while (($i < $x) && $primo)
{
$j = int ($x / $i);
$j = $x - ($j * $i);
#
if ($j == 0)
{
$primo = 0;
}
else
{
$i++;
}
}
#
return $primo;
}
##
## Inizio del programma.
##
$x = $ARGV[0];
#
if (&primo ($x))
{
print "$x è un numero primo\n";
}
else
{
print "$x non è un numero primo\n";
}
#
|
|
549.2
Scansione di array
In questa sezione vengono mostrati alcuni algoritmi, legati alla scansione degli array, portati in Perl. Per la spiegazione degli algoritmi, se non sono già conosciuti, occorre leggere quanto riportato nel capitolo 531.
549.2.1
Ricerca sequenziale
Il problema della ricerca sequenziale all'interno di un array, è descritto nella sezione 531.3.1.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/ricercaseq.pl>.
#!/usr/bin/perl
##
## ricercaseq.pl <elemento-cercato> <valore>...
##
#
# &ricercaseq (<lista>, <elemento>, <inizio>, <fine>)
#
sub ricercaseq
{
#
# Il primo argomento è un riferimento all'array, per cui
# lo scalare $lista diventa il nuovo riferimento locale
# all'array.
# Per leggerlo come array occorre la forma @$lista, mentre
# per leggerne un elemento occorre la forma ${$lista}[n].
#
local ($lista) = $_[0];
local ($x) = $_[1];
local ($a) = $_[2];
local ($z) = $_[3];
#
local ($i);
#
for ($i = $a; $i <= $z; $i++)
{
if ($x == ${$lista}[$i])
{
return $i;
}
}
#
# La corrispondenza non è stata trovata.
#
return -1;
}
##
## Inizio del programma.
##
$x = $ARGV[0];
@lista = @ARGV[1 .. $#ARGV];
#
$i = &ricercaseq (\@lista, $x, 0, $#lista);
#
print "L'elemento $x si trova nella posizione $i\n";
#
|
|
Esiste anche una soluzione ricorsiva che viene mostrata nella subroutine seguente:
sub ricercaseq {
local ($lista) = $_[0];
local ($x) = $_[1];
local ($a) = $_[2];
local ($z) = $_[3];
#
if ($a > $z)
{
return -1;
}
elsif ($x == ${$lista}[$a])
{
return $a;
}
else
{
return &ricercaseq ($lista, $x, $a+1, $z);
}
}
|
|
549.2.2
Ricerca binaria
Il problema della ricerca binaria all'interno di un array, è descritto nella sezione 531.3.2.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/ricercabin.pl>.
#!/usr/bin/perl
##
## ricercabin.pl <elemento-cercato> <valore>...
##
#
# &ricercabin (<lista>, <elemento>, <inizio>, <fine>)
#
sub ricercabin
{
#
# Il primo argomento è un riferimento all'array, per cui
# lo scalare $lista diventa il nuovo riferimento locale
# all'array.
# Per leggerlo come array occorre la forma @$lista, mentre
# per leggerne un elemento occorre la forma ${$lista}[n].
#
local ($lista) = $_[0];
local ($x) = $_[1];
local ($a) = $_[2];
local ($z) = $_[3];
#
local ($m);
#
# Determina l'elemento centrale.
#
$m = int (($a + $z) / 2);
#
if ($m < $a)
{
#
# Non restano elementi da controllare: l'elemento cercato non c'è.
#
return -1;
}
elsif ($x < ${$lista}[$m])
{
#
# Si ripete la ricerca nella parte inferiore.
#
return &ricercabin ($lista, $x, $a, $m-1);
}
elsif ($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.
##
$x = $ARGV[0];
@lista = @ARGV[1 .. $#ARGV];
#
$i = &ricercabin (\@lista, $x, 0, $#lista);
#
print "L'elemento $x si trova nella posizione $i\n";
#
|
|
549.3
Algoritmi tradizionali
In questa sezione vengono mostrati alcuni algoritmi tradizionali portati in Perl. Per la spiegazione degli algoritmi, se non sono già conosciuti, occorre leggere quanto riportato nel capitolo 531.
549.3.1
Bubblesort
Il problema del Bubblesort è stato descritto nella sezione 531.4.1. Viene mostrata prima una soluzione iterativa e successivamente la funzione bsort in versione ricorsiva.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/bsort.pl>.
#!/usr/bin/perl
##
## bsort.pl <valore>...
##
#
# &bsort (<lista>, <inizio>, <fine>)
#
sub bsort
{
#
# Il primo argomento è un riferimento all'array, per cui
# lo scalare $lista diventa il nuovo riferimento locale
# all'array.
# Per leggerlo come array occorre la forma @$lista, mentre
# per leggerne un elemento occorre la forma ${$lista}[n].
#
local ($lista) = $_[0];
local ($a) = $_[1];
local ($z) = $_[2];
#
local ($scambio);
#
local ($j);
local ($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.
##
@lista = @ARGV;
#
&bsort (\@lista, 0, $#lista);
#
print "@lista\n";
#
|
|
Segue la funzione bsort in versione ricorsiva:
sub bsort
{
local ($lista) = $_[0];
local ($a) = $_[1];
local ($z) = $_[2];
#
local ($k);
local ($scambio);
#
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);
}
}
|
|
549.3.2
Torre di Hanoi
Il problema della torre di Hanoi è descritto nella sezione 531.4.3.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/hanoi.pl>.
#!/usr/bin/perl
##
## hanoi.pl <n-anelli> <piolo-iniziale> <piolo-finale>
##
#
# &hanoi (<n-anelli>, <piolo-iniziale>, <piolo-finale>)
#
sub hanoi {
local ($n) = $_[0];
local ($p1) = $_[1];
local ($p2) = $_[2];
#
if ($n > 0)
{
&hanoi ($n-1, $p1, 6-$p1-$p2);
print "Muovi l'anello $n dal piolo $p1 al piolo $p2\n";
&hanoi ($n-1, 6-$p1-$p2, $p2);
}
}
##
## Inizio del programma.
##
$n = $ARGV[0];
$p1 = $ARGV[1];
$p2 = $ARGV[2];
#
&hanoi ($n, $p1, $p2);
#
|
|
549.3.3
Quicksort
L'algoritmo del Quicksort è stato descritto nella sezione 531.4.4.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/qsort.pl>.
#!/usr/bin/perl
##
## qsort.pl <valore>...
##
#
# &part (<lista>, <inizio>, <fine>)
#
sub part
{
#
# Il primo argomento è un riferimento all'array, per cui
# lo scalare $lista diventa il nuovo riferimento locale
# all'array.
# Per leggerlo come array occorre la forma @$lista, mentre
# per leggerne un elemento occorre la forma ${$lista}[n].
#
local ($lista) = $_[0];
local ($a) = $_[1];
local ($z) = $_[2];
#
# Viene preparata una variabile che serve per scambiare due valori.
#
local ($scambio) = 0;
#
# Si assume che $a sia inferiore a $z.
#
local ($i) = $a + 1;
local ($cf) = $z;
#
# Inizia il ciclo di scansione dell'array.
#
while (1)
{
while (1)
{
#
# Sposta $i a destra.
#
if ((${$lista}[$i] > ${$lista}[$a]) || ($i >= $cf))
{
last;
}
else
{
$i += 1;
}
}
while (1)
{
#
# Sposta $cf a sinistra.
#
if (${$lista}[$cf] <= ${$lista}[$a])
{
last;
}
else
{
$cf -= 1;
}
}
if ($cf <= $i)
{
#
# È avvenuto l'incontro tra $i e $cf.
#
last;
}
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>)
#
sub quicksort
{
#
# Il primo argomento è un riferimento all'array, per cui
# lo scalare $lista diventa il nuovo riferimento locale
# all'array.
#
local ($lista) = $_[0];
local ($a) = $_[1];
local ($z) = $_[2];
#
# Viene preparata la variabile $cf.
#
local ($cf) = 0;
#
if ($z > $a)
{
$cf = &part ($lista, $a, $z);
&quicksort ($lista, $a, $cf-1);
&quicksort ($lista, $cf+1, $z);
}
}
##
## Inizio del programma.
##
@lista = @ARGV;
#
quicksort (\@lista, 0, $#lista);
#
print "@lista\n";
#
|
|
549.3.4
Permutazioni
L'algoritmo ricorsivo delle permutazioni è descritto nella sezione 531.4.5.
Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/permuta.pl>.
#!/usr/bin/perl
##
## permuta.pl <valore>...
##
#
# &permuta (<lista>, <inizio>, <fine>)
#
sub permuta
{
#
# Il primo argomento è un riferimento all'array, per cui
# lo scalare $lista diventa il nuovo riferimento locale
# all'array.
# Per leggerlo come array occorre la forma @$lista, mentre
# per leggerne un elemento occorre la forma ${$lista}[n].
#
local ($lista) = $_[0];
local ($a) = $_[1];
local ($z) = $_[2];
#
local ($scambio);
#
local ($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 la situazione attuale dell'array.
#
print "@$lista\n";
}
}
##
## Inizio del programma.
##
@lista = @ARGV;
#
&permuta (\@lista, 0, $#lista);
#
|
|
Appunti di informatica libera 2007.02 --- Copyright © 2000-2007 Daniele Giacomini -- <daniele (ad) swlibero·org>
Dovrebbe essere possibile fare riferimento a questa pagina anche con il nome perl_esempi_di_programmazione.htm
[successivo]
[precedente]
[inizio]
[fine]
[indice generale]
[indice ridotto]
[indice analitico]
