C++入门教程，函数在C++中的作用（二）

检查是否成功：即看是否

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 ] 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 %d %d ",

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

有用  |  无用 取消

猜你喜欢