PROGRAMMIAMO
Algoritmi - Esempi

Vediamo ora alcuni semplici esempi di algoritmi:

a) Scambio di liquido fra due bicchieri

Supponiamo di avere due bicchieri, denominati A e B, pieni rispettivamente uno di acqua e l'altro di vino, e di voler travasare A in B e viceversa.

Il problema può essere risolto usando un terzo bicchiere C e l'algoritmo è il seguente:

1) versa A in C
2) versa B in A
3) versa C in B

b) Scambio di nomi all'interno di un file

Un problema molto simile al precedente si presenta usando un programma di video scrittura (come Word) quando si vogliono scambiare fra loro due nomi o parole contenute nel file.

Per esempio, supponiamo di avere un file contenente un testo (per esempio un racconto) e di volerlo correggere nel seguente modo: tutte le volte che nel file compare la parola Filippo la si vuole sostituire con la parola Giovanni e viceversa.

Se il file molto lungo, per evitare di fare manualmente tutte le sostituzioni, possiamo utilizzare la funzione Trova e Sostituisce presente in tutti i programmi di video scrittura. Qui tuttavia sorge un problema: se sostituiamo prima tutte le occorrenze di Filippo con Giovanni, poi ci ritroviamo con un file contenente solo il nome Giovanni e la sostituzione inversa non possibile. La stessa cosa, ovviamente, succederebbe, se sostituissimo prima tutte le occorrenze di Giovanni con Filippo.

La strategia di soluzione simile a quella dell'esempio dei due bicchieri. Dobbiamo usare una terza parola temporanea, scegliendo qualcosa che non compare gi nel nostro file (ad esempio una stringa a caso: xyzw123). Procediamo dunque nel seguente modo:

1) sostituiamo tutte le occorrenze nel file di Filippo con xyzw123
2) sostituiamo tutte le occorrenze di Giovanni con Filippo
3) sostituiamo tutte le occorrenze di xyzw123 con Giovanni

c) Problema del lupo, del cavolo e della capra

Un pastore deve attraversare un fiume portando sull'altra riva un lupo e una capra affamati e una cassa di cavoli. Ha a disposizione una barca a remi con la quale può traghettare un solo oggetto o animale alla volta. Ma, attenzione! Non può lasciare da soli:- il lupo e la capra perchè il lupo si mangia la capra;- la capra ed i cavoli perché la capra si mangia i cavoli.

Chiamiamo A la sponda iniziale e B la sponda su cui il barcaiolo deve trasportare lupo, capra e cavoli.

1) il barcaiolo porta la capra in B
2) il barcaiolo torna a prendere il lupo e lo porta in B
3) il barcaiolo riporta la capra in A
4) il barcaiolo porta i cavoli in B
5) il barcaiolo porta la capra in B

d) Ricavare una misura intermedia con due contenitori

Si supponga di avere due contenitori per liquidi: un contenitore A da 3 litri e un contenitore B da 5 litri. Si vuole ottenere una misura di 4 litri esatti.

L'algoritmo è il seguente:

1) Riempi B
2) Versa B in A fino a riempire A
3) Vuota A
4) Versa B in A
5) Riempi B
6) Versa B in A fino a riempire A
7) In B restano esattamente 4 litri

e) Differenza fra due orari

Si supponga di conoscere l'orario di inizio e l'orario di fine di un film e di volerne calcolare la durata in minuti.

Per fissare le idee supponiamo che l'orario di inizio sia le 20.30 e l'orario di fine sia le 22.14. Chiamiamo ora1 l'ora di inizio (20) e min1 i minuti di inizio (30). Allo stesso modo ora2 sarà l'ora finale (22) e min2 i minuti finali (14).

L'algoritmo potrebbe essere il seguente:

1) Calcolo tot1 = ora1 + min1 x 60
2) Calcolo tot2 = ora2 + min2 x 60
3) Faccio la differenza dif = tot2 - tot1

f) Ordinamento di 3 numeri

Siano dati tre valori A, B e C e li si vuole ordinare in modo crescente, cioè in modo che A contenga il valore più piccolo di tutti, B quello intermedio e C il più grande. L'algoritmo deve naturalmente funzionare con qualsiasi scelta di valori di A, B e C. Ecco una soluzione possibile:

1) SE B < A, ALLORA scambia B con A
2) SE C < A, ALLORA scambia C con A
3) SE B < A, ALLORA scambia B con A

Si noti che l'istruzione 1 e la 3 sono uguali. Tuttavia vengono eseguite con valori diversi e dunque, in generale, producono risultati diversi. L'istruzione "scambia" può essere ulteriormente dettagliata specificando tutti i passaggi intermedi necessari ad effettuare lo scambio fra il contenuto di due variabili.

g) Anni bisestili

Un anno è bisestile se il suo numero è divisibile per 4, con l'eccezione che gli anni secolari (quelli divisibili per 100) che sono bisestili solo se divisibili per 400. Sono cioè bisestili tutti gli anni la cui numerazione termina con le due cifre 04, 08, 12... fino a 96; gli anni che terminano con 00 sono bisestili solo se l'anno è divisibile per 400, cioè il 1600, il 2000, il 2400 eccetera.

Il seguente algoritmo determina se Anno è bisestile oppure no:

1) SE Anno è divisibile per 4 ma non è divisibile per 100
    ALLORA
        Anno è bisestile
        STOP

2) SE Anno è divisibile per 400,
    ALLORA
       Anno è bisestile
    ALTRIMENTI
       Anno non è bisestile
       STOP

Si noti l'uso dell'istruzione STOP, che serve per interrompere l'esecuzione dell'algoritmo. In caso contrario, dopo l'istruzione 1) verrebbe in ogni caso eseguita l'istruzione 2) e l'algoritmo non funzionerebbe correttamente.

 

h) Moltiplicazione fra due numeri senza usare il prodotto

Siano dati due numeri interi A e B. Si vuole calcolare il prodotto di A per B senza usare l'operatore di moltiplicazione, ovvero semplicemente eseguendo ripetutamente la somma. Ecco una possibile soluzione:

1) C = 0
2) RIPETI FINTANTOCHE' A è diverso da zero
    C = C + B
    A = A -1
3) Il risultato della moltiplicazione è in C

i) Confronto fra pesi

Si supponga di avere diversi pesi e di voler trovare quello di peso maggiore usando una bilancia a due braccia. La bilancia è in grado solo di fare il confronto fra il peso che si trova nel piatto A e quello che si trova nel piatto B, determinando il maggiore fra i due. Come si fa però a trovare il peso maggiore di tutti?

L'algoritmo è questo:

1) Prendi un peso qualsiasi e mettilo sul piatto A
2) RIPETI FINTANTOCHE' ci sono ancora pesi da pesare
- prendi un peso qualsiasi e mettilo sul piatto B
- SE B > A, ALLORA metti B in A e butta A
3) il peso maggiore si trova in A

   

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it