首页 > 代码库 > [算法] 固定的元素在固定长度上进行全排列
[算法] 固定的元素在固定长度上进行全排列
题目1：打印从1到最大n位数的所有数字。比如n是3，则打印1,2,3,4...999。
题目2：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能值出现的概率。
----------------
对于题目1，由于n的值可能会很大，所以直接print是不行的，没有一个数据类型可以承载大n。对于题目2，求概率就是求点数和为s的投掷出现的次数。这两个题目有一个共同点，它们都与一种序列有关系，这个序列可以描述为：有n个盒子，每个盒子里面都可以放x1到xn的任意一个数，输出所有可能的排放方式（可能要求有序）。对于题目1，就是有n个盒子，每个盒子里面放入0-9的任意一个数，打印序列。对于题目2，就是n个盒子，每个盒子里面放入1-6的任意一个数，统计盒子内元素的和的出现次数。
---------------
题目1的伪代码：
int* S=new int[n+1]; //用S[n]记录第n位，S就是那个盒子void printN(int n) //打印1到最大n位整数{ for(int i=0;i<10;i++) { S[n]=i; if(n>1) { printN(n-1); } else if(n==1) { print(S); //可能还需要些处理，倒过来，去打掉不需要的0等 } } }
对于题目2，我们不需要用一个数组表示出盒子，因为我们不关系盒子里的东西具体是什么，我们只关心里面元素的和。
void getAppearTimes(int n,int end,int curSum,int* probility){ for(int i=1;i<=6;i++) { if(end==0) { //probility[i]存储和为i的投掷出现次数 probility[curSum+i]++; } else { getAppearTimes(n,end-1,curSum+i,probility); } }}
[算法] 固定的元素在固定长度上进行全排列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。