数的全排列
- 什么是数的全排列，这是一个数学问题，就是从n个数字中选择n个数字按照一定的顺序排列起来
- 如：123的全排列是123、132、213、231、312、321
1234的全排列是1234、1243、1324、1342、1423、1432、2134、2143、2314、2341、2413、2431、3124、3142、3214、3241、3412、3421、4123、4132、4213、4231、4312、4321
1.已知数的个数
- 首先求123的全排列，三重嵌套循环就可以搞定，代码如下：
for(a=1;a<=3;a++) for(b=1;b<=3;b++) for(c=1;c<=3;c++) if(a!b&&a!=c&&b!=c) printf("%d%d%d",a,b,c);讯享网
2.不知数的个数
- 例如：输入3时输出123的全排列，输入4时输出1234的全排列
- 此算法的核心思想就是递归下图来用1234来演示一下
讯享网 - 如上图给每一次的交换都标上序号
- 我们知道对于n个数的全排列的个数为n！我们可以这样想
对于第一位我们做四次交换，对于它的每一次交换，后面三位再进行全排列，同样，对于第二位我们可以做三次交换，对于它的每一次交换，后面两位再进行全排，以此类推，就得到4x3x3x1即为全排列的个数
我们可以考虑用递归实现
步骤如下
1.做编号为1的交换（即1和自己交换），然后做编号为5的交换，再做编号为8的交换，最后就打印输出
2.第一次打印输出后，返回函数上一层，做编号为9的交换，再到最后一位打印输出
3.运行完返回函数上一层，我们已经将12打头的所有可能都输出了1234、1243然后我们再返回上一层做编号为6的交换（然后我们重复1、2的步骤），这时候将输出13打头的所有可能
4.这样递归再返回再递归再返回，用循环语句控制第一位变化最慢，最后一位变化最快的全排列输出
代码如下：
讯享网#include<stdio.h> //交换 void swap(int &a,int &b) {
int temp; temp=a; a=b; b=temp; } //全排列递归算法 void perm(int list[],int k,int m) {
//list 数组存放排列的数，k表示层，代表第几个数，m表示数组的长度 int i; if(k==m) {
//k=m表示到达最后一个数，不能再交换，最终的排列数需要输出 for(i=0;i<m;i++){
printf("%d",list[i]); } printf("\n"); } else{
for(i=k;i<m;i++){
swap(list[i],list[k]);//枚举该层子序列第一个位置可以取的值 perm(list,k+1,m);//该层递归的子序列第一个位置已经确定了，所以又可以往下再分 swap(list[i],list[k]);//把第该层子序列第一个位置的值换成另外一个值，所以要交换回来 } } } int main(){
int i,n,a[100]; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); perm(a,0,n); return 0; }
盒子思想
- 即把使用过的数字当成放在盒子里
- 代码如下：
#include<stdio.h> int a[10],book[10],n;//此处说明：c语言的全局变量在没有赋值以前默认为0 //book数组不用再次赋初值为0 void rank(int step){
int i; if(step==n+1)//如果站在第n+1的盒子面前，则证明前n个数已排好 {
//输出数字 for(i=1;i<=n;i++) printf("%d",a[i]); printf("\n"); return;//返回之前的一步（最近一次调用rank函数的地方） } //没走完时则按照1，2，3...n的顺序依次尝试 for(i=1;i<=n;i++){
//判断数字是否用过 if(book[i]==0)//book[i]=0表示数未用过 {
a[step]=i;//将数字i放到第step个盒子中 book[i]=1;//将book[i]设为1，表示数字i已使用 //走到下一个盒子面前，递归 rank(step+1); book[i]=0;//将刚才的数字标记为0，表示在这一轮数字没有使用过 } } return; } int main(){
scanf("%d",&n);//输入数字只能是1-9，如果要更大则要改变全局变量 rank(1);//首先站在1号盒子面前 return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/39484.html