输出几个数的全排列(110)

81 阅读 0 评论 54 点赞

我是靠谱客的博主成就悟空，最近开发中收集的这篇文章主要介绍输出几个数的全排列(110)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

前言

今天算是被这道题折磨了好久，我发现用递归解决的题目在别人把答案给你过后你看完真的会赞不绝口：我靠，真妙啊！！！，但是可能几小时，可能几天，让你再写一遍可能就会傻眼，还是不知道怎么去写，所以对于每一道算法题我都希望逐步追踪它的执行过程，以便留下更深的影响。

思想概述

假如有5个数，首先确定第1个位置上有几种可选择情况，显然是5种，然后确定第2个位置上有几种情况，由于1位置已确定，则还剩4种情况，以此类推，最后一个位置只有当前这种情况，具体实现及解释看下文，首先贴上代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
	int length;
	char *p = NULL;
	printf("请问一共需要处理多少个数？n");
	scanf("%d", &length);
	getchar();//不要忘记这一句，否则缓冲区剩余'n'，gets_s函数发现'n'证明用户输入结束，将'n'转化为''存在p中
	p = (char*)malloc(sizeof(char)*(length + 1));//动态分配长度为length+1的字符数组，多1是为了存''
	printf("请连续输入这%d个数:n", length);
	gets_s(p, length + 1);
	void AllRange(char *, int, int);
	AllRange(p, 0, strlen(p) - 1);
	return 0;
}
void swap(char *p, char *q)//交换函数
{
	char temp;
	temp = *p;
	*p = *q;
	*q = temp;
}
void AllRange(char *p, int k, int m)//核心函数，参数理解为：当前为k位置上选值，可能的值的下标为k~m
{
	void swap(char *, char *);
	if (k == m)
	{
		static int s = 1;
		printf("第%d种情况为:%sn", s++, p);
	}
	else
	{
		for (int j = k; j <= m; j++)//当前位置可能有哪几种情况
		{
			swap(&p[k], &p[j]);//确定k位置的值，确定的方法是当前k位置值与被选中位置的值互换
			AllRange(p, k + 1, m);//确定k+1位置的值
			swap(&p[k], &p[j]);//此语句只有当所有位置全部确定好后，才会开始指向第一次，含义是从后往前再把经历过变换的过程再换回去
		}
	}
}

代码解释：请先看如下对于递归过程的每步追踪结果，因为是按照我自己的思路写的，如果看不太懂可以看看下面的文字说明，文字和图片一起看
在这里插入图片描述

首先看分割线上面的内容，第一行后面的“注：本行展示所“干坏事””，由于此程序在为当前位置选一个数时，是将当前位置的值与想要的值互换得到的，我将这种交换的过程比喻成“干坏事”，第一次干坏事确定了下标0位置上的值，第二次干坏事确定了下标1位置上的值，以此类推，若有4个数，则它一共干了3次坏事(为什么不是4？也可以说是4，只不过是确定了前三个数后，最后一个数也就唯一确定了，换不换无所谓了)，3次坏事干完后产生了第一种情况bdac，继续选下一种情况，注意：当前数组中存的是第一种情况的结果，我们选第二种情况时应该也在abcd这种顺序上选，而不应该基于第一种情况的结果上选，由此出现了第二行后面的“注：本行展示“恢复””，恢复的含义是，由于干了3次坏事进行了3次交换，那么我就要再给它换回去，以确保它“恢复”成原始情况(abcd)，然后进行第二种情况的选取。