对农夫过河问题的完善对农夫过河问题的完善
农夫过河问题的完善，能打印出两条可能的路径
程序代码如下，在VC上调试通过，可以直接复制运行，并对代码段进行了说明
#include
#include
#define MAXNUM 20
typedef int DataType;
struct SeqQueue /* 顺序队列类型定义 */
{
int f, r;
DataType q[MAXNUM];
};
typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */ ...
对农夫过河问题的完善
农夫过河问题的完善，能打印出两条可能的路径
程序代码如下，在VC上调试通过，可以直接复制运行，并对代码段进行了说明
#include
#include
#define MAXNUM 20
typedef int DataType;
struct SeqQueue /* 顺序队列类型定义 */
{
int f, r;
DataType q[MAXNUM];
};
typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */
PSeqQueue createEmptyQueue_seq(void) {
PSeqQueue paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
if (paqu == NULL)
printf("Out of space!\n");
else
paqu->f = paqu->r = 0;
return (paqu);
}
int isEmptyQueue_seq( PSeqQueue paqu ) /*判断paqu所指是否是空队列*/ {
return paqu->f == paqu->r; }
void enQueue_seq(PSeqQueue paqu, DataType x) /* 在队列中插入一元素x */ {
if ((paqu->r + 1) % MAXNUM == paqu->f)
printf("Full queue.\n");
else
{
paqu->q[paqu->r] = x;
paqu->r = (paqu->r + 1) % MAXNUM;
}
}
void deQueue_seq(PSeqQueue paqu) /* 删除队列头部元素 */ {
if( paqu->f == paqu->r )
printf( "Empty Queue.\n" );
else
paqu->f = (paqu->f + 1) % MAXNUM; }
DataType frontQueue_seq( PSeqQueue paqu ) /* 对非空队列,求队列头部元素 */ {
return (paqu->q[paqu->f]); }
int farmer(int location) /*判断农夫位置*/
{
return 0 != (location & 0x08); }
int wolf(int location) /*判断狼位置*/
{
return 0 != (location & 0x04); }
int cabbage(int location) /*判断白菜位置*/
{
return 0 != (location & 0x02); }
int goat(int location) /*判断羊的位置*/
{
return 0 !=(location & 0x01); }
int safe(int location) /* 若状态安全则返回true */
{
if ((goat(location) == cabbage(location)) && (goat(location) != farmer(location)) )
return 0;
if ((goat(location) == wolf(location)) && (goat(location) != farmer(location)))
return 0;
return 1; /* 其他状态是安全的 */
}
void farmerProblem1( )
{
int movers, i, location, newlocation;
int route[16]; /*记录已考虑的状态路径*/
PSeqQueue moveTo;
moveTo = createEmptyQueue_seq( );
enQueue_seq(moveTo, 0x00);
for (i = 0; i < 16; i++) route[i] = -1;
route[0]=0;
while (!isEmptyQueue_seq(moveTo)&&(route[15] == -1))
{
location = frontQueue_seq(moveTo);
deQueue_seq(moveTo);
for (movers = 8; movers >= 1; movers >>= 1)
{
if ((0 != (location & 0x08)) == (0 != (location & movers)))
{
newlocation = location^(0x08|movers);
if (safe(newlocation) && (route[newlocation] == -1))
{
route[newlocation] = location;
enQueue_seq(moveTo, newlocation);
}
}
}
}
/* 打印出路径 */
if(route[15] != -1)
{
printf("The reverse path is : \n");
for(location = 15; location >= 0; location = route[location])
{
printf("The location is : %d\n",location);
if (location == 0) return;
}
}
else
printf("No solution.\n");
}
void farmerProblem2( )
{
int movers, i, location, newlocation;
int route[16]; /*记录已考虑的状态路径*/
PSeqQueue moveTo;
moveTo = createEmptyQueue_seq( );
enQueue_seq(moveTo, 0x00);
for (i = 0; i < 16; i++) route[i] = -1;
route[0]=0;
while (!isEmptyQueue_seq(moveTo)&&(route[15] == -1))
{
location = frontQueue_seq(moveTo);
deQueue_seq(moveTo);
for (movers = 1; movers <= 8; movers <<= 1)
{
if ((0 != (location & 0x08)) == (0 != (location & movers)))
{
newlocation = location^(0x08|movers);
if (safe(newlocation) && (route[newlocation] == -1))
{
route[newlocation] = location;
enQueue_seq(moveTo, newlocation);
}
}
}
}
/* 打印出路径 */
if(route[15] != -1)
{
printf("The reverse path is : \n");
for(location = 15; location >= 0; location = route[location])
{
printf("The location is : %d\n",location);
if (location == 0) return;
}
}
else
printf("No solution.\n");
}
int main() /*主函数*/
{
farmerProblem1();
farmerProblem2();
return 0;
}
本文档为【对农夫过河问题的完善】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483