Lotto 迭代算法 cpp
题目内容：
给定N个数字，再从中选定M个数字出来。
将每一种组合内的数字又小到大排列之后，将所有组合按照字典序排列，
请你找到第X组的第Y个数字。
给定的数字为1~N。
范例：
范例1：
(N,M,X,Y) = (5,2,8,2)
所有组合按顺序排列为：
(1 2), (1 3), (1 4), (1 5), (2 3),
(2 4), (2 5), (3 4), (3 5), (4 5)
所以第8组第2个数字为4。
输入格式:
第一行有一个数字T代表有多少组测试案例。
每一组测试案例一共一行。
这一行有四个数字 N M X Y。
意义如上所述。
测试案例范围：
T < 1000
1 < N < 12
1 < M < N
0 < X <= C(N, M)
0 < Y <= N
输出格式：
对于每一个测试案例，找到第X组第Y个数字。
将所有测试案例的答案加和后再输出。
输入样例：
2
5 2 8 2
6 3 7 3
输出样例：
10
时间限制：500ms内存限制：32000kb代码实现：
采用迭代的方式，分析每组数字的进位规则进行迭代。
#include <iostream>
inline void printArray(int array[], int len)
{
for(int i=0;i<len;i++)
{
std::cout<<array[i]<<" ";
}
std::cout<<std::endl;
}
inline void getNext(int array[], int len, int n){
int i, cur;
cur = len - 1;
while (array[cur] >= cur + n - len + 1){
cur--;
}
array[cur]++;
for (i = cur + 1; i < len; i++){
array[i] = array[i - 1] + 1;
}
}
int main(){
int test_num, i, j;
int n, m, x, y, sum = 0;
std::cin >> test_num;
for (j = 0; j<test_num; j++){
std::cin >> n >> m >> x >> y;
int* array = new int[m];
for (i = 1; i <= m; i++){
array[i - 1] = i;
}
for (i = 2; i <= x; i++){
getNext(array, m, n);
}
sum += array[y - 1];
delete [] array;
}
std::cout << sum;
return 0;
}
