main.cpp

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

/********************************************************************************
 23. (覆盖问题) 有边长为Ｎ（Ｎ为偶数）的正方形，请你用Ｎ＾２／２个长为２,
 宽为１的长方形，将它全部覆盖。编程打印出所有覆盖方法。如：Ｎ＝４

    ┌─┬──┬─┐            ┌──┬──┐
    │  │    │  │ １２２４   │    │    │  １１２２
    │  ├──┤  │            ├──┼──┤
    │  │    │  │ １３３４   │    │    │  ３３４４
    ├─┼──┼─┤            ├──┼──┤
    │  │    │  │ ５６６８   │    │    │  ５５６６
    │  ├──┤  │            ├──┼──┤
    │  │    │  │ ５７７８   │    │    │  ７７８８
    └─┴──┴─┘            └──┴──┘
	分析:
	经过观察显然可知:
	找出一个没有被覆盖的1*1的方块,它可以与上,下,左,右相邻的1*1方块组成2*1的覆盖
	方块,而这样的几种情况是没有重复的,所以我们要完成所有的覆盖方法,就等于我们要完
	成这几种情况的覆盖方法,而这几种情况还是一个覆盖问题,所以,我采用分治算法解决!
*********************************************************************************/


#include <stdio.h>

#define N 4

typedef struct
{
	int x;
	int y;
	int d;//方向
} Block;

void Find(int k);
void Cover(int x, int y, int d, int k);

//四种基于某点的覆盖情况
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

//保存覆盖结果
Block blk[N*N/2];

//保存显示结果
int map[N][N];

//输出数据文件指针
FILE* fp;

//计数器
int counter = 0;

//输出显示结果到文件cover.txt
void output()
{
	int k;
	int x,y;
	//填充显示矩阵
	for(k=0; k<N*N/2; k++)
	{
		map[blk[k].y][blk[k].x] = k+1;
		map[blk[k].y+dy[blk[k].d]][blk[k].x+dx[blk[k].d]] = k+1;
	}
	//显示矩阵
	for(y=0; y<N; y++)
	{
		for(x=0; x<N; x++)
		{
			fprintf(fp,"%3d",map[y][x]);
		}
		fprintf(fp,"\n");
	}
	fprintf(fp,"\n");

}

//判断该块是否在覆盖范围内
int InArea(int x, int y)
{
	if(x<0)
		return 0;
	if(x>=N)
		return 0;
	if(y<0)
		return 0;
	if(y>=N)
		return 0;

	return 1;
}

//查找某一块是否有重叠
int Search(int x, int y, int k)
{
	int t,flag=0;
	for(t=0; t<k; t++)
	{
		if(x==blk[t].x && y==blk[t].y)
		{
			flag = 1;
			break;
		}
		if(x==blk[t].x+dx[blk[t].d] && y==blk[t].y+dy[blk[t].d])
		{
			flag = 1;
			break;
		}
	}
	return flag;
}

//找出一个没有被覆盖的1*1方块
void Find(int k)
{
	int x,y;
	for(y=0; y<N; y++)
	{
		for(x=0; x<N; x++)
		{
			if(!Search(x,y,k))
			{
				goto L;
			}
		}
	}
	//分治
L:	Cover(x,y,0,k);
	Cover(x,y,1,k);
	Cover(x,y,2,k);
	Cover(x,y,3,k);
}

//覆盖
void Cover(int x, int y, int d, int k)
{
	int tx,ty;
	tx = x+dx[d];
	ty = y+dy[d];
	if(!InArea(tx,ty) || Search(tx,ty,k))
		return;
	blk[k].x = x;
	blk[k].y = y;
	blk[k].d = d;

	if(k==N*N/2-1)//完成了
	{
		counter ++;
		//输出覆盖结果
		output();
	}
	else{//如果还没完成,继续查找
		Find(k+1);
	}
}

void main()
{
	fp = fopen("cover.txt","w");
	Find(0);
	fprintf(fp,"一共有%d种覆盖方法!",counter);
	fclose(fp);
}