KaQqi 发表于 2019-4-14 15:09

全排列问题的递归解法

思路有两个,一个是递归,一个是栈。两者的本质都是深度优先搜索。。

直接上代码。
第一题 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;
}

zjgt 发表于 2019-4-15 14:11

想想是不是可以优化呢,比如可以用一个数组来标记对应的数字或字母是否已使用,这样就不用再遍历一遍数组来判断是否已使用:lol

KaQqi 发表于 2019-4-15 18:58

zjgt 发表于 2019-4-15 14:11
想想是不是可以优化呢,比如可以用一个数组来标记对应的数字或字母是否已使用,这样就不用再遍历一遍数组来 ...

是的,可以打静态表来优化
页: [1]
查看完整版本: 全排列问题的递归解法