main.cpp

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

/****************************************************************************
21. 请设计一个程序，由计算机把１..￣.８的八个自然数填入图中，使得横、
 竖、对角任何两个相邻的小方格中的两个数是不连续的。(下图右侧的 4 个图
 为禁止的情形).

            ┌─┐          ┌─┐               ┌─┐
            │  │          │４│               │８│
        ┌─┼─┼─┐      └─┼─┐       ┌─┼─┘
        │  │  │  │          │５│       │７│
        ├─┼─┼─┤          └─┘       └─┘
        │  │  │  │      ┌─┐
        └─┼─┼─┘      │６│           ┌─┬─┐
            │  │          ├─┤           │１│２│
            └─┘          │７│           └─┴─┘
			                └─┘ 

            ┌─┐                    
            │t2│                       
        ┌─┼─┼─┐     
        │t4│t0│t6│        
        ├─┼─┼─┤        
        │t7│t1│t5│      
        └─┼─┼─┘   
            │t3│          
            └─┘  

分析:采用剪枝回溯法
由于位置的特殊性,将空格按照如下次序搜索.
******************************************************************************/

#include <stdio.h>
#include <math.h>

//路径集合
static int *t[8];
int t0[] = {1,8,0};//由于位置的特殊性,这里只能放1,8
int t1[] = {1,8,0};//如上类推
int t2[] = {2,7,0};
int t3[] = {2,7,0};
int t4[] = {3,4,5,6,0};
int t5[] = {3,4,5,6,0};
int t6[] = {3,4,5,6,0};
int t7[] = {3,4,5,6,0};

//邻居表
static int *n[8];
int n0[] = {1,2,4,5,6,7,-1};
int n1[] = {0,3,4,5,6,7,-1};
int n2[] = {0,4,6,-1};
int n3[] = {1,5,7,-1};
int n4[] = {0,1,2,7,-1};
int n5[] = {0,1,3,6,-1};
int n6[] = {0,1,2,5,-1};
int n7[] = {0,1,3,4,-1};

//结果的形式
char res[] = "\
            ┌─┐\n\
            │%2d│\n\
        ┌─┼─┼─┐\n\
        │%2d│%2d│%2d│\n\
        ├─┼─┼─┤\n\
        │%2d│%2d│%2d│\n\
        └─┼─┼─┘\n\
            │%2d│\n\
            └─┘\n\
";

//保存路径
static int Path[8];

//检查合法性
int checked(int k)
{
	int i;
	for(i=0; n[k][i]!=-1; i++)
	{
		if( n[k][i] < k) 
		{
			//如果与邻居数相差1,(不符合)则返回0
			if(abs(t[k][Path[k]]-t[n[k][i]][Path[n[k][i]]]) == 1 )
				return 0;
		}
	}
	for(i=0; i<k; i++)
	{
		//如果与前面解有重复,(不符合)返回0
		if(t[k][Path[k]] == t[i][Path[i]])
			return 0;
	}
	//符合,返回1
	return 1;
}

//显示结果
void ShowRes()
{
	printf(res, t2[Path[2]],t4[Path[4]],
		t0[Path[0]],t6[Path[6]],t7[Path[7]],
		t1[Path[1]],t5[Path[5]],t3[Path[3]]);
}

//主函数
void main()
{
	int k;
	int flag = 0;

	t[0] = t0;
	t[1] = t1;
	t[2] = t2;
	t[3] = t3;
	t[4] = t4;
	t[5] = t5;
	t[6] = t6;
	t[7] = t7;

	n[0] = n0;
	n[1] = n1;
	n[2] = n2;
	n[3] = n3;
	n[4] = n4;
	n[5] = n5;
	n[6] = n6;
	n[7] = n7;

	for(k=0; k<8; k++)
		Path[k] = -1;

	k=0;

	while(k>=0)
	{
		while(t[k][++Path[k]]!=0)
		{
			if(checked(k) && k<7)
			{
				//部分解
				k++;
			}
			else if(checked(k) && k==7)
			{
				//完全解
				flag = 1;
				ShowRes();
				//回溯,找出所有解
				Path[k] = -1;
				k--;
			}
		}
		//回溯
		Path[k] = -1;
		k--;
	}

	//如果没有解
	if(flag == 0)
	{
		printf("no solve!");
	}

}