三、商人过河问题

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

　　给出最弱却万能的算法——枚举法。坐船过河及划船回来的可能方案为一个仆人、一个商人或两个商人、两个仆人及一个商人一个仆人。

　　故每次从上述的五种方案中选择一个划过河去，然后检查河岸两侧的人数，看是否会发生仆人杀死商人，如果两边都不会，则再从上述的五个方案中选择一个让人把船划回来，然后再检查是否会发生仆人杀死商人，如果没有就又重新从五个方案中选一个划过河，如上重复直到所有人都过河了。

　　上面在选方案时除了保证商人不被杀死，还要保证此方案运行（即过河或划回来）后，两岸的人数布局从来都没有出现过，否则就形成无限循环，且必须合理，即没有负数。如果有一次的方案选择失败，则退回去重新选另一个方案再试。如果所有方案都失败，则再退回到更上一次的方案选择。如果一直退到第一次的方案选择，并且已没有可选的方案，则说明上题无解。

　　上面的算法又提出了两个基本又重要的概念——层次及容器。下面先说明容器。容器即装东西的东西，而C++中操作的东西只有数字，因此容器就是装数字的东西，也就是内存。容器就平常的理解是能装多个东西，即能装多个数字。这很简单，使用之前的数组的概念就行了。但如果一个盒子能装很多苹果，那它一定占很大的体积，即不管装了一个苹果还是两个苹果，那盒子都要占半立方米的体积。数组就好像盒子，不管装一个元素还是两个元素，它都是long[10]的类型而要占40个字节。

　　容器是用来装东西的，那么要取出容器中装的东西，就必须有种手段标识容器中装的东西，对于数组，这个东西就是数组的下标，如long a[10]; a[3];就取出了第四个元素的值。由于有了标识，则还要有一种手段以表示哪些标识是有效的，如上面的a数组，只前面两个元素记录了数字，但是却a[3];，得到的将是错误的值，因为只有a[0]和a[1]是有意义的。

　　因此上面的用数组作容器有很多的问题，但它非常简单，并能体现各元素之间的顺序关系，如元素被排序后的数组。但为了适应复杂算法，必须还要其他容器的支持，如链表、树、队列等。它们一般也被称做集合，都是用于管理多个元素用的，并各自给出了如何从众多的元素中快速找到给定标识所对应的元素，而且都能在各元素间形成一种关系，如后面将要提到的层次关系、前面数组的顺序关系等。关于那些容器的具体实现方式，请参考其他资料，在此不表。

　　上面算法中提到“两岸的人数布局从来都没有出现过”，为了实现这点，就需要将其中的资源——人数布局映射为数字，并且还要将曾经出现过的所有人数布局全部记录下来，也就是用一个容器记录下来，由于还未说明结构等概念，故在此使用数组来实现这个容器。上面还提到从已有的方案中选择一个，则可选的方案也是一个容器，同上，依旧使用一数组来实现。

　　层次，即关系，如希望小学的三年2班的XXX、中国的四川的成都的XXX等，都表现出一种层次关系，这种层次关系是多个元素之间的关系，因此就可以通过找一个容器，那个容器的各元素间已经是层次关系，则这个容器就代表了一种层次关系。树这种容器就是专门对此而设计的。

　　上面算法中提到的“再退回到更上一次的方案选择”，也就是说第一次过河选择了一个商人一个仆人的方案，接着选择了一个商人回来的方案，此时如果选择两个仆人过河的方案将是错误的，则将重新选择过河的方案。再假设此时所有过河的方案都失败了，则只有再向后退以重新选择回来的方案，如选择一个仆人回来。对于此，由于这里只要求退回到上一次的状态，也就是人数布局及选择的方案，则可以将这些统一放在容器中，而它们各自都只依靠顺序关系，即第二次过河的方案一定在第一次过河的方案成功的前提下才可能考虑，因此使用数组这个带有顺序关系的容器即可。

　　第一步：上面算法的资源有两个：坐船的方案和两岸的人数布局。坐船的方案最多五种，在此使用一个char类型的数字来映射它，即此8位二进制数的前4位用补码格式来解释得到的数字代表仆人的数量，后4位则代表商人的数量。因此一个商人和一个仆人就是( 1 << 4 ) | 1。两岸的人数布局，即两岸的商人数和仆人数，由于总共才3+3=6个人，这都可以使用char类型的数字就能映射，但只能映射一个人数，而两岸的人数实际共有4个（左右两岸的商人数和仆人数），则这里使用一个char[4]来实现（实际最好是使用结构来映射而不是char[4]，下篇说明）。如char a[4];表示一人数布局，则a[0]表示河岸左侧的商人数，a[1]表示左侧的仆人数，a[2]表示河岸右侧的商人数，a[3]表示右侧的仆人数。

　　注意前面说的容器，在此为了装可选的坐船方案故应有一容器，使用数组，如char sln[5];。在此还需要记录已用的坐船方案，由于数组的元素具备顺序关系，所以不用再生成一容器，直接使用一char数字记录一下标，当此数字为3时，表示sln[0]、sln[1]和sln[2]都已经用过且都失败了，当前可用的为sln[3]和sln[4]。同样，为了装已成功的坐船方案作用后的人数布局及当时所选的方案，就需要两个容器，在此使用数组（实际应该链表）char oldLayout[200][4], cur[200];。oldLayout就是记录已成功的方案的容器，其大小为200，表示假定在200次内，一定就已经得出结果了，否则就会因为超出数组上限而可能发生内存访问违规，而为什么是可能在《C++从零开始（十五）》中说明。

　　前面说过数组这种容器无法确定里面的有效元素，必须依靠外界来确定，对此，使用一unsigned char curSln;来记录oldLayout和cur中的有效元素的个数。规定当curSln为3时，表示oldLayout[0][0～3]、oldLayout[1][0～3]和oldLayout[2][0～3]都有效，同样cur[0]、cur[1]和cur[2]都有效，而之后的如cur[3]等都无效。

　　第二步：操作有：执行过河方案、执行回来方案、检查方案是否成功、退回到上一次方案选择、是否所有人都过河、判断人数布局是否相同。如下：

　　前两个操作：将当前的左岸人数减去相应的方案定的人数，而右岸则加上人数。要表现当前左岸人数，可以用oldLayout[ curSln ][0]和oldLayout[ curSln ][1]表示，而相应方案的人数则为( sln[ cur[ curSln ] ] & 0xF0 ) >> 4和sln[ cur[ curSln ] ] & 0xF。由于这两个操作非常类似，只是一个是加则另一个就是减，故将其定义为函数，则为了在函数中能操作oldLayout、curSln等变量，就需要将这些变量定义为全局变量。

检查是否成功：即看是否

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

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

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

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

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

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] && // 这里虽然4个数字比较是否相等
oldLayout[ curSln ][1] == oldLayout[ i ][1] && // 但总共才4个字节长，实际可以
oldLayout[ curSln ][2] == oldLayout[ i ][2] && // 通过一次4字节长数字比较替换
oldLayout[ curSln ][3] == oldLayout[ i ][3] && // 四次1字节长数字比较来优化
( ( i & 1 ) ? 1 : -1 ) == b ) // 保证过河后的方案之间比较，回来后的方案之间比较
// i&1等效于i%2，i&7等效于i%8，i&63等效于i%64
return true;
return false;
}
void 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++ ) // 初始化每次选择方案时的初始化方案为sln[0]
cur[ i ] = 0; // 由于cur是全局变量，在VC中，其已经被赋值为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 ) )
{
// 重新选择本次的方案
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[ curSln - 1 ][0] == 0 && oldLayout[ curSln - 1 ][1] == 0 &&
oldLayout[ curSln - 1 ][2] == 3 && oldLayout[ curSln - 1 ][3] == 3 ) );

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

　　上面数组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]所表现的语义不够强，代码可读性较差。下篇说明结构，并展示类型的意义——如何解释内存的值。

 2/2   首页 上一页 1 2