流离之人追逐幻影

用户名：pwj666

访问量：60243

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13962
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：188

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C++代码）（经常这样写会不会被打死）

理解全排列（递归）-----每日PAT

　　作者: 流离之人追逐幻影　　　　发表时间：2019-07-15 02:40:22 浏览：783　|　评论：0　

原始问题：输出1~n这个n个整数的全排列
简化问题：输出1~4这个4个整数的全排列

初始想法
```
1.找可以递归的部分
2.找终止条件
```

```
首先，先在脑子里模拟我想要的计算机大致计算过程：
123
12
1
13
132
13
1

2
21
213
21
23
231
23
2

.....我知道计算机就是得这样子计算，但是我该如何去实现啊。不知道，所以就把代码仔细研究了几遍。
```

```
以分治的思想可以把问题分解为，“以1开头的全排列”，“以2开头的全排列”，......“以4开头的全排列”。所以可以设一个数组P,用来存放当前排列，再设定一个hashTables数组来判断整数x是否已在数组P中。
```

```
现在按顺序往P的第1位到第4位中填入数字。现在就可以假设P[1]~P[index-1]就已经填好了，正准备填P[index]。那么肯定得枚举1~4，如果当前数字还没有在P[1]~p[index-1]中，（hashTable[x]==false）,则就把它填入P[index]中，同时将hashTable[x]置为true，然后去处理P的下一位（进行递归）,当递归完成时，再将hashTable[x]还原为false，以便让P[index]填下一个数字。
```

```
然后是找递归边界，当index=4+1的时候说明P的第1~4位都已经填好了，此时就可以进行输出了，然后直接return。
```
1~4全排列
```
#include<stdio.h>

const int maxn=11;
int P[maxn],HashTable[maxn]={false};

void generateP(int index) {
    if (index == 4 + 1) {
        for (int i = 1; i <= 4; i++) {
            printf("%d", P[i]);
        }
        printf("\n");
        return;
    }

for (int x = 1; x <= 4; x++) {//枚举1~4,，试图将x填入P[index]
        if (HashTable[x] == false) {//如果x不在P[1]~p[index-1]中
            P[index] = x;//令P的第index位为x，即把x加入当前排列
            HashTable[x] = true;//记x已在P中
            generateP(index + 1);//处理排列的第index+1位
            HashTable[x] = false;//已处理完P[index]为x的子问题，还原状态
        }
    }
}
int main(){
    generateP(1);//从P[1]开始填
    return 0;
}

```
![](/image_editor_upload/20190716100551_75150.png)
1~N全排列 （N自定）
```
#include<stdio.h>

const int maxn=11;
int N,P[maxn],HashTable[maxn]={false};
void generateP(int index) {
    if (index == N + 1) {
        for (int i = 1; i <= N; i++) {
            printf("%d", P[i]);
        }
        printf("\n");
        return;
    }

for (int x = 1; x <= N; x++) {
        if (HashTable[x] == false) {
            P[index] = x;
            HashTable[x] = true;
            generateP(index + 1);//
            HashTable[x] = false;	
        }
    }
}
int main(){
    N=3;
    generateP(1);
    return 0;
}

```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）（经常这样写会不会被打死）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

理解全排列（递归）-----每日PAT

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言训练-尼科彻斯定理（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

用筛法求之N内的素数。（C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1024题解

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

1250题解

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）（经常这样写会不会被打死）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

理解全排列（递归）-----每日PAT

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言训练-尼科彻斯定理 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

用筛法求之N内的素数。 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1024题解

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

1250题解

　　评论区

C语言训练-尼科彻斯定理（C语言代码）

用筛法求之N内的素数。（C++代码）