您现在的位置是:首页 > 正文

三人三鬼过河问题

2024-01-30 23:23:20阅读 0

三人三鬼过河问题:

三个人和三个鬼在河边,都想要到河的对岸去;河边有一只船,只能搭载两个人、或者两个鬼、或者一人一鬼;如果在岸上或者在船上,鬼的数目多于人的数目,鬼就会把人吃掉。
怎样安排人和鬼的组合上船过河,才能使三个人和三个鬼都安全到河的对岸去呢?

程序思路:

人鬼过河问题实际上可以考虑为状态之间的迁移,或者是构建一个有向图,然后在图中寻找可行的路径。

我们把当前岸边作为左岸,河的对岸作为右岸。

那么状态包含两个因素,一个是左岸上人鬼的数量(右岸人鬼的数量可以由左岸人鬼数量计算得出),另一个是船在左岸还是在右岸。

迁移表现为从人鬼从左岸渡船到右岸,或者人鬼从右岸渡船到左岸。

因为鬼多于人的时候会吃人,所以不是任意的人和鬼的数量的组合都是合理的状态。

程序中首先找到所有合理的状态,然后再找到所有状态到状态可行的迁移,最后深度搜索所有迁移,寻找到从开始状态到结束状态间的可行路径。

程序的输出也是按照这个步骤,分成了三个部分,分别是可行状态、可行迁移,可行路径。

H-human人

G-ghost鬼

B-boat船

LB-left boat船在左边

RB-right boat船在右边

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LBOAT '*'
#define RBOAT ' '

typedef struct HGB_struct
{
	int H;
	int G;
	int B;
} HGB;

int ARR_LEN;

int state_count;
HGB *state; //[ARR_LEN];
int *transfer; // [ARR_LEN][ARR_LEN];

int stack_sp;
HGB *stack; // [ARR_LEN];

#define transfer_ref(i, j) (transfer[i * ARR_LEN + j])

#define stack_init() (stack_sp = 0)
#define stack_push(hgb) (stack[stack_sp++] = (hgb))
#define stack_pop() (stack[--stack_sp])
#define stack_top(hgb) (stack[stack_sp - 1])
#define stack_find(hgb, result) for(result = stack_sp - 1; result >= 0; result--) { if(stack[result].H == hgb.H && stack[result].G == hgb.G && stack[result].B == hgb.B) break; }

#define state_find(hgb, result) for(result = state_count - 1; result >= 0; result--) { if(state[result].H == hgb.H && state[result].G == hgb.G && state[result].B == hgb.B) break; }

int search(HGB hgb, int n)
{
	int i, index;
	int found;

	if((hgb.H == 0) && (hgb.G == 0) && (hgb.B == RBOAT))
	{
		stack_push(hgb);

		printf("=======================================================================================================\n");
		for(i = 0; i < stack_sp; i++)
			printf("H%dG%d[%c] ", stack[i].H, stack[i].G, stack[i].B);
		printf("\n");

		printf("-------------------------------------------------------------------------------------------------------\n");
		printf( "H%dG%d             H%dG%d\n",
			stack[0].H, stack[0].G,
			n - stack[0].H, n - stack[0].G);

		for(i = 0; i < stack_sp - 1; i++)
		{

			if(i % 2)
			{
				printf( "       <-H%dG%d--\n"
					"H%dG%d             H%dG%d\n",
					stack[i + 1].H - stack[i].H, stack[i + 1].G - stack[i].G,
					stack[i + 1].H, stack[i + 1].G,
					n - stack[i + 1].H, n - stack[i + 1].G);
			}
			else
			{
				printf( "       --H%dG%d->\n"
					"H%dG%d             H%dG%d\n",
					stack[i].H - stack[i + 1].H, stack[i].G - stack[i + 1].G,
					stack[i + 1].H, stack[i + 1].G,
					n - stack[i + 1].H, n - stack[i + 1].G);
			}

		}
		printf("=======================================================================================================\n");

		stack_pop();

		return -1;
	}
	else
	{
		stack_find(hgb, index);
		if(index >= 0)
		{
			return 0;
		}

		state_find(hgb, index);

		stack_push(hgb);

		for(i = 0; i < state_count; i++)
		{
			if(transfer_ref(index, i))
			{
				search(state[i], n);
			}
		}

		stack_pop();

		return 0;
	}
}

void human_ghost(int human_ghost_count, int boat_capacity)
{
	int i, j;
	int HL, GL, HR, GR;
	int tmp;
	int result;

	stack = NULL; // [ARR_LEN];
	state = NULL; //[ARR_LEN];
	transfer = NULL; // [ARR_LEN][ARR_LEN];
	ARR_LEN = (2 * (human_ghost_count + 1) * (human_ghost_count + 1));

	do
	{
		state = (HGB *)malloc(ARR_LEN * sizeof(HGB));
		if(state == NULL) break;

		stack = (HGB *)malloc(ARR_LEN * sizeof(HGB));
		if(stack == NULL) break;

		transfer = (int *)malloc(ARR_LEN * ARR_LEN * sizeof(int));
		if(transfer == NULL) break;

		printf("human_ghost:%d boat_capacity:%d\n", human_ghost_count, boat_capacity);

		state_count = 0;
		for(i = 0; i < (human_ghost_count + 1) * (human_ghost_count + 1); i++)
		{
			HR = i / (human_ghost_count + 1);
			GR = i % (human_ghost_count + 1);
			HL = human_ghost_count - HR;
			GL = human_ghost_count - GR;

			if((HL > 0) && (HL < GL)) continue;
			if((HR > 0) && (HR < GR)) continue;

			printf("H%dG%d:H%dG%d L\n", HL, GL, HR, GR);
			printf("H%dG%d:H%dG%d R\n", HL, GL, HR, GR);

			state[state_count].H = HL;
			state[state_count].G = GL;
			state[state_count].B = LBOAT;
			state_count++;
			state[state_count].H = HL;
			state[state_count].G = GL;
			state[state_count].B = RBOAT;
			state_count++;
		}

		printf("         ");
		for(j = 0; j < state_count; j++)
		{
			printf("H%dG%d[%c] ", state[j].H, state[j].G, state[j].B);
		}
		printf("\n");

		for(i = 0; i < state_count; i++)
		{
			printf("H%dG%d[%c] |", state[i].H, state[i].G, state[i].B);

			for(j = 0; j < state_count; j++)
			{
				transfer_ref(i, j) = 1;

				if(state[i].B == LBOAT)
				{
					if(state[j].B == LBOAT) transfer_ref(i, j) = 0;

					if(state[i].H < state[j].H) transfer_ref(i, j) = 0;

					if(state[i].G < state[j].G) transfer_ref(i, j) = 0;

					tmp = (state[i].H + state[i].G) - (state[j].H + state[j].G);
					if(tmp <= 0 || tmp > boat_capacity) transfer_ref(i, j) = 0;
				}
				else
				{
					if(state[j].B == RBOAT) transfer_ref(i, j) = 0;

					if(state[i].H > state[j].H) transfer_ref(i, j) = 0;

					if(state[i].G > state[j].G) transfer_ref(i, j) = 0;

					tmp = (state[j].H + state[j].G) - (state[i].H + state[i].G);
					if(tmp <= 0 || tmp > boat_capacity) transfer_ref(i, j) = 0;
				}

				if(transfer_ref(i, j))
				{
					printf(" H%dG%d%c |", state[j].H, state[j].G, state[j].B);
				}
				else
				{
					printf("       |");
				}
			}

			printf("\n");
		}

		stack_init();
		search(state[0], human_ghost_count);

	} while(0);

	if(stack) free(stack);
	if(state) free(state);
	if(transfer) free(transfer);
}

int main(int argc, char *argv[])
{
	int human_ghost_count = 0;
	int boat_capacity = 0;

	human_ghost(3, 2);

	return 0;
}

程序的输出结果:

human_ghost:3 boat_capacity:2
H3G3:H0G0 L
H3G3:H0G0 R
H3G2:H0G1 L
H3G2:H0G1 R
H3G1:H0G2 L
H3G1:H0G2 R
H3G0:H0G3 L
H3G0:H0G3 R
H2G2:H1G1 L
H2G2:H1G1 R
H1G1:H2G2 L
H1G1:H2G2 R
H0G3:H3G0 L
H0G3:H3G0 R
H0G2:H3G1 L
H0G2:H3G1 R
H0G1:H3G2 L
H0G1:H3G2 R
H0G0:H3G3 L
H0G0:H3G3 R
         H3G3[*] H3G3[ ] H3G2[*] H3G2[ ] H3G1[*] H3G1[ ] H3G0[*] H3G0[ ] H2G2[*] H2G2[ ] H1G1[*] H1G1[ ] H0G3[*] H0G3[ ] H0G2[*] H0G2[ ] H0G1[*] H0G1[ ] H0G0[*] H0G0[ ] 
H3G3[*] |       |       |       | H3G2  |       | H3G1  |       |       |       | H2G2  |       |       |       |       |       |       |       |       |       |       |
H3G3[ ] |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |
H3G2[*] |       |       |       |       |       | H3G1  |       | H3G0  |       | H2G2  |       |       |       |       |       |       |       |       |       |       |
H3G2[ ] | H3G3* |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |
H3G1[*] |       |       |       |       |       |       |       | H3G0  |       |       |       | H1G1  |       |       |       |       |       |       |       |       |
H3G1[ ] | H3G3* |       | H3G2* |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |
H3G0[*] |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |
H3G0[ ] |       |       | H3G2* |       | H3G1* |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |
H2G2[*] |       |       |       |       |       |       |       |       |       |       |       | H1G1  |       |       |       | H0G2  |       |       |       |       |
H2G2[ ] | H3G3* |       | H3G2* |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |
H1G1[*] |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       | H0G1  |       | H0G0  |
H1G1[ ] |       |       |       |       | H3G1* |       |       |       | H2G2* |       |       |       |       |       |       |       |       |       |       |       |
H0G3[*] |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       | H0G2  |       | H0G1  |       |       |
H0G3[ ] |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |
H0G2[*] |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       | H0G1  |       | H0G0  |
H0G2[ ] |       |       |       |       |       |       |       |       | H2G2* |       |       |       | H0G3* |       |       |       |       |       |       |       |
H0G1[*] |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       | H0G0  |
H0G1[ ] |       |       |       |       |       |       |       |       |       |       | H1G1* |       | H0G3* |       | H0G2* |       |       |       |       |       |
H0G0[*] |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |       |
H0G0[ ] |       |       |       |       |       |       |       |       |       |       | H1G1* |       |       |       | H0G2* |       | H0G1* |       |       |       |
=======================================================================================================
H3G3[*] H3G1[ ] H3G2[*] H3G0[ ] H3G1[*] H1G1[ ] H2G2[*] H0G2[ ] H0G3[*] H0G1[ ] H1G1[*] H0G0[ ] 
-------------------------------------------------------------------------------------------------------
H3G3             H0G0
       --H0G2->
H3G1             H0G2
       <-H0G1--
H3G2             H0G1
       --H0G2->
H3G0             H0G3
       <-H0G1--
H3G1             H0G2
       --H2G0->
H1G1             H2G2
       <-H1G1--
H2G2             H1G1
       --H2G0->
H0G2             H3G1
       <-H0G1--
H0G3             H3G0
       --H0G2->
H0G1             H3G2
       <-H1G0--
H1G1             H2G2
       --H1G1->
H0G0             H3G3
=======================================================================================================
=======================================================================================================
H3G3[*] H3G1[ ] H3G2[*] H3G0[ ] H3G1[*] H1G1[ ] H2G2[*] H0G2[ ] H0G3[*] H0G1[ ] H0G2[*] H0G0[ ] 
-------------------------------------------------------------------------------------------------------
H3G3             H0G0
       --H0G2->
H3G1             H0G2
       <-H0G1--
H3G2             H0G1
       --H0G2->
H3G0             H0G3
       <-H0G1--
H3G1             H0G2
       --H2G0->
H1G1             H2G2
       <-H1G1--
H2G2             H1G1
       --H2G0->
H0G2             H3G1
       <-H0G1--
H0G3             H3G0
       --H0G2->
H0G1             H3G2
       <-H0G1--
H0G2             H3G1
       --H0G2->
H0G0             H3G3
=======================================================================================================
=======================================================================================================
H3G3[*] H2G2[ ] H3G2[*] H3G0[ ] H3G1[*] H1G1[ ] H2G2[*] H0G2[ ] H0G3[*] H0G1[ ] H1G1[*] H0G0[ ] 
-------------------------------------------------------------------------------------------------------
H3G3             H0G0
       --H1G1->
H2G2             H1G1
       <-H1G0--
H3G2             H0G1
       --H0G2->
H3G0             H0G3
       <-H0G1--
H3G1             H0G2
       --H2G0->
H1G1             H2G2
       <-H1G1--
H2G2             H1G1
       --H2G0->
H0G2             H3G1
       <-H0G1--
H0G3             H3G0
       --H0G2->
H0G1             H3G2
       <-H1G0--
H1G1             H2G2
       --H1G1->
H0G0             H3G3
=======================================================================================================
=======================================================================================================
H3G3[*] H2G2[ ] H3G2[*] H3G0[ ] H3G1[*] H1G1[ ] H2G2[*] H0G2[ ] H0G3[*] H0G1[ ] H0G2[*] H0G0[ ] 
-------------------------------------------------------------------------------------------------------
H3G3             H0G0
       --H1G1->
H2G2             H1G1
       <-H1G0--
H3G2             H0G1
       --H0G2->
H3G0             H0G3
       <-H0G1--
H3G1             H0G2
       --H2G0->
H1G1             H2G2
       <-H1G1--
H2G2             H1G1
       --H2G0->
H0G2             H3G1
       <-H0G1--
H0G3             H3G0
       --H0G2->
H0G1             H3G2
       <-H0G1--
H0G2             H3G1
       --H0G2->
H0G0             H3G3
=======================================================================================================

网站文章

  • RSA公钥/私钥/签名工具包

    package com.example.demo.utils;import org.apache.commons.codec.binary.Base64;import org.springframew...

    2024-01-30 23:22:49
  • 软件项目的开发的时间视乎永远都不够用

    从大学毕业到现在已经5年了,在这5年的时间里一直没有离开过软件行业,也一直在做ERP系统的开发,设计和管理工作。 在此期间经历了3家公司包括现在这家,这3家公司性质各不相同,第一家是日企,第二家是国内私人企业,现在所在的这家是一家新加坡企业。虽然企业的文化及背景差异很大,但是对于我们这些IT从业者来说,感觉在项目工作上的时间总是被压的很紧。...

    2024-01-30 23:22:42
  • 浅谈-计算机加电后的启动过程(一)

    加载BIOS 当PC的电源打开后, 80x86结构的CPU将自动进入实模式.并且CPU的 cs:ip 寄存器被强制初始化为 0xF0000 : 0xFFF0. 先抛出来个问题, 为什么 cs:ip 寄...

    2024-01-30 23:22:35
  • BI低代码数字化应用搭建平台

    BI低代码数字化应用搭建平台

    易搭可以集成企业的各类数据源,高效打通企业分散的数据,结合业务场景,通过可视化的数据建模加工、报表制作与数据分析功能,敏捷开发出各类领导驾驶舱、复杂固定报表,统一用户权限管控,打造企业级的数据分析平台或数据中台,实现业务数据化、管理数字化。

    2024-01-30 23:22:25
  • 电脑怎么连接手机wifi

    1、首先打开手机,点击打开设置中的“其他无线连接”。 2、然后在弹出来的窗口中点击打开个人热点中的“开启个人热点”后面的开关。 3、然后打开电脑,点击打开右下角WiFi图标。 4、然后在弹出来的窗口中点击想要连接到WiFi下方的“连接”即可。

    2024-01-30 23:21:57
  • 自定义表单

    这种方法相当于将数据库表的一行保存一条数据记录,调整为多行保存一条数据记录,每一行对应一个表单字段,在后端接口开发上需要作出相应的调整,缺点依然是查询数据和统计分析都不太方便。经常有很多VForm的用...

    2024-01-30 23:21:49
  • Spring Transaction学习笔记--编程式事物声明

    一、编程式事物流程 二、编程式事物例子 一、编程式事物流程 编程式事物实现主要有两种方法,一种是使用TransactionTemplate,另一中就是使用PlatformTransactionManager.这里我主要介绍前者的使用方式。 1、 准备jdbc.properties配置数据库需要的信息,将配置属性注入com.mchange.v2.c3p0.ComboPo...

    2024-01-30 23:21:41
  • 微软手机停止服务器,黯然退场!微软手机操作系统停更 比尔·盖茨多次痛惜错过机会...

    微软手机停止服务器,黯然退场!微软手机操作系统停更 比尔·盖茨多次痛惜错过机会...

    图为无关微软的移动操作系统停更了。微软正式宣布,12月10日起,将停止对Windows 10 Mobile最新版本的支持。Windows phone仍然可以运行,但运行最后官方支持的Windows 1...

    2024-01-30 23:21:11
  • 进制转换(java实现)

    405. 数字转换为十六进制数 StringBuilder 要求返回字符串,使用StringBuilder。StringBuilder是线程不安全的,但是相对于StringBuffer速度较快,虽然S...

    2024-01-30 23:21:04
  • 判断一棵树是否为平衡二叉树

    平衡二叉树即为树中任意节点的左右两子树高度差不超过1struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int a) :val(a), left(NULL), right(NULL) {};};struct rType { bool isBalanced; int height; rType...

    2024-01-30 23:20:57