Risolviamo il famoso problema con l'aiuto del pc
In questo articolo presenterò un sorgente C che permette di risolvere il famoso problema dell'attraversamento di un fiume con capra, cavolo e lupo: questo programma è stato presentato sulla rivista Dev. #143 come una delle soluzioni a questo problema.
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:
LUPO-CAPRA-CAVOLO
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 (per Doctor Brom - DEV.143)
*******************************************************************************/
#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;
}
Copyright © by Sebastien Costa All Right Reserved.
