main.cpp

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

/*******************************************************************************
11. 巧排数字。将１、２、．．．、２０这２０个数排成一排，使得相邻的两个数之
和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法。
//用回溯法求解
//经验证n为偶数时有解.
*********************************************************************************/

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

const int n=20;

//判断一个数是否是素数
bool IsPrimeNumber(int num)
{
	bool flag=true;
	int temp=(int)sqrt(num);
	if(num==1) return false;
	for(int i=2;i<=temp;i++)
	{
		if(num%i==0)
		{
			flag=false;
			break;
		}
	}
	return flag;
}

//回溯算法求解
void main()
{
	
	int i,k=0;
	int path[n];
	int flags[n];
	int ways[n];
	bool IsSolve=false;
	//初始化
	for(i=0;i<n;i++)
	{
		flags[i]=false;
		path[i]=ways[i]=0;
	}
	
	//随机选择一个数,加入解空间
	srand(time(NULL));
	i=rand()%n+1;
	path[k]=i;
	flags[i-1]=true;
	do
	{
		while(ways[k]<n)
		{
			//如果是最终解,跳出
			if(k==n-1&&IsPrimeNumber(path[0]+path[k]))
			{
				IsSolve=true;//标志问题解决
				//有解
				//printf("get a solve!\n");
				//输出一个解
				for(i=0;i<n;i++)
					printf("%3d",path[i]);
				printf("\n");
				getchar();
				//回溯
				flags[path[k]-1]=false;
				ways[k]=0;
				path[k]=0;
				k--;
			}//如果是局部解,继续向前搜索
			else if(k<n-1 && flags[ways[k]]==false 
				&& IsPrimeNumber(path[k]+ways[k]+1))
			{
				flags[ways[k]]=true;//标志该数已被加入局部解
				path[k+1]=ways[k]+1;//将该数加入局部解
				ways[k]++;//到达新的分支
				k++;//向前一步
			}//否则搜索其他分支
			else ways[k]++;
		}
		//如果当前没有解,回溯
		flags[path[k]-1]=false;
		ways[k]=0;
		path[k]=0;
		k--;
	}while(k>=0);
	
	if(!IsSolve)//无解
	{
		printf("no solve!\n");
	}
}