Demo entry 6360172

Poisson Problem

   

Submitted by anonymous on May 01, 2017 at 05:45
Language: C++. Code size: 4.0 kB.

//
#include "stdafx.h"
#include <iostream>
#include<string.h>
#include<malloc.h>

#define N 3          //酒杯数
#define MAX_SIZES 10000  //状态表中的最大状态数

typedef  struct node    //边节点
{
	int adjvex;//邻接点的位置
	node *next;//指向下一个节点
}ARCNODE;//邻接表中的结点类型

typedef struct   //顶点节点
{
	int vexdata[N];        //各酒杯的存储状态
	ARCNODE *next;//指向下一个邻接点
}VEXNODE;//表头结点类型

int A[MAX_SIZES];//用于存储路径的数组
int  top = 0;//数组中的个数

int full[N];//各酒杯的最大容量
int part[N];//各酒杯的当前容量
int end[N];//最终状态

VEXNODE s[MAX_SIZES];  //状态表
int sta;//状态表当前状态数
int dis = 0; //遍历路径的长度
int sum = 0;//所有解的个数
int end_vex;//结束的状态点
bool visited[MAX_SIZES];//标记状态是否被访问  

bool compare(int a[], int b[])   //比较状态
{
	int i;
	for (i = 0; i<N; i++)
		if (a[i] != b[i])
			return true;//两数组不相等,返回true

	return false;//相等,返回false
}

void save(int number)
{   //保存状态,如果状态存在则仅仅加入邻接表,如果不存在则加入状态表,并加入邻接表
	ARCNODE *p;
	int i;
	for (i = 0; i <= sta; i++)
	{
		if (!compare(part, s[i].vexdata))
			break;//该状态存在,跳出for循环
	}

	if (i>sta)//将该状态加入状态表
	{
		sta++;
		for (int j = 0; j<N; j++)
			s[sta].vexdata[j] = part[j];
		s[sta].next = NULL;
		if (!compare(part, end))
			end_vex = sta;//该状态是最终状态,记住在状态表中的位置

	}

	p = new ARCNODE;
	p->adjvex = i;
	p->next = s[number].next;
	s[number].next = p;//加入邻接表
}

void jisuan(int number)//求出某状态的所有邻接点
{
	int i, j, I, J;
	for (i = 0; i<N; i++)//编号为i的酒杯与其他酒杯交换
	{

		for (j = 0; j<N; j++)
		{
			if (j == i)     continue;//同一酒杯,无法变换
			I = part[i];//保存i酒杯的当前的容量
			J = full[j] - part[j];//j酒杯的空闲量

			if (I <= J)//若i酒杯的当前容量小于等于j酒杯的空闲量
			{
				part[i] = 0;
				part[j] += I;//将i酒杯的酒倒向j酒杯
				save(number);//调用save()函数,保存当前的状态
				part[i] = I;
				part[j] -= I;//恢复各酒杯的原始状态
			}
			else//若i酒杯的当前容量大于j酒杯的空闲量
			{
				part[i] -= J;
				part[j] = full[j];//把j酒杯加满
				save(number);//调用save()函数,保存当前的状态
				part[i] += J;
				part[j] -= J;//恢复各酒杯的原始状态
			}
		}
	}
}


void create()//建立状态的函数
{
	int number, i;
	printf("输入各个酒杯的容积:");
	for (i = 0; i<N; i++)
		scanf_s("%d", &full[i]);
	printf("输入对应酒杯的起始状态:");
	for (i = 0; i<N; i++)
		scanf_s("%d", &s[0].vexdata[i]);//初始状态即状态表中的s[0]

	printf("输入对应酒杯的最终状态:");
	for (i = 0; i<N; i++)
		scanf_s("%d", &end[i]);//所求的状态
	number = 0; sta = 0;
	s[0].next = NULL;

	while (number <= sta)
	{
		for (i = 0; i<N; i++)
			part[i] = s[number].vexdata[i];//将s[number]的状态赋给各酒杯当前的容量
		jisuan(number);//调用jisuan(),求出该状态所有的邻接点
		number++;
	}

	for (number = 0; number <= sta; number++)
		visited[number] = false;
}

void prtf()   //输出路径
{
	int i, j, k;
	printf("方案%d:\n", sum);
	for (i = 0; i<top; i++)
	{
		printf(" ");
		j = A[i];//路径中的位置
		for (k = 0; k<N; k++)
			printf("%d,", s[j].vexdata[k]);//输出该状态
		printf(" ");
	}
	printf("\n");
}

void stat()   //长度统计函数
{ 
	int *array = 0, num, i;
	num = sum;
	array = (int*)malloc(sizeof(int)*num);
	if (array == 0)
	{
		printf("out of memory,press any key to quit...\n");
		exit(0);             // 终止程序运行,返回操作系统   
	}
	//由遍历函数输入路径数据
	for (i = 0; i < num; i++)
	{
		array[i] = dis;
	}
	free(array);        // 释放由malloc函数申请的内存块   
}
void dfs(int v0)//深度优先搜索遍历函数
{
	if (!visited[v0])//判断该状态是否被访问过
	{
		dis = dis + 1;
		if (v0 == end_vex)//判断该状态是否是最终状态
		{
			sum++;
			prtf();//调用输出函数
			printf("路径长度为 %d\n", dis);
			dis = 0; 
		}
		else//若不是,深度搜索
		{
			ARCNODE *p;
			p = s[v0].next;
			visited[v0] = true;//标记该状态已访问
			while (p)
			{
				A[top++] = p->adjvex;   //记录路径
				dfs(p->adjvex);//递归调用遍历函数
				A[--top];//清空路径
				p = p->next;
			}
			visited[v0] = false;//标记该状态未访问,用于其它路径中访问
		}
	}
}

void findpath()
{
	A[top++] = 0;         //选择深度搜索遍历的起点
	dfs(0);           //进行深度搜索遍历
}
void main()
{
	int i, k;
	create();        //建立模型的状态
	printf("状态表中的%d种状态:\n", sta + 1);
	for (i = 0; i <= sta; i++)
	{
		for (k = 0; k<N; k++)
			printf("%d,", s[i].vexdata[k]);
		printf("\t");
	}
	printf("\n共得到如下解法:\n");
	findpath();              //输出得到的解
	system("pause");

}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).