main.cpp

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

/*****************************************************************************
 22. 在一个４＊４的小方格（如图所示）中放置８个＊号，使得每行每列放且
 仅放两个＊号。

          ┌─┬─┬─┬─┐
          │＊│＊│  │  │
          ├─┼─┼─┼─┤
          │＊│  │＊│  │
          ├─┼─┼─┼─┤
          │  │＊│  │＊│
          ├─┼─┼─┼─┤
          │  │  │＊│＊│
          └─┴─┴─┴─┘

 求出所有的基本解。
 *****************************************************************************/


#include <stdio.h>

#define N 4

int a[] = {0,0,0,1,1,2};
int b[] = {1,2,3,2,3,3};

static int path[N];

int checked(int k)
{
	int i;
	int col[N];

	for(i=0; i<N; i++)
		col[i] = 0;

	for(i=0; i<=k; i++)
	{
		col[a[path[i]]] ++;
		col[b[path[i]]] ++;
	}

	for(i=0; i<N; i++)
	{
		if(col[i] > 2)
			return 0;
	}
	return 1;
}

void ShowPath()
{
	int row,col;
	for(row=0; row<N; row++)
	{
//		printf("%3d",path[row]);
		for(col=0; col<N; col++)
		{
			if(col==a[path[row]] || col==b[path[row]])
				printf(" *");
			else printf(" O");
		}
		printf("\n");
	}
	printf("\n");
}

void main()
{
	int flag = 0;
	int k; 

	for(k=0; k<N; k++)
		path[k] = -1;

	k=0;

	while(k>=0)
	{
		while(++path[k]<6)
		{
			if(checked(k) && k<N-1)
			{
				k++;
			}
			else if(checked(k) && k==N-1)
			{
				flag = 1;
				ShowPath();
				getchar();
				path[k] = -1;
				k--;
			}
		}
		path[k] = -1;
		k--;
	}
	if(!flag)
	{
		printf("no solve!\n");
	}
}