YZM的全排列

50073081 YZM的全排列

【试题描述】

一天，老师给可怜的YZM出了一道题：写出1~n的全排列。YZM写了一天也没写出来。请你帮帮快跪的YZM，输出1~n的全排列。注：这里n为9

【输入要求】

输入n

【输出要求】

1~n的全排列，每个一行

【输入实例】

【输出实例】

12

21

【其他说明】

不允许使用内部函数，也不许直接输出。题目由wxjor提供。
wxjor温馨提示：n<=9

【试题分析】

这一题也是一道经典的不能再经典的dfs，但可能有些初学者不知道DFS，我就讲的细一点点。我们可以定义一个记录数的工具step，一开始step从1开始。如果step超过了n，那么证明这行排列排列完毕了。然后依次输出，别忘记输出回车！然后结束这次DFS。代码如下:

if(n+1==step)//当n+1==step代表step超过了n

{

	for(int j=1;j<=n;j++) printf("%d",a[j]);//挨个输出

	printf("\n");//一定要回车

	return ;//结束这行的DFS

}

大家想一想，还差什么呢？

当然，差for(int i=1;i<=n;i++)这层循环，还有吗？

我们来看一下，为什么上面的样例中没有给出11和22，难道是题错了？

注意这一点：全排列是不能有重复的。

那么，怎么知道这个数以前处没出现过呢？

我们可以定义一个book数组，如果i出现了，那么把book[i]表为1。

for循环代码：

for(i=1;i<=n;i++)//从一到n循环

    if(book[i]==0)//如果没有出现过

    {

	a[step]=i;//第step部是i

	book[i]=1;//标记为出现过

	dfs(step+1);//遍历下一步

	book[i]=0;//标记为未出现过，因为下一个排列要使用

    }

dfs整体代码：

void dfs(int step)

{

    int i;

	if(n+1==step)

	{

		for(int j=1;j<=n;j++) printf("%d",a[j]);

		printf("\n");

		return ;

	}

	for(i=1;i<=n;i++)

	    if(book[i]==0)

	    {

		a[step]=i;

		book[i]=1;

		dfs(step+1);

		book[i]=0;

            }

}

然后int main()。

输入n。

dfs(?)。

从几开始呢？

我们说，通常情况下，都是从1开始的。

来看看为什么我们这题是从1开始？因为我们是从step=1时来弄的。

【代码】

#include<iostream>

#include<fstream>

using namespace std;

int a[10],book[10],n;

void dfs(int step)

{

    int i;

	if(n+1==step)

	{

		for(int j=1;j<=n;j++) printf("%d",a[j]);

		printf("\n");

		return ;

	}

	for(i=1;i<=n;i++)

	    if(book[i]==0)

	    {

		a[step]=i;

		book[i]=1;

		dfs(step+1);

		book[i]=0;

            }

}

int main()

{

    scanf("%d",&n);

    dfs(1);

}

巴特西

YZM的全排列

最新文章

热门文章