如何用C++实现从m个数当中选n个组合

Securing the Barn

Time Limit: 1 Seconds Memory Limit: 32768 K

Total Submit:42 Accepted:16

--------------------------------------------------------------------------------

Description

Farmer John has installed a new security system on the barn and now must issue a valid password to the cows in the herd. A valid password consists of L (3 <= L <= 15) different lower-case characters (from the traditional latin character set 'a'...'z'), has at least one vowel ('a', 'e', 'i', 'o', or 'u'), at least two consonants (non-vowels), and has characters that appear in alphabetical order (i.e., 'abc' is valid; 'bac' is not).
Given a desired length L along with C lower-case characters, write a program to print all the valid passwords of length L that can be formed from those letters. The passwords must be printed in alphabetical order, one per line.

Input

* Line 1: Two space-separated integers, L and C
* Line 2: C space-separated lower-case characters that are the set of characters from which to build the passwords

IMPORT：

To avoid get Wrong Answer, Please use gets() (C) or cin (C++) instead of scanf("%c") or getchar() to receive input.

Output

* Lines 1..?: Each output line contains a word of length L characters (and no spaces). The output lines must appear in alphabetical order.

Sample Input

4 6
a t c i s w

Sample Output

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

Hint

INPUT DETAILS:
Passwords of length 4 chosen from the given six characters

这个题目要求出并记录所有组合，所以for循环是省不了的，但是可以做到不无脑。

首先分析一下题目，设取出的n个数和为y，那么可以得出：
y的最大值为 i+(i-1)+(i-2)+···+(i-n+1)
进行检定：如果y的最大值小于m，那么无解；否则，y的最大值肯定满足条件，使用for循环，依次逐渐减小n个数的值，直至y=m，则输出了所有解。

代码我就不写了，算法如上，再举例说明一下最后中情况for循环的思路，就拿楼主的例子说明：
“十个数，从1到10，m=15，n=3”
首先，10、9、8必然满足条件，将第三个数从8开始减小，一直到1都满足条件；
然后，减小第二个数，起始为10、8、7，再将第三个数从7开始减小，一直到1都满足条件；
···
最终当循环到6、5、4时，再减小将不满足条件，输出完毕。

还有什么疑问，再追问

不好意思，英文我看不懂，不过中文我就懂了 #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <time.h> int a[100];//a[0]舍弃不用，a[1]至a[m]存组合数 void zh(int n,int m,int num) { int i; if(m==num-1) { for(i=1;i<=m;i++) printf("%d ",a[i]); printf("\n"); return; } for(i=a[num-1]+1;i<n+1;i++)//有顺序的排列即为组合 { a[num]=i; //printf("a[%d]=%d\n",num,a[num]); zh(n,m,num+1); } } main() { int n,m; a[0]=0; printf("please input n,m (n>m)\n"); scanf("%d %d",&n,&m); zh(n,m,1); getch(); }