In questo articolo presenterò un sorgente C che permette di risolvere il famoso problema dell'attraversamento di un fiume con capra, cavolo e lupo.
L'idea è di utilizzare due parole da 16 bit (word) in cui ogni singolo bit rappresenta un oggetto (ad esempio 0x0001=capra, 0x0002=cavolo, 0x0004=lupo ...): una parola rappresenterà gli oggetti che devono attraversare il fiume (da_attraversare) mentre l'altra rappresenterà gli oggetti che lo hanno attraversato (attraversato):
word da_attraversare;
word attraversato;
Quindi, ad esempio, nel caso si debbano fare attraversare lupo,capra e cavolo si partirà con:
da_attraversare = 0x0007;
attraversato = 0x0000;
Ecco che quindi l'attraversamento e il riattraversamento sono due operazioni molto semplici:
// ATTRAVERSAMENTO:
da_attraversare = da_attraversare & ~oggetto;
attraversato = attraversato | oggetto;
// RIATTRAVERSAMENTO:
attraversato = attraversato & ~oggetto;
da_attraversare = da_attraversare | oggetto;
dove oggetto è una word con un solo bit settato (quello relativo all'oggetto che si vuole spostare).
Nota: utilizzando una word il numero massimo di oggetti gestibili è 16.
E' necessario identificare quali combinazioni di oggetti sono ammesse e quali no; per questo all'avvio viene predisposto l'array combinazioni[] in cui l'indice è dato dalla combinazione (nell'esempio, cavolo e lupo sarà 0x0002+0x0004 = 0x0006) e il contenuto sarà 0 per indicare combinazione non ammessa o 1 per indicare combinazione ammessa.
char combinazioni[ MAX_COMBINAZIONI ];
Il numero massimo di combinazioni dipende dal numero massimo di oggetti, precisamente il numero di combinazioni è dato da 2^n_oggetti: all'interno del software il numero di oggetti massimo è stato limitato a 10 in modo da avere un array combinazioni[] di 1024 bytes.
Una volta fatto compilare all'utente la tabella delle combinazioni con le soluzioni ammesse e non ammesse (attivando la #define DEBUG ci sono alcune tabelle precompilate), l'algoritmo prevede delle chiamate fra queste due funzioni:
int attraversa_fiume( word oggetto_spostato );
int riattraversa_fiume( word oggetto_spostato );
Ogni volta che si attraversa o riattraversa il fiume bisogna passare l'oggetto spostato in maniera che al successivo attraversamento o riattraversamento non si riporti indietro lo stesso oggetto (si creerebbe un ciclo infinito).
Queste due funzioni si richiamano fra di loro finchè la parola da_attraversare non si azzera, a quel punto si uscirà da tutte le chiamate per ritornare immediatamente al main().
Per quanto riguarda le soluzioni trovate, ecco gli output del programma:
Inserire il numero di oggetti da far attraversare: 3
Inserisci i nomi degli oggetti:
Oggetto n.1 :lupo
Oggetto n.2 :capra
Oggetto n.3 :cavolo
Ora rispondi S (si) alle combinazioni ammesse e N (no) a quelle non ammesse:
lupo s
capra s
lupo capra n
cavolo s
lupo cavolo s
capra cavolo n
La soluzione si svolge in 7 passi:
attraversa con capra
riattraversa da solo
attraversa con lupo
riattraversa con capra
attraversa con cavolo
riattraversa da solo
attraversa con capra
/******************************************************************************* Autore: Sebastien Costa Data: 01/10/2006 Descrizione: come salvare capra e cavoli *******************************************************************************/ #include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
/******************************************************************************* ridefinizioni e strutture *******************************************************************************/ #define word unsigned short // 16 bit senza segno typedef struct { char tipo; word oggetti; } str_attr; #define ATTRAVERSAMENTO 1 #define RIATTRAVERSAMENTO 2 /******************************************************************************* prototipi di funzione *******************************************************************************/ int attraversa_fiume( word oggetto_spostato ); int riattraversa_fiume( word oggetto_spostato ); /******************************************************************************* attivare la flag DEBUG assieme ad uno dei contesti per ottenere informazioni di debug ed evitare di ricaricare ogni volta le combinazioni *******************************************************************************/ //#define DEBUG //#define LUPO_CAPRA_CAVOLO //#define LUPO_CAPRA_CAVOLO_LEVIATANO //#define LEOPARDO_CAPRA_TOPO_MAIS /******************************************************************************* costanti *******************************************************************************/ #define MAX_OGGETTI 10 #define MAX_COMBINAZIONI 1024 // 2 ^ MAX_OGGETTI #define MAX_NAME_LEN 20 #define MAX_ATTRAVERSAMENTI 10 // numero massimo di attraversamenti /******************************************************************************* variabili globali *******************************************************************************/ int n_oggetti; // numero di oggetti inseriti dall'utente int n_combinazioni; // 2 ^ n_oggetti char name[ MAX_OGGETTI ][ MAX_NAME_LEN ]; // tabella dei nomi degli oggetti char combinazioni[ MAX_COMBINAZIONI ]; // elenco combinazioni (ammesse o non ammesse) char traghettabile[ MAX_COMBINAZIONI ]; // elenco combinazioni di oggetti traghettabili assieme // (ammesse o non ammesse) word da_attraversare; // maschera oggetti che devono attraversare word attraversato; // maschera oggetti che sono attraversati int passo; // passo corrente str_attr attr[ MAX_ATTRAVERSAMENTI ]; // log dei passi che stiamo eseguendo int min_passi; // il minimo di passi fra tutte le soluzioni trovate str_attr min_attr[ MAX_ATTRAVERSAMENTI ]; /******************************************************************************* attraversa_fiume() *******************************************************************************/ int attraversa_fiume( word oggetto_spostato ) { int i; word da_attraversare_save; word attraversato_save; da_attraversare_save = da_attraversare; // salva lo stato all'entrata attraversato_save = attraversato; if( passo >= MAX_ATTRAVERSAMENTI ) return 0; #ifdef DEBUG printf( "%02d attraversa_fiume(0x%02X) 0x%02X 0x%02Xn", passo, oggetto_spostato, da_attraversare, attraversato ); getch(); #endif if( oggetto_spostato != 0 ) // possiamo anche attraversare senza niente { if( combinazioni[ da_attraversare ] ) { attr[ passo ].tipo = ATTRAVERSAMENTO; attr[ passo ].oggetti = 0; passo ++; if( riattraversa_fiume( 0 ) ) // facciamo un tentativo andando senza niente return 1; passo --; } } for( i = 1; i < n_combinazioni; i ++ ) // ciclo su tutte le possibili combinazioni di oggetti { if( i != oggetto_spostato ) // evita un loop avanti-indietro di un solo oggetto { if( ( traghettabile[ i ] ) && // se è una combinazione traghettabile ( da_attraversare & i ) == i ) // e se gli oggetti devono attraversare { // proviamo a farlo attraversare // salviamo l'azione attr[ passo ].tipo = ATTRAVERSAMENTO; attr[ passo ].oggetti = i; // toglie l'oggetto da da_attraversare e lo mette in attraversato da_attraversare = da_attraversare & ~i; attraversato = attraversato | i; if( da_attraversare == 0 ) // se abbiamo fatto attraversare tutto { #ifdef DEBUG printf( "Ho fatto attraversare tutto!!!n" ); getch(); #endif if( passo < min_passi ) // se la soluzione è migliore rispetto alla precedente { min_passi = passo; memcpy( (void *)&min_attr, (void *)&attr, sizeof(str_attr) * MAX_ATTRAVERSAMENTI ); } return 0; } // se la combinazione è giusta, facciamo attraversare qualcun altro if( combinazioni[ da_attraversare ] ) { passo ++; if( riattraversa_fiume( i ) ) return 1; // se abbiamo risolto, usciamo subito passo --; } // ripristina come prima di questo attraversamento... da_attraversare = da_attraversare_save; attraversato = attraversato_save; } } } return 0; } /******************************************************************************* riattraversa_fiume() *******************************************************************************/ int riattraversa_fiume( word oggetto_spostato ) { int i; word da_attraversare_save; word attraversato_save; da_attraversare_save = da_attraversare; // salva lo stato all'entrata attraversato_save = attraversato; if( passo >= MAX_ATTRAVERSAMENTI ) return 0; #ifdef DEBUG printf( "%02d riattraversa_fiume(0x%02X) 0x%02X 0x%02Xn", passo, oggetto_spostato, da_attraversare, attraversato ); getch(); #endif if( oggetto_spostato != 0 ) // possiamo anche tornare senza niente { if( combinazioni[ attraversato ] ) { attr[ passo ].tipo = RIATTRAVERSAMENTO; attr[ passo ].oggetti = 0; passo ++; if( attraversa_fiume( 0 ) ) // facciamo un tentativo tornando indietro senza niente return 1; passo --; } } for( i = 1; i < n_combinazioni; i ++ ) // ciclo su tutte le possibili combinazioni di oggetti { if( i != oggetto_spostato ) // evita un loop avanti-indietro di un solo oggetto { if( ( traghettabile[ i ] ) && // se è una combinazione traghettabile ( attraversato & i ) == i ) // e se gli oggetti sono già attraversati { // proviamo a portarli indietro // salviamo l'azione attr[ passo ].tipo = RIATTRAVERSAMENTO; attr[ passo ].oggetti = i; // toglie l'oggetto da attraversato e lo mette in da_attraversare attraversato = attraversato & ~i; da_attraversare = da_attraversare | i; // se la combinazione è giusta, facciamo attraversare qualcun altro if( combinazioni[ attraversato ] ) { passo ++; if( attraversa_fiume( i ) ) return 1; // se abbiamo risolto, usciamo subito passo --; } // ripristina come prima di questo attraversamento... da_attraversare = da_attraversare_save; attraversato = attraversato_save; } } } return 0; } /******************************************************************************* main() *******************************************************************************/ int main() { int i, j; word mask; char buff[ 80 ]; #ifndef DEBUG // inserimento dati (possibilità di caricare da file...) printf( "Inserire il numero di oggetti da far attraversare: " ); n_oggetti = atoi( gets( buff ) ); if( ( n_oggetti < 1 ) || ( n_oggetti > MAX_OGGETTI ) ) { printf( "nmi dispiace, gestisco da 1 a %d oggetti...", MAX_OGGETTI ); return 0; } printf( "nInserisci i nomi degli oggetti:n" ); for( i = 0; i < n_oggetti; i ++ ) { printf( "Oggetto n.%d :", i+1 ); gets( name[ i ] ); } n_combinazioni = 1; for( i = 0; i < n_oggetti; i ++ ) n_combinazioni = n_combinazioni * 2; combinazioni[ 0 ] = 0; // combinazione non ammessa combinazioni[ n_combinazioni-1 ] = 0; // combinazione non ammessa printf( "nOGGETTI CHE POSSONO STARE ASSIEME DA SOLIn" ); printf( "Ora rispondi S (si) alle combinazioni ammesse e N (no) a quelle non ammesse:n" ); for( i = 1; i < ( n_combinazioni - 1 ); i ++ ) { mask = 0x0001; for( j = 0; j < n_oggetti; j ++ ) // stampa gli oggetti compresi in 'i' { if( i & mask ) printf( "%s ", name[ j ] ); mask = mask << 1; // ad ogni oggetto corrisponde un bit della maschera } gets( buff ); // legge input da tastiera if( ( buff[ 0 ] == 'S' ) || ( buff[ 0 ] == 's' ) ) combinazioni[ i ] = 1; // ammessa else combinazioni[ i ] = 0; // non ammessa } printf( "nOGGETTI CHE POSSONO ESSERE TRAGHETTATI ASSIEMEn" ); printf( "Ora rispondi S (si) alle combinazioni ammesse e N (no) a quelle non ammesse:n" ); for( i = 1; i < ( n_combinazioni - 1 ); i ++ ) { mask = 0x0001; for( j = 0; j < n_oggetti; j ++ ) // stampa gli oggetti compresi in 'i' { if( i & mask ) printf( "%s ", name[ j ] ); mask = mask << 1; // ad ogni oggetto corrisponde un bit della maschera } gets( buff ); // legge input da tastiera if( ( buff[ 0 ] == 'S' ) || ( buff[ 0 ] == 's' ) ) traghettabile[ i ] = 1; // ammessa else traghettabile[ i ] = 0; // non ammessa } #else #ifdef LUPO_CAPRA_CAVOLO n_oggetti = 3; strcpy( name[ 0 ], "lupo" ); strcpy( name[ 1 ], "capra" ); strcpy( name[ 2 ], "cavolo" ); n_combinazioni = 1; for( i = 0; i < n_oggetti; i ++ ) n_combinazioni = n_combinazioni * 2; combinazioni[ 0x00 ] = 0; // | | combinazioni[ 0x01 ] = 1; // lupo | | combinazioni[ 0x02 ] = 1; // | capra | combinazioni[ 0x03 ] = 0; // lupo | capra | combinazioni[ 0x04 ] = 1; // | | cavolo combinazioni[ 0x05 ] = 1; // lupo | | cavolo combinazioni[ 0x06 ] = 0; // | capra | cavolo combinazioni[ 0x07 ] = 0; // lupo | capra | cavolo traghettabile[ 0x00 ] = 0; // | | traghettabile[ 0x01 ] = 1; // lupo | | traghettabile[ 0x02 ] = 1; // | capra | traghettabile[ 0x03 ] = 0; // lupo | capra | traghettabile[ 0x04 ] = 1; // | | cavolo traghettabile[ 0x05 ] = 0; // lupo | | cavolo traghettabile[ 0x06 ] = 0; // | capra | cavolo traghettabile[ 0x07 ] = 0; // lupo | capra | cavolo #endif #ifdef LUPO_CAPRA_CAVOLO_LEVIATANO n_oggetti = 4; strcpy( name[ 0 ], "lupo" ); strcpy( name[ 1 ], "capra" ); strcpy( name[ 2 ], "cavolo" ); strcpy( name[ 3 ], "leviatano" ); n_combinazioni = 1; for( i = 0; i < n_oggetti; i ++ ) n_combinazioni = n_combinazioni * 2; combinazioni[ 0x00 ] = 0; // | | | combinazioni[ 0x01 ] = 1; // lupo | | | combinazioni[ 0x02 ] = 1; // | capra | | combinazioni[ 0x03 ] = 0; // lupo | capra | | combinazioni[ 0x04 ] = 1; // | | cavolo | combinazioni[ 0x05 ] = 1; // lupo | | cavolo | combinazioni[ 0x06 ] = 0; // | capra | cavolo | combinazioni[ 0x07 ] = 0; // lupo | capra | cavolo | combinazioni[ 0x08 ] = 1; // | | | leviatano combinazioni[ 0x09 ] = 0; // lupo | | | leviatano combinazioni[ 0x0A ] = 1; // | capra | | leviatano combinazioni[ 0x0B ] = 0; // lupo | capra | | leviatano combinazioni[ 0x0C ] = 1; // | | cavolo | leviatano combinazioni[ 0x0D ] = 1; // lupo | | cavolo | leviatano combinazioni[ 0x0E ] = 0; // | capra | cavolo | leviatano combinazioni[ 0x0F ] = 0; // lupo | capra | cavolo | leviatano traghettabile[ 0x00 ] = 0; // | | | traghettabile[ 0x01 ] = 1; // lupo | | | traghettabile[ 0x02 ] = 1; // | capra | | traghettabile[ 0x03 ] = 0; // lupo | capra | | traghettabile[ 0x04 ] = 1; // | | cavolo | traghettabile[ 0x05 ] = 0; // lupo | | cavolo | traghettabile[ 0x06 ] = 0; // | capra | cavolo | traghettabile[ 0x07 ] = 0; // lupo | capra | cavolo | traghettabile[ 0x08 ] = 1; // | | | leviatano traghettabile[ 0x09 ] = 0; // lupo | | | leviatano traghettabile[ 0x0A ] = 0; // | capra | | leviatano traghettabile[ 0x0B ] = 0; // lupo | capra | | leviatano traghettabile[ 0x0C ] = 0; // | | cavolo | leviatano traghettabile[ 0x0D ] = 0; // lupo | | cavolo | leviatano traghettabile[ 0x0E ] = 0; // | capra | cavolo | leviatano traghettabile[ 0x0F ] = 0; // lupo | capra | cavolo | leviatano #endif #ifdef LEOPARDO_CAPRA_TOPO_MAIS n_oggetti = 4; strcpy( name[ 0 ], "leopardo" ); strcpy( name[ 1 ], "capra" ); strcpy( name[ 2 ], "topo" ); strcpy( name[ 3 ], "mais" ); n_combinazioni = 1; for( i = 0; i < n_oggetti; i ++ ) n_combinazioni = n_combinazioni * 2; combinazioni[ 0x00 ] = 0; // | | | combinazioni[ 0x01 ] = 1; // leopardo | | | combinazioni[ 0x02 ] = 1; // | capra | | combinazioni[ 0x03 ] = 0; // leopardo | capra | | combinazioni[ 0x04 ] = 1; // | | topo | combinazioni[ 0x05 ] = 0; // leopardo | | topo | combinazioni[ 0x06 ] = 1; // | capra | topo | combinazioni[ 0x07 ] = 0; // leopardo | capra | topo | combinazioni[ 0x08 ] = 1; // | | | mais combinazioni[ 0x09 ] = 1; // leopardo | | | mais combinazioni[ 0x0A ] = 0; // | capra | | mais combinazioni[ 0x0B ] = 0; // leopardo | capra | | mais combinazioni[ 0x0C ] = 0; // | | topo | mais combinazioni[ 0x0D ] = 0; // leopardo | | topo | mais combinazioni[ 0x0E ] = 0; // | capra | topo | mais combinazioni[ 0x0F ] = 0; // leopardo | capra | topo | mais traghettabile[ 0x00 ] = 0; // | | | traghettabile[ 0x01 ] = 1; // leopardo | | | traghettabile[ 0x02 ] = 1; // | capra | | traghettabile[ 0x03 ] = 0; // leopardo | capra | | traghettabile[ 0x04 ] = 1; // | | topo | traghettabile[ 0x05 ] = 0; // leopardo | | topo | traghettabile[ 0x06 ] = 0; // | capra | topo | traghettabile[ 0x07 ] = 0; // leopardo | capra | topo | traghettabile[ 0x08 ] = 1; // | | | mais traghettabile[ 0x09 ] = 1; // leopardo | | | mais traghettabile[ 0x0A ] = 1; // | capra | | mais traghettabile[ 0x0B ] = 0; // leopardo | capra | | mais traghettabile[ 0x0C ] = 1; // | | topo | mais traghettabile[ 0x0D ] = 0; // leopardo | | topo | mais traghettabile[ 0x0E ] = 0; // | capra | topo | mais traghettabile[ 0x0F ] = 0; // leopardo | capra | topo | mais #endif #endif // predispone gli oggetti da far attraversare da_attraversare = 0; attraversato = 0; mask = 0x0001; for( i = 0; i < n_oggetti; i ++ ) { da_attraversare = da_attraversare | mask; mask = mask << 1; } // elaborazione con relativa stampa dei risultati passo = 0; min_passi = 99; attraversa_fiume( 0x0000 ); if( min_passi != 99 ) { printf( "La soluzione si svolge in %d passi:n", min_passi+1 ); for( i = 0; i <= min_passi; i ++ ) { if( min_attr[ i ].tipo == ATTRAVERSAMENTO ) printf( "attraversa " ); else printf( "riattraversa " ); if( min_attr[ i ].oggetti == 0 ) printf( "da solo" ); else { printf( "con " ); mask = 0x0001; for( j = 0; j < n_oggetti; j ++ ) { if( min_attr[ i ].oggetti & mask ) { printf( name[ j ] ); printf( " " ); } mask = mask << 1; } } printf( "n" ); } } else { printf( "Non ho trovato alcuna soluzione...n" ); } return 0; }
