商人过河问题

涛的个人资料徒然草的新园子照片日志列表更多

工具

帮助

日志

排列方式：

2009/3/4

3个商人带着3个仆人过河，过河的工具只有一艘小船，只能同时载两个人过河，包括划船的人。在河的任何一边，只要仆人的数量超过商人的数量，仆人就会联合起来将商人杀死并抢夺其财物，问应如何设计过河顺序才能让所有人都安全地过到河的另一边。

网上看到一个解答，学习了一下：

#include <stdio.h>

// 5 skemes to cross the river: 1 salesman, 1 servant, 2 salesman, 2 servant, 1 salesman and 1 servant.

char sln[5] = { ( 1 << 4 ), 1, ( 2 << 4 ), 2, ( 1 << 4 ) | 1 };
unsigned char curSln = 1;
char oldLayout[200][4], cur[200];
// Here b indicates going to the opposite bank or getting back.
void DoSolution( char b ) {
    unsigned long oldSln = curSln - 1;
    oldLayout[ curSln ][0] = oldLayout[ oldSln ][0] - b * ( ( sln[ cur[ curSln ] ] & 0xF0 ) >> 4 );
    oldLayout[ curSln ][1] = oldLayout[ oldSln ][1] - b * ( sln[ cur[ curSln ] ] & 0xF );
    oldLayout[ curSln ][2] = oldLayout[ oldSln ][2] + b * ( ( sln[ cur[ curSln ] ] & 0xF0 ) >> 4 );
    oldLayout[ curSln ][3] = oldLayout[ oldSln ][3] + b * ( sln[ cur[ curSln ] ] & 0xF );
}

bool BeRepeated( char b ) {
    for( unsigned long i = 0; i < curSln; i++ )
        if( oldLayout[ curSln ][0] == oldLayout[ i ][0] &&
                oldLayout[ curSln ][1] == oldLayout[ i ][1] &&
                oldLayout[ curSln ][2] == oldLayout[ i ][2] &&
                oldLayout[ curSln ][3] == oldLayout[ i ][3] &&
                ( ( i & 1 ) ? 1 : -1 ) == b ) // go or back must be same
                // i&1 equals i%2; i&7 equals i%8, so does i&63 and i%64.
            return true;
    return false;
}

int main() {
    char b = 1;
    oldLayout[0][0] = oldLayout[0][1] = 3;
    cur[0] = oldLayout[0][2] = oldLayout[0][3] = 0;
    for( unsigned char i = 0; i < 200; i++ )      cur[ i ] = 0;

    do   {
        DoSolution( b );
        if( ( oldLayout[ curSln ][1] > oldLayout[ curSln ][0] && oldLayout[ curSln ][0] ) ||
                ( oldLayout[ curSln ][3] > oldLayout[ curSln ][2] && oldLayout[ curSln ][2] ) ||
                oldLayout[ curSln ][0] < 0 || oldLayout[ curSln ][1] < 0 ||
                oldLayout[ curSln ][2] < 0 || oldLayout[ curSln ][3] < 0 ||
                BeRepeated( b ) )      {
            // rechoose a scheme...
P:
               cur[ curSln ]++;
               if( cur[ curSln ] > 4 )   {
                    b = -b;
               cur[ curSln ] = 0;
                curSln--;
                    if( !curSln ) break; // no answer to this question.
                    goto P;
               }
            continue;
         }
        b = -b;
        curSln++;
    }
    while( !( oldLayout[ curSln - 1 ][0] == 0 && oldLayout[ curSln - 1 ][1] == 0 && oldLayout[ curSln - 1 ][2] == 3 && oldLayout[ curSln - 1 ][3] == 3 ) );

    for(unsigned char i = 0; i < curSln; i++ )
        printf( "%d %d\t %d %d\n", oldLayout[ i ][0], oldLayout[ i ][1], oldLayout[ i ][2], oldLayout[ i ][3] );
    return 0;
}

输出如下：
3 3      0 0
3 1      0 2
3 2      0 1
3 0      0 3
3 1      0 2
1 1      2 2
2 2      1 1
0 2      3 1
0 3      3 0
0 1      3 2
1 1      2 2
0 0      3 3