[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home] [volume] [parte]


Capitolo 588.   Algoritmi tradizionali

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

588.1   Bubblesort

Il problema del Bubblesort è stato descritto nella sezione 543.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.c>.

#include <stdio.h>

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

int
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");

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

Al posto di dichiarare l'array lista con una quantità di elementi definita in fase di funzionamento, si può usare la funzione malloc(), avendo cura di incorporare il file stdlib.h:

#include <stdio.h>
#include <stdlib.h>
...
int
main (int argc, char *argv[])
{
    int *lista = (int *) malloc ((argc - 1) * sizeof (int));
...

588.2   Torre di Hanoi

Il problema della torre di Hanoi è descritto nella sezione 543.4.3.

Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/hanoi.c>.

#include <stdio.h>

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

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

588.3   Quicksort

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

Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/qsort.c>.

#include <stdio.h>

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

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

int
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");

    return 0;
}

Per questo esempio vale la stessa considerazione già fatta a proposito dell'uso di malloc() al posto di un array con una quantità di elementi definita dinamicamente durante il funzionamento del programma.

588.4   Permutazioni

L'algoritmo ricorsivo delle permutazioni è descritto nella sezione 543.4.5.

Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/permuta.c>.

#include <stdio.h>

void visualizza (int lista[], int dimensione)
{
    int i;

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

void permuta (int lista[], int a, int z, int dimensione)
{
    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, dimensione);

            // Scambia i valori.

            scambio = lista[k];
            lista[k] = lista[z];
            lista[z] = scambio;
          }
      }
    else
      {
        // Visualizza l'array.

        visualizza (lista, dimensione);
      }
}

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

    // Esegue le permutazioni.

    permuta (lista, 0, argc - 2, argc - 1);

    return 0;
}

Per questo esempio vale la stessa considerazione già fatta a proposito dell'uso di malloc() al posto di un array con una quantità di elementi definita dinamicamente durante il funzionamento del programma.


Appunti di informatica libera 2008 --- Copyright © 2000-2008 Daniele Giacomini -- <appunti2 (ad) gmail·com>


Dovrebbe essere possibile fare riferimento a questa pagina anche con il nome algoritmi_tradizionali.htm

[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home]

Valid ISO-HTML!

CSS validator!

Gjlg Metamotore e Web Directory