C++从零开始（八）——C++样例一(2)

    检查是否成功：即看是否

    oldLayout[1][ curSln ] > oldLayout[0][ curSln ] && oldLayout[0][ curSln ]以及是否

    oldLayout[3][ curSln ] > oldLayout[2][ curSln ] && oldLayout[2][ curSln ]

    并且保证各自不为负数以及没有和原来的方案冲突。检查是否和原有方案相同就是枚举所有原由方案以和当前方案比较，由于比较复杂，在此将其定义为函数，通过返回bool类型来表示是否冲突。

    退回上一次方案或到下一个方案的选择，只用curSln——或curSln++即可。而是否所有人都过河，则只用oldLayout[0～1][ curSln ]都为0而oldLayout[2～3][ curSln ]都为3.而判断人数布局是否相同，则只用相应各元素是否相等即可。

    第三步：下面剩下的就没什么东西了，只需要按照算法说的顺序，将刚才的各操作拼凑起来，并注意“重复直到所有人都过河了”转成do while即可。如下：

 #include// 分别表示一个商人、一个仆人、两个商人、两个仆人、一个商人一个仆人
char sln[5] = { ( 1 << 4 ), 1, ( 2 << 4 ), 2, ( 1 << 4 ) | 1 };
unsigned char curSln = 1;
char oldLayout[4][200], cur[200];

void DoSolution( char b )
{
    unsigned long oldSln = curSln - 1;  // 临时变量，出于效率
    oldLayout[0][ curSln ] =
        oldLayout[0][ oldSln ] - b * ( ( sln[ cur[ curSln ] ] & 0xF0 ) >> 4 );
    oldLayout[1][ curSln ] =
        oldLayout[1][ oldSln ] - b * ( sln[ cur[ curSln ] ] & 0xF );
    oldLayout[2][ curSln ] =
        oldLayout[2][ oldSln ] + b * ( ( sln[ cur[ curSln ] ] & 0xF0 ) >> 4 );
    oldLayout[3][ curSln ] =
        oldLayout[3][ oldSln ] + b * ( sln[ cur[ curSln ] ] & 0xF );
}
bool BeRepeated( char b )
{
    for( unsigned long i = 0; i < curSln; i++ )
        if( oldLayout[0][ curSln ] == oldLayout[0][ i ] &&
            oldLayout[1][ curSln ] == oldLayout[1][ i ] &&
            oldLayout[2][ curSln ] == oldLayout[2][ i ] &&
            oldLayout[3][ curSln ] == oldLayout[3][ i ] &&
            ( ( i & 1 ) ? 1 : -1 ) == b )  // 保证过河后的方案之间比较，回来后的方案之间比较
                                           // i&1等效于i%2，i&7等效于i%8，i&63等效于id
            return true;
    return false;
}
void main()
{
    char b = 1;
    oldLayout[0][0] = oldLayout[1][0] = 3;
    cur[0] = oldLayout[2][0] = oldLayout[3][0] = 0;
    for( unsigned char i = 0; i < 200; i++ )  // 初始化每次选择方案时的初始化方案为sln[0]
        cur[ i ] = 0;                         // 由于cur是全局变量，在VC中，其已经被赋值为0
                                              // 原因涉及到数据节，在此不表
    do
    {
        DoSolution( b );
        if( ( oldLayout[1][ curSln ] > oldLayout[0][ curSln ] && oldLayout[0][ curSln ] ) ||
            ( oldLayout[3][ curSln ] > oldLayout[2][ curSln ] && oldLayout[2][ curSln ] ) ||
            oldLayout[0][ curSln ] < 0 || oldLayout[1][ curSln ] < 0 ||
            oldLayout[2][ curSln ] < 0 || oldLayout[3][ curSln ] < 0 ||
            BeRepeated( b ) )
        {
        // 重新选择本次的方案
P:
            cur[ curSln ]++;
            if( cur[ curSln ] > 4 )
            {
                b = -b;
                cur[ curSln ] = 0;
                curSln--;
                if( !curSln )
                    break;  // 此题无解
                goto P;  // 重新检查以保证cur[ curSln ]的有效性
            }
            continue;
        }
        b = -b;
        curSln++;
    }
    while( !( oldLayout[0][ curSln - 1 ] == 0 && oldLayout[1][ curSln - 1 ] == 0 &&
              oldLayout[2][ curSln - 1 ] == 3 && oldLayout[3][ curSln - 1 ] == 3 ) );

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

    上面数组sln[5]的初始化方式下篇介绍。上面的预编译指令#include将在《C++从零开始（十）》中说明，这里可以不用管它。上面使用的函数printf的用法，请参考其它资料，这里它只是将变量的值输出在屏幕上而已。

    前面说此法是枚举法，其基本上属于万能方法，依靠CPU的计算能力来实现，一般情况下程序员第一时间就会想到这样的算法。它的缺点就是效率极其低下，大量的CPU资源都浪费在无谓的计算上，因此也是产生瓶颈的大多数原因。由于它的万能，编程时很容易将思维陷在其中，如求和1到100，一般就写成如下：

    for（ unsigned long i = 1， s = 0； i <= 100； i++ ） s += i；

    但更应该注意到还可unsigned long s = （ 1 + 100 ） * 100 / 2；，不要被枚举的万能占据了头脑。

    上面的人数布局映射成一结构是最好的，映射成char[4]所表现的语义不够强，代码可读性较差。下篇说明结构，并展示类型的意义——如何解释内存的值。