递归：全排列字符(C语言)思路讲解 |
您所在的位置：网站首页 › c语言全排列思路 › 递归：全排列字符(C语言)思路讲解 |
递归：全排列字符(C语言)思路讲解
|
一、确定递归的退出条件所涉及的变量
以全排类字符为例，假设有数组[1,2,3,4,5]做全排列，那么其退出条件应该为当前存放数组已等同于数组长度。即找到了无论是[1,2,3,5,4] or [2,1,3,5,4]。只要保证此次数组内容已满足形成新的数组排列方式，就给它退出。 假设我们的数组长度变量为numLen，每次存放后进行记录当前数组长度的变量为index，那么该退出条件如下： if (!(index < numLen)) { return ; } 二、回溯思路依旧以全排类字符为例，假设数组[1,2,3,4,5]此刻已经形成了第一个排列也就是自身[1,2,3,4,5]。那么此刻我应该让代码回溯至之前的状态，可以回溯至【1，2，3，未知,未知】。也可以回溯至【1，2，3，5，未知】。 这是什么意思呢？实际上当我们形成了一个完整的内容，那接下里要做的就是存放该完整内容，然后回溯至不完整状态。也就是说，递归完成的需求永远在最内一层，结束最内一层后，就会回到上一层的下一行代码继续执行，那么这一行我们要做的就是标记已存放的完整内容。如何标记呢？ 以全排列为例：因为全排列永远是在排列初始数组[1,2,3,4,5]。假设我这个时候执行到[1,2,3]时，如果说我的[1,2,3,4,5]这种排列方式已经存放，那接下来要走的一定是[1,2,3,5,4]。 因为当执行完[1,2,3,4,5]后，形成的新数组长度等于原始数组，所以再进一层的函数退出。 接下来退出到了[1,2,3,4,5]的状态，此时调用循环已不符合循环规定，退出至[1,2,3,4]状态，此时我们应该是释放四号位的锁定效果，五号位的锁定效果在上一层已被释放，所以循环会遍历到五号位的元素5，这个时候会形成[1,2,3,5]，随着再进一步，就会形成[1,2,3,5,4]的效果。 其他的数组效果也会随着这个原理一步步推到出来，而这就是递归的回溯思路。形成需求、记录、回溯至不符合的需求、继续新的需求、新的记录，直到全部形成并退出 if (index < numLen) { for (int i = 0; i < numLen; i++) { if (flag[i] == 0) { column[index] = arr[i]; flag[i] = 1; dfs(doubleDimensionalArray, arr, numLen, flag, index + 1, column, ptr); flag[i] = 0; } } } else { //输出已满足 for (int i = 0; i < numLen; i++) { doubleDimensionalArray[(*ptr)][i] = column[i]; } (*ptr)++; }注*：代码片段和完整代码不太相似，请辨别 记住这两个思路，在任何递归思想上都可以按照这个思路进行代码编写，最后，再附上完整代码。 #include #include "stdlib.h" #include "string.h" void dfs( int ** doubleDimensionalArray, int *arr, int numLen, int *flag,int index, int *column,int *ptr) { if (index < numLen) { for (int i = 0; i < numLen; i++) { if (flag[i] == 0) { column[index] = arr[i]; flag[i] = 1; dfs(doubleDimensionalArray, arr, numLen, flag, index + 1, column, ptr); flag[i] = 0; } } } else { //输出已满足 for (int i = 0; i < numLen; i++) { doubleDimensionalArray[(*ptr)][i] = column[i]; } (*ptr)++; } } int main() { int numLen = 0; printf("输入需要排列的数组大小:"); scanf_s("%d",&numLen); printf("顺序输入需要的数字:"); int* arr = ( int*)malloc(sizeof(int) * numLen); for (int i = 0; i < numLen; i++) { scanf_s("%d", &arr[i]); } for (int i = 0; i < numLen - 1; i++) { for (int j = i + 1; j < numLen; j++) { if (arr[i] > arr[j]) { int tempNum = arr[i]; arr[i] = arr[j]; arr[j] = tempNum; } } } int count = 1; for (int i = 1; i2^33次方的，就别用，性能直接崩掉了。所以，一般而言，递归都是用来提高个人开发逻辑和脑容量的。但如果希望自己的编程逻辑再进一步，那一定要学会递归思路哦。希望各位的编程能力都能让中国的科技越来越完善，怎么说来着，遥遥领先~
|
【本文地址】
今日新闻 |
推荐新闻 |