百度面试（组合排列数）
1、请编写函数foo(int x, int y, int n) 计算：随机生成x个大小为[1,y]的正整数，它们的和为n的概率是多少？语言仅限于PHP、C/C++、Java中的一种。
个人认为本质是求组合
概率=和为n的组合个数/总的组合个数
求解组合数
package baidu;
public class rand {
/**
* @param args
*/
public static int n=7, r=5;
public static int[] C={0,0,0,0,0,0,0};
public static int[] used={0,0,0,0,0,0,0};
public static void main(String[] args) {
// TODO Auto-generated method stub
//combine(0,0);
char elements[]={'a','b','c','d','e'};
int setLg=5;
GenCom(elements, setLg, 3);
}
//法1 递归
public static void combine(int pos, int h)
{
int i;
if (pos==r) {
for (i=0; i<n; i++)
if(used[i]==1)
{
System.out.print(i);
}
System.out.print("\n");
return;
}
for (i=h; i<=n-r+pos; i++)
if (used[i]==0) {
used[i]++;
combine(pos+1,i+1);
used[i]--;
}
}
//法2 位运算
public static void OutputCom( char elements[], int[] flags, int length)
{
int i;
for(i=0; i<length; i++)
{
if(flags[i]==1)
{
System.out.print(elements[i]);
}
}
System.out.print("\n");
}
/*计算组合*/
public static int GenCom( char elements[], int setLg, int k)
//elements:集合元素; setLg:集合长度; k:从集合中要选取的元素个数
{
if(k>setLg || k<=0)
return -1;
int i,j; //循环变量
int has10; //是否有"10"组合的标志:1-有;0-无
int bound; //第一个"10"组合的索引
int num1; //"10"组合左边的"1"的个数
int[] flags =new int[setLg];//与元素集合对应的标志:1-被选中;0-未被选中
//初始化,将标志的前k个元素置1,表示第一个组合为前k个数
for(i=0; i<k; i++)
flags[i]=1;
for(i=k; i<setLg; i++)
flags[i]=0;
OutputCom(elements, flags, setLg);//输出初始化的组合
/*
从左到右扫描标志的"10"组合，找到第一个"10"组合后将其变为"01"组合，同时将其左边的所有"1"全部移动到数组的最左端
*/
while(true)
{
num1 = 0;
has10= 0;
for(i=0; i<setLg-1; i++)
{
if(flags[i]==1 && flags[i+1]==0)//找到第一个"10"组合
{
bound = i;
flags[i]=0;//将该"10"组合变为"01"组合
flags[i+1]=1;
for(j=0; j<num1; j++)//将其左边的所有"1"全部移动到数组的最左端
{
flags[j]=1;
}
for(j=num1; j<bound; j++)
{
flags[j]=0;
}
has10 = 1;
break;
}
else if(flags[i]==1)
{
num1++;
}
}
if(has10==0)//没有"10"组合了,代表组合计算完毕
break;
OutputCom(elements, flags, setLg);
}
return 1;
}
}
排列数
全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。现以{1, 2, 3, 4, 5}为
例说明如何编写全排列的递归算法。
1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。
由于一个数的全排列就是其本身，从而得到以上结果。
2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。
即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.
从而可以推断，设一组数p = {r1, r2, r3, ... ,rn}, 全排列为perm(p)，pn = p - {rn}。
因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。当n = 1时perm(p} = r1。
为了更容易理解，将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。
算法如下：
#include <stdio.h>
int n = 0;
void swap(int *a, int *b)
{
int m;
m = *a;
*a = *b;
*b = m;
}
void perm(int list[], int k, int m)
{
int i;
if(k > m)
{
for(i = 0; i <= m; i++)
printf("%d ", list[i]);
printf("/n");
n++;
}
else
{
for(i = k; i <= m; i++)
{
swap(&list[k], &list[i]);
perm(list, k + 1, m);
swap(&list[k], &list[i]);
}
}
}
int main()
{
int list[] = {1, 2, 3, 4, 5};
perm(list, 0, 4);
printf("total:%d/n", n);
return 0;
}
