#include?
#include?
#include?
#include?
#define?N?200
#define?MaxVertices?100?//假設(shè)包含100個(gè)頂點(diǎn)
#define?MaxWeight?32767?//不鄰接時(shí)為32767，但輸出時(shí)用?“∞“
#define?MAXV?10
#define?INF?32767
using?namespace?std;
typedef?struct{?//包含權(quán)的鄰接矩陣的的定義
????int?Vertices[MaxVertices];??//頂點(diǎn)信息的數(shù)組
????int?Edge[MaxVertices][MaxVertices];?//邊的權(quán)信息的數(shù)組
????int?numV;?//當(dāng)前的頂點(diǎn)數(shù)
????int?numE;?//當(dāng)前的邊數(shù)
}AdjMatrix;


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

void?menu（）//主菜單?
{	
//標(biāo)題頭?
	cout<<“				-----------------------------------------------------				“<	cout<<“?????????????					《算法設(shè)計(jì)與分析》實(shí)驗(yàn)“<	cout<<“				-----------------------------------------------------“<//選擇菜單
	cout<<“				??1.算法分析基礎(chǔ)——Fibonacci序列問(wèn)題“?<	cout<<“				??2.分治法在數(shù)值問(wèn)題中的應(yīng)用——矩陣相乘問(wèn)題?“<	cout<<“				??3.減治法在數(shù)值問(wèn)題中的應(yīng)用——8枚硬幣問(wèn)題?“<	cout<<“				??4.變治法在數(shù)值問(wèn)題中的應(yīng)用——堆排序問(wèn)題?“<	cout<<“				??5.動(dòng)態(tài)規(guī)劃法在圖問(wèn)題中的應(yīng)用——全源最短路徑問(wèn)題?“<	cout<<“				??99.退出本實(shí)驗(yàn)“?<	cout<<“				-----------------------------------------------------“<	cout<<“				??請(qǐng)輸入您所要執(zhí)行的操作（1234599）；“<	
}

//Fibonacci算法實(shí)現(xiàn)階段?
//Fibonacci數(shù)列
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計(jì)算機(jī)所能計(jì)算的最大整數(shù)是第%d個(gè)fibonacci整數(shù)。\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計(jì)算機(jī)所能表示的最大fibonacci整數(shù)是第%d個(gè)fibonacci整數(shù)。\n“i）;
}

void?fibonacci（）
{
	double?start;
	start=clock（）;
	Fib（）;
	printf（“\t迭代所用時(shí)間是%lf?\n\n“clock（）-start）;
	start=clock（）;
	Fn（）;
	printf（“\t遞歸所用時(shí)間是%lf?\n\n“clock（）-start）;
}



//矩陣相乘問(wèn)題求解?
void?PrintIn（Array?AArray?B）
{
	int?n=A.n;
	int?ij;
	printf（“請(qǐng)輸入A數(shù)據(jù)：\n“）;
	for（i=0;i?????????for（j=0;j			?cin>>A.a[i*n+j];
????printf（“請(qǐng)輸入B數(shù)據(jù)：\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