Esatto, ti faccio un esempio banale:
in un software come un videogame (tetris?) la mappa del livello potrebbe stare in un array bidimensionale n*m (una matrice), tanto ne conosciamo le dimensioni quando lo programmiamo, ma se volessimo trovare il MDC tra n numeri dati in input dall'utente senza conoscere n a priori non sapremmo quanto fare grande l'array e converrebbe usare le liste.
Uso il secondo esempio definendo induttivamente/ricorsivamente il MCD (non saro' rigorosissimo):
- base induttiva: il MCD di un numero solo e' se stesso, quello di 0 e' 0
- passo di induzione: il MCD di n numeri e' uguale al MCD tra il primo numero e gli n-1 numeri restanti
Grazie al passo dell'induzione possiamo reiterare il calcolo dell'MCD tra soli due numeri fino ad ottenere quello di tutti gli n insieme.
Ora vediamo i file coinvolti.
mcd.h
- Codice: Seleziona tutto
// Contiene i prototipi delle nostre funzioni piu' alcune definizioni
#ifndef MCD
// Se mcd.h e' stato gia' incluso da qualche altro programma non abbiamo bisogno di reincluderlo
// quindi controlliamo l'esistenza di un token inventato da noi
#define MCD
#include <iostream>
using namespace std;
{
struct node
{
int value;
node *next;
}
typedef *node list; // La nostra lista e' il puntatore al primo valore
list emptyList=NULL;
bool isEmpty(list);
void headInsert(list, list);
int mcd(list);
}
#endif
mcd.cpp
// Contiene le funzioni vere e proprie definite in mcd.h
#include <iostream>
#include "mcd.h"
using namespace std;
bool isEmpty(list l) {
return (l == emptyList);
}
void headInsert(list l, list n) {
if (isEmpty(l)) {
l = n;
n->next = emptyList;
return;
}
else {
n->next = l;
l = n;
}
}
int mcd(list l)
// Contiene l'algoritmo euclideo, non la scrivo
Dentro il main dovrai includere mcd.h e fare due cicli:
- uno while per inserire i numeri finche' l'utente desidera usando la funzione headInsert
- un if che se la lista e' vuota o contiene un numero solo restituisce, rispettivamente 0 o il numero, altrimenti chiama ricorsivamente mcd su l->next.
Per effettuare cicli con la ricorsione NON servono ne' for ne' while, il ciclo lo realizza la ricorsione in se'.
