main.cpp

我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:递归,分治,动态规划,回溯法,AO算法等,除此之外还用到比较多的数学知识,我做了一部分,还有一些暂时还没做出来,大家也帮

/*******************************************************************************
53. (工作安排问题) 现有 N (N≤8) 件工作, 分别由 N 个人完成, 每人都完成一
 件,且只完成一件, 每人完成不同工作的时间不同. 试设计一种分配工作方案, 使
 完成 N 件工作所需的总时间最少.
    原始数据由文本文件 EXAM1.TXT 给出, 其格式如下:
    第 1 行:        工作任务数(N)
    第 2 -- N+1 行: 第 i+1 行为第 i 个人完成各件工作所需的时间. 以上各数
 均为不超过 1000 的正整数.
    计算结果可直接在屏幕上输出: 第一行为工作分配方案, 共 N 组, 每组数据的
 形式为 a-b, 其中 a 为工作人员编号, b 为他应完成的工作序号.
    例: 设 EXAM1.TXT 的数据为:
         4
         2  15  13  4
         10  4  14  15
         9  14  16  13
         7  8  11  9
     对此, 一个正确的输出可以是
         1-4, 2-2, 3-1, 4-3
         TOTAL=28
*********************************************************************************/

#include <stdio.h>
#include <malloc.h>

//数组大小
int n;
//数组
int** arr;
//排列数组
int* a;
//最小消耗
int min_cost;
//结果
int* result;

//保存对应结果
void synrs()
{
	int i;
	for(i=0; i<n; i++)
		result[i]=a[i];
}

//生成所有排列,对每个排列计算比较,获得最小值
void perm(int m)
{
	static int flag=0;
	if(m==n)
	{
		//process
		int sum=0;
		for(int i=0;i<n;i++)
		{
			sum+=arr[i][a[i]];
		}
		if(flag==0)
		{
			flag=1;
			min_cost=sum;
			synrs();
		}
		else
		{
			if(min_cost>sum)
			{
				min_cost=sum;
				synrs();
			}
		}
	}
	else
	{
		int i;
		for(i=m; i<n; i++)
		{
			int temp;
			temp=a[m];
			a[m]=a[i];
			a[i]=temp;
			perm(m+1);
			temp=a[m];
			a[m]=a[i];
			a[i]=temp;
		}
	}
}

//输出结果
void output()
{
	int i;
	for(i=0; i<n; i++)
	{
		printf("%d---%d ",i,result[i]);
	}
	printf("\n");
	printf("%d\n",min_cost);
}

void main()
{
	int i,j;
	FILE* fp;

	//打开文件
	fp = fopen("EXAM1.TXT","r");
	//读取n
	fscanf(fp,"%d",&n);

	//申请空间
	result=(int*)malloc(n*sizeof(int));
	a=(int*)malloc(n*sizeof(int));
	for(i=0;i<n;i++)
		a[i]=i;
	arr=(int**)malloc(n*sizeof(int*));
	for(i=0;i<n;i++)
	{
		arr[i]=(int*)malloc(n*sizeof(int));
	}
	//读取数据
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			fscanf(fp,"%d",&arr[i][j]);
	}
	//计算
	perm(0);
	//输出
	output();

	//关闭文件
	fclose(fp);
	//释放空间
	free(a);
	free(result);
	for(i=0; i<n; i++)
		free(arr[i]);
	free(arr);
}