Algoritmo iterativo
Da Wikipedia, l'enciclopedia libera.
Dicesi algoritmo iterativo un algoritmo formulato per mezzo della ripetizione di sé stesso un certo numero di volte (un ciclo). Tutte le operazioni che richiedono la ripetizione di una stessa azione più volte, ma in numero finito sono dette procedure iterative. Ad ogni iterazione, l'esecutore svolge un compito. Al termine verifica se tale compito vada ripetuto mediante una condizione di ripetizione.
Indice |
[modifica] Esempio della catena di montaggio
Per spiegare meglio il concetto di algoritmo iterativo, si consideri il lavoro di un addetto ad una catena di montaggio: egli deve eseguire le stesse azioni ripetutamente finché ci sono pezzi da assemblare. L'algoritmo iterativo della catena di montaggio può essere così descritto:
1. Preleva i componenti 2. Assembla i componenti 3. Passa i componenti al collega 4. Se ci sono altri componenti da assemblare, torna al punto 1
[modifica] Utilizzo delle iterazioni nei linguaggi di programmazione
Per rendere agevole l'implementazione di procedure iterative nei linguaggi di programmazione di alto livello, sono disponibili due fondamentali costrutti: for e while. Il primo si presta ai cicli enumerativi (ossia quelli in cui il numero di iterazioni è prestabilito o dipende da un valore numerico calcolato prima dell'iterazione), mentre il secondo permette una libera applicazione della condizione di iterazione.
A tal proposito vanno fatte alcune importanti distinzioni sintattiche tra i linguaggi della famiglia C (con l'aggiunta di Java) e il linguaggio Visual Basic. Affrontiamo separatamente le sintassi dei suddetti costrutti nei due casi
[modifica] Famiglia C
Per quanto riguarda il costrutto for, la sintassi è la seguente:
for (istruzione iniziale; condizione di iterazione; istruzione di fine ciclo) { [istruzioni di iterazione] }
oppure
for (istruzione iniziale; condizione di iterazione; istruzione di fine ciclo) [istruzione di iterazione];
a seconda del fatto che una iterazione preveda una o più istruzioni. Il funzionamento è il seguente:
- Viene eseguita l'istruzione iniziale
- Viene eseguito il blocco iterativo
- Viene eseguita l'istruzione di fine ciclo
- Se la condizione di iterazione è vera viene ripetuto il ciclo, quindi si torna alla verifica della condizione
- Se la condizione di iterazione è falsa si esce dal ciclo
La definizione di cui sopra permette di utilizzare un ciclo for con qualunque tipo di condizione. Tuttavia tale ciclo si presta per algoritmi enumerativi. Ad esempio, il seguente codice C++ scrive a video, elemento per elemento, gli elementi di un array:
for (i = 0; i < count(arr); i++) cout << arr[i]<<endl;
Per quanto riguarda il costrutto while, esso specifica soltanto la condizione di iterazione, lasciando le due altre operazioni al codice. Esiste una variante, la do... while. Esaminiamone la sintassi:
while (condizione) { [istruzioni] } while (condizione) istruzione;
do { [istruzioni] } while (condizione); do [istruzione] while (condizione);
La differenza tra i costrutti è tanto semplice quanto sostanziale:
- While verifica la condizione: se è vera esegue il ciclo finché la condizione non diventerà falsa
- Do... While esegue la prima iterazione, e poi si comporta come il precedente
Do...While è dunque particolarmente indicato quando si ha a che fare con strutture dati dalle quali i dati da verificare devono prima essere estratti tramite una chiamata a funzione.
Ad esempio, posto di avere una classe di tipo Stack MyStack, contenente oggetti di tipo MyObj, vogliamo scrivere a video il contenuto degli oggetti fino a trovare un particolare elemento terminatore, posot che lo stack non sia mai vuoto (es. il costruttore inizializza lo stack col terminatore e la pop non lo elimina comunque). Il seguente codice richiede il ciclo do...while
char TERMINATOR = '\0'; MyStack Stk; MyObj Obj; string Objstr do { Obj = Stk.pop(); Objstr = Obj.content(); cout << Objstr << endl; } while (Objstr != TERMINATOR);
Nei linguaggi C è possibile controllare la sequenza dinamica dei cicli iterativi mediante due istruzioni in grado rispettivamente di saltare alla prossima iterazione o interrompere del tutto il ciclo. Tali istruzioni sono continue e break. Ad esempio il seguente codice mostra i primi 5 file eseguibili di una directory, memorizzata come array di stringhe. Nell'esempio non si tiene conto di estensioni multiple (es. .exe.bak)
k = 0; for (i = 0; 0 < count(dir); i++) { if (!strpos(".exe",dir[i])) continue; if (k == 5) break; cout << dir[i] << endl; k++; }
[modifica] Visual Basic
Nel linguaggio Visual Basic, con particolare riferimento alla versione .NET, è possibile realizzare cicli iterativi in maniera molto semplice grazie ai costrutti For... Next e Do... Loop.
Il ciclo For di VB è strettamente pensato per cicli enumerativi. Se in C i parametri del for sono liberi, in VB è richiesto che il ciclo sia numerico. Ecco la sintassi specifica (<> indicano opzionalità):
For [contatore] = [valore iniziale] To [valore finale] <Step [salto]> [istruzioni] Next
La variabile contatore deve essere di tipo numerico, i valori iniziale e finale possono essere anche funzioni che restituiscono un intero. Lo step è un valore opzionale che indica l'entità dell'incremento/decremento, che di default è 1 (o -1). L'esecutore riconosce dinamicamente, a runtime, se il ciclo deve essere incrementativo o decrementativo confrontando i valori inziale e finale.
Analogamente ai linguaggi C è possibile utilizare un ciclo Do... Loop in quattro diverse versioni
While [condizione] Do [istruzioni] Loop Do [istruzioni] While [condizione]
Le altre due si ottengono sostuendo a While il termine Until
- La prima sintassi verifica che la condizione sia vera prima di procedere
- La seconda esegue la prima iterazione e poi verifica che la condizione sia vera
- La terza e la quarta, analogamente con le precedenti, proseguono solo se la condizione è falsa
[modifica] Iterazioni nei linguaggi assemblativi
In assembly non sono disponibili costrutti iterativi. Questo perché essi collidono con il concetto di semplicità del linguaggio assemblativo. Per realizzare un ciclo for con istruzioni assemblative si parte dall'esempio della catena di montaggio, e si realizza il codice strutturandolo nel seguente modo:
- Si etichettano il punto di inzio ciclo (START) e la prima istruzione dopo il ciclo (END)
- Eventuali istruzioni pre-iterazione vanno prima della label START
- Istruzioni break corrispondono ad un salto incondizionato (JMP) a END
- Istruzioni continue corrispondono ad un salto incondizionato (JMP) a START
- Si implementa la condizione di iterazione su START, implementando un algoritmo di confronto tale che se la condizione è falsa si salta subito a END
- Si implementa tutto l'algoritmo dell'iterazione
- Si fa un salto incondizionato a START
[modifica] Voci correlate
Informatica | |||||
---|---|---|---|---|---|
Progetto Informatica | Portale Informatica | BarCode | |||
Categorie
|