Capitolo 8. 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.

8.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 1.

8.1.1 Somma tra due numeri positivi

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

#!/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;
}

8.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 1.2.2.

#!/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;
}

8.1.3 Divisione intera tra due numeri positivi

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

#!/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";
#======================================================================

8.1.4 Elevamento a potenza

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

#!/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));
      }
}

8.1.5 Radice quadrata

Il problema della radice quadrata è stato descritto nella sezione 1.2.5.

#!/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";
#======================================================================

8.1.6 Fattoriale

Il problema del fattoriale è stato descritto nella sezione 1.2.6.

#!/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;
      }
}

8.1.7 Massimo comune divisore

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

#!/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";
#======================================================================

8.1.8 Numero primo

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

#!/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";
  }
#======================================================================

8.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 1.

8.2.1 Ricerca sequenziale

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

#!/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 occorrerà la forma @$lista, mentre
    # per leggerne un elemento occorrerà 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);
      }
}

8.2.2 Ricerca binaria

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

#!/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 occorrerà la forma @$lista, mentre
    # per leggerne un elemento occorrerà 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";
#======================================================================

8.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 1.

8.3.1 Bubblesort

Il problema del Bubblesort è stato descritto nella sezione 1.4.1. Viene mostrato prima una soluzione iterativa e successivamente la funzione bsort in versione ricorsiva.

#!/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 occorrerà la forma @$lista, mentre
    # per leggerne un elemento occorrerà 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 ($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);
      }
}

8.3.2 Torre di Hanoi

Il problema della torre di Hanoi è stato descritto nella sezione 1.4.2.

#!/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);

#======================================================================

8.3.3 Quicksort

L'algoritmo del Quicksort è stato descritto nella sezione 1.4.3.

#!/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 occorrerà la forma @$lista, mentre
    # per leggerne un elemento occorrerà la forma ${$lista}[n].
    #------------------------------------------------------------------
    local ($lista) = $_[0];
    local ($a) = $_[1];
    local ($z) = $_[2];

    #------------------------------------------------------------------
    # Viene preparata una variabile che servirà per scambiare due
    # valori.
    #------------------------------------------------------------------
    local ($scambio) = 0;

    #------------------------------------------------------------------
    # Si assume che $a sia inferiore a $u.
    #------------------------------------------------------------------
    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";

#======================================================================

8.3.4 Permutazioni

L'algoritmo ricorsivo delle permutazioni è stato descritto nella sezione 1.4.4.

#!/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 occorrerà la forma @$lista, mentre
    # per leggerne un elemento occorrerà 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);
#======================================================================