蓝桥杯算法提高VIP-排列数 （深度优先算法）

解题思路:

深度优先算法:

一维数组a[10]用来存放10个数，book[10]作为标志数组，用来判断当前数是否已经访问过(是否已经使用过)，

book[i]=0表示第i个数未被访问

book[i]=1表示第i个数已经被使用(访问)

部分代码解析:

        for(i=0; i<10; i++)
	{
		if(book[i]==0)          //第i个数未被使用
		{
			a[step]=i;      //将i存入数组a中
			book[i]=1;      //book[i]=1表示i已经被使用了
			dfs(step+1,n);  //递归
			book[i]=0;	//一定要将刚才的数收回，才能进行下一次尝试 
		}
	}

注意事项:

参考代码:

#include <stdio.h>
int a[10],book[10];
int g_count; 
void dfs(int step,int n)
{
	int i;
	if(step==10) //step从0开始 step==10时，表示前0~9都处理好了 
	{
		g_count++;
		if(n==g_count)
		{
			for(i=0; i<10; i++)
			{
				printf("%d",a[i]);
			}
		}
		return;
	}
	for(i=0; i<10; i++)
	{
		if(book[i]==0)
		{
			a[step]=i;
			book[i]=1;
			dfs(step+1,n);
			book[i]=0;	
		}
	}
	return ;
}
int main()
{
	int n;	
	scanf("%d",&n);
	dfs(0,n);	
}