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


Capitolo 565.   BC: esempi di programmazione

Questo capitolo raccoglie solo alcuni esempi di programmazione, in parte già descritti in altri capitoli. Per eseguire questi esempi basta usare il comando seguente, dove prova.b rappresenta il nome del file da eseguire:

bc prova.b[Invio]

Si vuole evitare l'uso di estensioni al linguaggio BC, per cui i programmi non vengono mostrati come script; inoltre manca la possibilità di controllare l'interazione con l'utilizzatore, quindi le funzioni devono essere richiamate manualmente e al termine si deve usare il comando quit, oppure si conclude il flusso dello standard input con la combinazione [Ctrl d].

Negli esempi non si fa uso delle librerie standard, pertanto i nomi relativi possono essere riutilizzati.

Le espressioni vengono scritte in modo da evitare la visualizzazione non desiderata. Per esempio, invece di i++, si preferisce usare la forma i=(i+1), quando possibile.

Bisogna ricordare che se non si assegna il risultato generato da una funzione, questo viene visualizzato. La variabile t è stata usata negli esempi per raccogliere questo risultato quando non desiderato.

565.1   Problemi elementari di programmazione

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

565.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.b>.

/*
    somma.b
    Somma esclusivamente valori positivi.
*/

define s (x, y) {
    auto z, i
    z=x
    for (i=1; i<=y; i++) {
        z=(z+1)
    }
    return (z)
}

"Per calcolare la somma, si utilizzi la funzione s (x, y): "

In alternativa si può tradurre il ciclo for in un ciclo while:

define s (x, y) {
    auto z, i
    z=x
    i=1
    while (i<=y) {
        z=(z+1)
        i=(i+1)
    }
    return (z)
}

565.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.b>.

/*
    moltiplica.b
*/

define m (x, y) {
    auto z, i
    z=0
    for (i=1; i<=y; i++) {
        z=(z+x)
    }
    return (z)
}

"Per calcolare la moltiplicazione, si utilizzi la funzione m (x, y): "

In alternativa si può tradurre il ciclo for in un ciclo while:

define m (x, y) {
    auto z, i
    z=0
    i=1
    while (i<=y) {
        z=(z+x)
        i=(i+1)
    }
    return (z)
}

565.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.b>.

/*
    dividi.b
    Divide esclusivamente valori positivi.
*/

define d (x, y) {
    auto z, i
    z=0
    i=x
    while (i>=y) {
        i=(i-y)
        z=(z+1)
    }
    return (z)
}

"Per calcolare la divisione intera, si utilizzi la funzione d (x, y): "

565.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.b>.

/*
    exp.b
*/

define x (x, y) {
    auto z, i
    z=1
    for (i=1; i<=y; i++) {
        z=(z*x)
    }
    return (z)
}

"Per calcolare l'elevamento a potenza, si utilizzi la funzione x (x, y): "

In alternativa si può tradurre il ciclo for in un ciclo while:

define x (x, y) {
    auto z, i
    z=1
    i=1
    while (i<=y) {
        z=(z*x)
        i=(i+1)
    }
    return (z)
}

È possibile usare anche un algoritmo ricorsivo:

define x (x, y) {
    if (x==0) {
        return (0)
    }
    if (y==0) {
        return (1)
    }
    return (x * x (x, y-1))
}

565.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.b>.

/*
    radice.b
*/

define r (x) {
    auto z, y
    z=0
    y=0
    while (1) {
        y=(z*z)
        if (y>x) {
            /* È stato superato il valore massimo. */
            z=(z-1)
            return (z)
        }
        z=(z+1)
    }
}

"Per calcolare la radice quadrata, si utilizzi la funzione r (x): "

565.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.b>.

/*
    fatt.b
*/

define f (x) {
    auto i
    i=(x-1)
    while (i>0) {
        x=(x*i)
        i=(i-1)
    }
    return (x)
}

"Per calcolare il fattoriale, si utilizzi la funzione f (x): "

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

define f (x) {
    if (x>1) {
        return (x * f (x-1))
    }
    return (1)
}

565.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.b>.

/*
    mcd.b
*/

define m (x, y) {
    auto n
    while (x!=y) {
        n=0
        if (x>y) {
            x=x-y
            n=1
        }
        if (n==0) {
            y=(y-x)
        }
    }
    return (x)
}

"Per calcolare il massimo comune divisore, "
"si utilizzi la funzione m (x, y): "

565.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.b>.

/*
    primo.b
*/

define p(x) {
    auto i, j
    i=2
    while (i<x) {
        scale=0
        j=(x/i)
        j=x-(j*i)
        if (j==0) {
            return (0)
        }
        i=(i+1)
    }
    return (1)
}

"Per verificare se un numero sia primo, si utilizzi la funzione p (x, y); "
"1 indica un numero primo, 0 indica un numero che non è primo. "

565.2   Scansione di array

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

Per usare questi programmi, mancando un sistema normale di interazione con l'utilizzatore, è necessario creare un array prima di utilizzare la funzione che svolge il lavoro di ricerca o di riordino. Per esempio, nel caso della funzione r() per la ricerca sequenziale:

bc ricercaseq.b[Invio]

Ricerca sequenziale: r (<lista>, , <elemento>, <inizio>, <fine>)

a[0]=3[Invio]

a[1]=10[Invio]

a[2]=33[Invio]

a[3]=56[Invio]

r (a[], 33, 0, 3)[Invio]

2

[Ctrl d]

565.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.b>.

/*
    ricercaseq.b
*/

/* r (<lista>, <elemento>, <inizio>, <fine>) */
define r (l[], x, a, z) {
    auto i
    for (i=a; i<=z; i++) {
        if (x==l[i]) {
            return (i)
        }
    }
    /* La corrispondenza non è stata trovata. */
    return (-1)
}

"Ricerca sequenziale: r (<lista>, , <elemento>, <inizio>, <fine>) "

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

define r (l[], x, a, z) {
    if (a>z) {
        return (-1)
    }
    if (x==l[a]) {
        return (a)
    }
    return (r (l[], x, a+1, z))
}

565.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.b>.

/*
    ricercabin.b
*/

/* r (<lista>, <elemento>, <inizio>, <fine>) */
define r (l[], x, a, z) {
    auto m
    /* Determina l'elemento centrale. */
    scale=0
    m = ((a+z)/2)
    if (m<a) {
        /* Non restano elementi da controllare: l'elemento cercato non c'è. */
        return (-1)
    }
    if (x<l[m]) {
        /* Si ripete la ricerca nella parte inferiore. */
        return (r (l[], x, a, m-1))
    }
    if (x>l[m]) {
        /* Si ripete la ricerca nella parte superiore. */
        return (r (l[], x, m+1, z))
    }
    /* $m rappresenta l'indice dell'elemento cercato. */
    return (m)
}

"Ricerca binaria: r (<lista>, <elemento>, <inizio>, <fine>) "

565.3   Algoritmi tradizionali

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

Per consentire la visualizzazione del contenuto di un array è necessario predisporre una funzione apposita, che viene presentata qui, senza ripeterla nei vari esempi proposti (per evitare di visualizzare uno zero aggiuntivo, conviene assegnare il valore restituito dalla funzione stessa).

/* v (<lista>, <inizio>, <fine>) */
define v (l[], a, z) {
    auto j
    for (j=a; j<=z; j++) {
        (l[j])
    }
    return
}

565.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.b>.

/*
    bsort.b
*/

/* l[] è l'array da riordinare. */

/* b (<inizio>, <fine>) */
define b (a, z) {
    auto s, j, 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 (l[k]<l[j]) {
                /* Scambia i valori */
                s=l[k]
                l[k]=l[j]
                l[j]=s
            }
        }
    }
    return
}

"Bubblesort: l[]; t = b (<inizio>, <fine>)   "
"L'array da riordinare è l[]. "

Segue la funzione bsort() in versione ricorsiva:

define b (a, z) {
    auto s, k
    if (a<z) {
        /*
            Scansione interna dell'array per collocare nella posizione a
            l'elemento giusto.
        */
        for (k=(a+1); k<=z; k++) {
            if (l[k]<l[a]) {
                /* Scambia i valori */
                s=l[k]
                l[k]=l[a]
                l[a]=s
            }
        }
        b (a+1, z)
    }
    return
}

565.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.b>.

/*
    hanoi.b
*/

/* h (<n-anelli>, <piolo-iniziale>, <piolo-finale>) */
define h (n, i, f) {
    auto t
    if (n>0) {
        t = h (n-1, i, 6-i-f)
        "Muovi l'anello " ; n
        "dal piolo " ; i
        "al piolo " ; f
        t = h (n-1, 6-i-f, f);
    }
    return
}

"Torre di Hanoi: t = h (<n-anelli>, <piolo-iniziale>, <piolo-finale>) "

565.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.b>.

/*
    qsort.b
*/

/* l[] è l'array da riordinare. */

/* p (<inizio>, <fine>) */
define p (a, z) {
    auto s, i, c
    /* Si assume che a sia inferiore a z. */
    i=(a+1)
    c=z

    /* Inizia il ciclo di scansione dell'array. */
    while (1) {
        while (1) {
            /* Sposta i a destra. */
            if (l[i]>l[a]) {
                break
            }
            if (i>=c) {
              break
            }
            i=(i+1)
        }        
        while (1) {
            /* Sposta c a sinistra. */
            if (l[c]<=l[a]) {
                break
            }
            c=(c-1)
        }
        if (c<=i) {
            /* È avvenuto l'incontro tra i e c. */
            break
        }
        /* Vengono scambiati i valori. */
        s=l[c]
        l[c]=l[i]
        l[i]=s

        i=(i+1)
        c=(c-1)
    }

    /*
        A questo punto l[a..z] è stata ripartita e c è la collocazione
        di l[a].
    */
    s=l[c]
    l[c]=l[a]
    l[a]=s

    /*
        A questo punto l[c] è un elemento (un valore) nella
        posizione giusta.
    */
    return (c)
}

/* q (<inizio>, <fine>) */
define q (a, z) {
    auto c
    if (z>a) {
        c = p (a, z)
        q (a, c-1)
        q (c+1, z)
    }
    return
}

"Quicksort: l[]  t = q (<inizio>, <fine>)  "
"Prima riempire l'array l[], poi chiamare la funzione q()."

565.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.b>.

/*
    permuta.b
*/

/* v (<lista>, <inizio>, <fine>) */
define v (l[], a, z) {
    auto j
    for (j=a; j<=z; j++) {
        (l[j])
    }
    return
}

/* p (<lista>, <inizio>, <fine>, <max_array>) */
define p (l[], a, z, d) {
    auto k
    auto t
    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 */
            s=l[k]
            l[k]=l[z]
            l[z]=s

            /*
                Esegue una chiamata ricorsiva per permutare un segmento
                più piccolo dell'array.
            */

            t = p (l[], a, z-1, d)

            /* Scambia i valori */
            s=l[k]
            l[k]=l[z]
            l[z]=s
        }
        return
    }
    /* Visualizza la situazione attuale dell'array. */
    " "
    t = v (l[],0,d)
    return
}

"Permutazioni: t = p (<lista>, <inizio>, <fine>, <max_array>)"

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 bc_esempi_di_programmazione.htm

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

Valid ISO-HTML!

CSS validator!