1.txt

1、 实验要求：用高级语言编写求自由距离的程序

#include <fstream>
#include <iostream>
#include <string>
#include "math.h"
#define INF 100
#define L 20
using namespace std;

int pow2(int num)	//求2的num次方
{	int r=1;
	for(int i=num;i>0;i--)
		r=r*2;
	return r;
};

int main()
{	
	int i,j,k,l;		//循环变量
	int n0=3,k0=1,t=2;
	int tmp=INF;
	cout<<"请依次输入n0,k0,t的值."<<endl;
	cout<<"n0=";
	cin>>n0;
	cout<<"k0=";
	cin>>k0;
	cout<<"t=";
	cin>>t;
	int M=pow2(k0);					//2的k0次方
	int N=pow2(k0*t);				//2的k0*t次方
	int **status_pre=new int*[N];	//网格图中每一个状态对就的前一个状态
	int **tran_weight=new int*[N];	//网格图中每一个状态对就的前一个状态转移到该状态的码字重量
	for(i=0; i<N;i++)			//建立网格图
	{	status_pre[i]=new int[M];
		tran_weight[i]=new int[M];
		for(j=0;j<M;j++)
		{	
			cout<<"请输入能够转移到S"<<i<<"第"<<j+1<<"个状态的状态号:";
			cin>>status_pre[i][j];
			cout<<endl;
			cout<<"请输入由S"<<status_pre[i][j]<<"转移到S"<<i<<"所对应的码字重量:";
			cin>>tran_weight[i][j];
			cout<<endl;
		}
	}
	/*int status_pre[4][2]={{0,1},{2,3},{0,1},{2,3}};
	int tran_weight[4][2]={{0,1},{2,1},{3,2},{1,2}};*/
	int *d=new int[N];				//用于存储运算中经l步到达第i个状态的最轻路由重量
	int *d_tmp=new int[N];			//用于存储运算中经l-1步到达第i个状态的最轻路由重量
	int **pre=new int *[N];			//用于存储运算中经l步到达第i个状态的最轻路由对应的前一个状态						
	for(i=0;i<N;i++)				//对d[]进行初始化并开辟路由的存储空间
	{	d[i]=INF;
		pre[i]=new int[L];
	}
	d[0]=0;	
	l=1;							//从第一步开始
	int mid;
	while(1)
	{	for(i=0;i<N;i++)			//将上一步计算出来的结束暂存于d_tmp
		{	d_tmp[i]=d[i];
		}
		for(i=0;i<N;i++)
		{	tmp=INF;
			for(j=0;j<M;j++)
			{	mid=d_tmp[status_pre[i][j]]+tran_weight[i][j];
				if(mid<tmp && mid>0)
				{	tmp=mid;
					pre[i][l]=status_pre[i][j];	//记录实现此最轻路由的前一状态
				}
			}
			d[i]=tmp;
		}
		k=1;
		while(d[k]>=d[0] && k<N)		//检查结束条件(d[0]小于其它任何值)
		{	k++;
		}
		if(k>=N) break;
		l++;
	}
	cout<<"自由距离为"<<d[0]<<endl;		//输出计算机搜索结果
	cout<<"对应的路径为S0";
	tmp=0;
	while(l)
	{	cout<<"<--S"<<pre[tmp][l];
		tmp=pre[tmp][l];
		l--;
	}
	delete [] status_pre;
	delete [] tran_weight;
	delete [] d;
	delete [] d_tmp;
	delete [] pre;
	system("pause");
	return 0;
}