main.cpp

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

/*********************************************************************
4. 在Ｎ行Ｎ列的数阵中, 数Ｋ（１〈＝Ｋ〈＝Ｎ）在每行和每列中出现且仅
  出现一次，这样的数阵叫Ｎ阶拉丁方阵。例如下图就是一个五阶拉丁方阵。
  编一程序，从键盘输入Ｎ值后，打印出所有不同的Ｎ阶拉丁方阵，并统计个数。

        1  2  3  4  5
        2  3  4  5  1
        3  4  5  1  2
        4  5  1  2  3
        5  1  2  3  4

 *********************************************************************/

/**********************************************************************
解决方法:
1.生成1~N的排列
2.按照上面错位输出
3.对于每一种1~N的排列执行1,2
//关键是生成排列
*********************************************************************/


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

static int *pnNum;
static int N;
static int count;

void output()
{
	int i;
	for(i=0; i<N; i++)
	{
		int k;
		for(k=0; k<N; k++)
		{
			printf("%3d",pnNum[(i+k)%N]);
		}
		printf("\n");
	}
	printf("\n");
}

//生成一个排列
void perm(int k)
{
	int m;
	if(k == N-1)
	{
		//输出
		count++;
		output();
		return ;
	}
	for(m=k; m<N; m++)
	{
		int temp;
		temp = pnNum[m];
		pnNum[m] = pnNum[k];
		pnNum[k] = temp;
		perm(k+1);
		temp = pnNum[m];
		pnNum[m] = pnNum[k];
		pnNum[k] = temp;
	}
}

void main()
{
	int i;

	printf("请输入一个正整数N:");
	scanf("%d",&N);
	if(N<0)
	{
		printf("N不符合!\n");
		return;
	}
	pnNum = (int*)malloc(N*sizeof(int));
	for(i=0; i<N; i++)
	{
		pnNum[i] = i+1;
	}
	perm(0);
	printf("总数%d\n",count);
	free(pnNum);
}