Generic placeholder image
闲敲代码、落灯花
What's past is prologue

联系邮箱:email@hezehua.net


联系QQ:1907330840

座右铭

保持热情,持续学习,每日精进

算法--生成1~n的排列

算法--生成1~n的排列

本文与作者在csdn上的博文【算法--生成1~n的排列】保持同步


(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)。

从中我们似乎发现了一些规律:先输出以1开头的排列,再输出以2开头的排列,然后是3;而在以1开头的排列中,1的后一位又是按从小到大的顺序出现,这似乎有些递归的联系。

事实上,我们分析一下生成排列的全过程,就会发现有一定递归的规律:

这不就是一棵树嘛?确实,由于这棵树能展现递归函数的调用过程,所以也称之为----解答树。

现在,根据解答树我们可以开始构造递归函数了:  定义一个大小等于待排列元素数目的数组,据解答树特点,可用DFS方式逐层深入给数组填空,然后由数组大小作为递归边界,并且在赋值时注意判断不可重复。

代码如下

#include<cstdio>
#include <cstdlib>
using namespace std;

void permutation(int *a,int n,int cur){
    if(cur==n){
        for(int i=0;i<n;i++)printf("%d ",a[i]);printf("\n");
    }
    else {
        for(int j=1;j<=n;j++){
            int ok=1;
            for(int k=0;k<cur;k++){          
                if(a[k]==j){
                    ok=0;break;
                }
            }
            if(ok){
                a[cur]=j;
                permutation(a,n,cur+1);
            }           
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    int *a=new int[n]; 
    permutation(a,n,0); 
}



猜你喜欢
算法--大数开方
阅读 533

之前已找到比较好的大数乘法算法,现在我们来解决大数开方问题,如有大数n,求其开方x,则x与n必满足x*x=n;也就是说我们能遍历x找到n的开方,但是问题在于我们是不可能对大数遍历的。如果我们可以确定它的大致范围,仅仅测试几个不容易直接判断的数据就找到目标数据就好了。      1-一个n位数的开...

动态规划入门之国王的金矿
阅读 575

最近学习算法,对动态规划不太了解,使用的时候照搬转移方程式,知其然不知其所以然,今天看到一篇动态规划的教程,解释得非常通俗,原文在这里[动态规划入门教程] (http://blog.csdn.net/woshioosm/article/details/7438834),下面我用自己的记忆和理解...

大数乘法(二)
阅读 574

乘法运算过程模拟法首先获取输入的乘数(a)与被乘数(b)字符串,按一般乘法运算过程,先是a的最后一位数字与b的最后一位数字相乘,接着a中用于相乘的数下标递减,直到a中所有数字与b最后一位都相乘过,保存结果后再递减b中的用于相乘的数字的下标,循环下去,直到b中每一位数都与a所有数相乘完。 在这个过程...

大数乘法(一)
阅读 488

常用的大数相乘算法有模拟加减法和分治法,第一种符合我们的运算习惯,第二种用数学方法提高了效率,(具体描述与实现可参考http://www.cnblogs.com/heyonggang/p/3599857.html)而两种各有优势的方法的程序实现都比较复杂,并且不易于初学者理解,于是我琢磨出了一个将...

算法--生成可重集排列
阅读 384

在生成1~n的排列一文中,我们获取排列时用了控制不相等来实现让每个数都不重复地出现,所以如果要生成含有重复元素的全排列,对对生成1~n的排列的程序适当修改即可。 首先,把各个元素改成用户输入,输入数组为p,然后把if(a[k]==j)改为if(a[k]==p[j]),a[cur]=j改成a[cur...

大数加减
阅读 414

太残忍,半个月不做题,就对题目毫无感觉了,明明思路正确清晰,但敲的代码满满的bug,连输入字符串前要开辟空间都能无视。。。还在输入后就清空了却在后面一个劲的对它操作。。。略怀悲伤地把代码改好了。#include #include #incl...

生成子集——位向量法
阅读 380

生成0~n序列的子集对于0~n的每一个值在集合中都有存在和不存在两种状态,所以递归每个值的存在状态即可生成子集#include #include #include #include

在棋盘上放置8个皇后,使得他们不能相互攻击,此时,每个皇后的攻击范围为同行同列和同对角线,要求找出所有解, 回忆之前分析生成排列所用的解答树,我们再把问题简化为四皇后问题,规则不变,写出它的完整解答树 与生成1~n的排列这篇博文中的解答树最大的不同点就是----只有一条或者几条路径可以...