全排列问题的递归解法
思路有两个,一个是递归,一个是栈。两者的本质都是深度优先搜索。。直接上代码。
第一题 p1199
http://ybt.ssoier.cn:8088/problem_show.php?pid=1199
#include <stdio.h>
#include <string.h>
int longs;
char s;
char solution;
void Output()
{
for(int i = 0;i<longs;i++)
{
printf("%c",solution);
}
printf("\n");
}
bool not_used(char x)
{
for(int i = 0;i<=longs;i++)
{
if(x == solution)
{
return 0;
}
}
return 1;//没被用过
}
int Go(int count)
{
if(count == longs)
{
Output();
solution = 0;
return 0;
}
for(int i = 0;i<longs;i++)
{
if(not_used(s))
{
solution = s;
Go(count+1);
solution = 0;
}
}
}
int main()
{
scanf("%s",&s);
longs = strlen(s);
// printf("%c\n",s);
Go(0);
return 0;
}
第二题 p1706
https://www.luogu.org/problemnew/show/P1706
#include <stdio.h>
int n;
char solution;
void Output()
{
for(int i = 0;i<n;i++)
{
printf("%5d",solution);
}
printf("\n");
}
bool not_used(int x)
{
for(int i = 0;i<=n;i++)
{
if(x == solution)
{
return 0;
}
}
return 1;//没被用过
}
int Go(int count)
{
if(count == n)
{
Output();
solution = 0;
return 0;
}
for(int i = 1;i<=n;i++)
{
if(not_used(i))
{
solution = i;
Go(count+1);
solution = 0;
}
}
}
int main()
{
scanf("%d",&n);
Go(0);
return 0;
}
想想是不是可以优化呢,比如可以用一个数组来标记对应的数字或字母是否已使用,这样就不用再遍历一遍数组来判断是否已使用:lol zjgt 发表于 2019-4-15 14:11
想想是不是可以优化呢,比如可以用一个数组来标记对应的数字或字母是否已使用,这样就不用再遍历一遍数组来 ...
是的,可以打静态表来优化
页:
[1]