算法分析与设计实验代码.cpp

1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下：
－－－－－－－－－－－－－－－－－－－－－－－－－
《算法设计与分析》实验
－－－－－－－－－－－－－－－－－－－－－－－－－
算法分析基础——Fibonacci序列问题
分治法在数值问题中的应用——矩阵相乘问题
减治法在组合问题中的应用——8枚硬币问题
变治法在排序问题中的应用——堆排序问题
动态规划法在图问题中的应用——全源最短路径问题
99. 退出本实验
－－－－－－－－－－－－－－－－－－－－－－－－－
请输入您所要执行的操作（1，2，3，4，5，99）：
2）点击操作后进入相应的实验项目或是相应项目的下一级菜单；
3）可以反复执行，直到退出实验。

#include 
#include 
#include 
#include 
#define N 200
#define MaxVertices 100 //假设包含100个顶点
#define MaxWeight 32767 //不邻接时为32767，但输出时用 “∞“
#define MAXV 10
#define INF 32767
using namespace std;
typedef struct{ //包含权的邻接矩阵的的定义
    int Vertices[MaxVertices];  //顶点信息的数组
    int Edge[MaxVertices][MaxVertices]; //边的权信息的数组
    int numV; //当前的顶点数
    int numE; //当前的边数
}AdjMatrix;


typedef struct array
{
	int *a;
	int n;
}Array;

void menu（）//主菜单 
{	
//标题头 
	cout<<“				-----------------------------------------------------				“<	cout<<“             					《算法设计与分析》实验“<	cout<<“				-----------------------------------------------------“<//选择菜单
	cout<<“				  1.算法分析基础——Fibonacci序列问题“ <	cout<<“				  2.分治法在数值问题中的应用——矩阵相乘问题 “<	cout<<“				  3.减治法在数值问题中的应用——8枚硬币问题 “<	cout<<“				  4.变治法在数值问题中的应用——堆排序问题 “<	cout<<“				  5.动态规划法在图问题中的应用——全源最短路径问题 “<	cout<<“				  99.退出本实验“ <	cout<<“				-----------------------------------------------------“<	cout<<“				  请输入您所要执行的操作（1234599）；“<	
}

//Fibonacci算法实现阶段 
//Fibonacci数列
int Fi（int i）
{
	if（i<=1）
		return i;
	else
		return Fi（i-1）+Fi（i-2）;
}

void Fn（）
{
	int i=0j=0;
	do
	{
		j=Fi（i）;
		if（j>=0）
			printf（“%d  “j）;
		++i;
	}while（j>=0）;
	printf（“\n计算机所能计算的最大整数是第%d个fibonacci整数。\n“i-1）;
}

void Fib（）
{ 
	int i=1f[3]={01};
	printf（“%d  \n“f[0]）;
	do
	{	
		printf（“%d  \n“f[1]）;
		f[2]=f[1]+f[0];
		f[0]=f[1];
		f[1]=f[2];
		i++;
	}while（f[1]>=f[0]）;
	printf（“\n\t计算机所能表示的最大fibonacci整数是第%d个fibonacci整数。\n“i）;
}

void fibonacci（）
{
	double start;
	start=clock（）;
	Fib（）;
	printf（“\t迭代所用时间是%lf \n\n“clock（）-start）;
	start=clock（）;
	Fn（）;
	printf（“\t递归所用时间是%lf \n\n“clock（）-start）;
}



//矩阵相乘问题求解 
void PrintIn（Array AArray B）
{
	int n=A.n;
	int ij;
	printf（“请输入A数据：\n“）;
	for（i=0;i         for（j=0;j			 cin>>A.a[i*n+j];
    printf（“请输入B数据：\n“）;
	for（i=0;i         for（j=0;j           cin>>B.a[i*n+j];
}

void RandomIn（Array AArray B）
{
	int n=A.n;
	srand（（unsigned）time（NULL））;
	int ij;
	for（i=0;i		for（j=0;j			A.a[i*n+j]=rand（）%10;
		
	for（i=0;i	   for（j=0;j		B.a[i*n+j]=rand（）%10;
}
void PrintOut（Array A）
{  
	int n=A.n;
	int ij;
	for（i=0;i	   { for（j=0;j		   cout<		 printf（“\n“）;	
	   }
}
void divide（Array dArray d00Array d01Array d10Array d11）  /*分割矩阵*/
{
	int n=d00.n;
   int ij;
   for（i=0;i   {
	   for（j=0;j	   {
		   d00.a[n*i+j]=d.a[2*n*i+j];
		   d01.a[n*i+j]=d.a[2*n*i+n+j];
		   d10.a[n*i+j]=d.a[2*n*n+2*n*i+j];
		   d11.a[n*i+j]=d.a[2*n*n+2*n*i+n+j];
	   }
   }
}
Array merge（Array d00Array d01Array d10Array d11）  
{
  int n=d00.n;
  int ij;
  Array d;
  d.a=（int *）malloc（sizeof（int）* （4*n*n））;
  for（i=0;i   {
	   for（j=0;j