一步一步写算法（之数据选择）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    在数学中，有一些数据选择的内容。举个例子来说，有这样一组数据：1、2、3、4。现在我们打算从中挑选出1个数据，那么有几种选择呢？结果应该是1、2、3、4；那么如果挑选2个数据呢，怎么选呢？那么结果应该是12、13、14、15。以此类推，我们还能挑选出3个数据、4个数据的情况。

    那么，在程序上面应该怎么表示呢？其实可以使用递归的方法。请大家和我一起计算一下：

    如果需要从1、2、3、4中挑选两个数据，那么是不是先从1开始，然后再2、3、4中挑选一个数据，这样可以有12、13、14三种情况。接着呢，我们从2开始，下面可以选择的数据只有从3、4中选择了，1不能选择了，否则会产生重复选项。以此类推，那我们从4开始的时候，发现4后面没有数据的时候，此时迭代终止。

    挑选2个数据如此，那么挑选n个数据是不是也是这样呢？首先选出第1个数据，那么剩下来的数据只能从这个数据后面位置开始挑选，如果挑选出n-1个数据，那么表示n个数据存在，继续寻找到，直到n-1个数据选不出来为止；接着我们移动第一个数据的位置，同样需要在当前数据的后面挑选n-1个数据。以此类推，如果我们发现当前数据后面连n-1个数据都没有了，那么表示递归就结束了。

    下面我们就可以书写代码了。

    a) 定义全局空间和打印函数，保存已经遍历的数据

static int gAllData[MAX_NUMBER]= {0}; 

static int gTotal = 0; 

void print(int pData[], int length) 

{ 

    int index; 

    for(index = 0; index < length; index++) 

        printf("%d", pData[index]); 

    printf("\n"); 

} 

static int gAllData[MAX_NUMBER]= {0};

static int gTotal = 0;

void print(int pData[], int length)

{

       int index;

       for(index = 0; index < length; index++)

              printf("%d", pData[index]);

       printf("\n");

}    b）开始数据的迭代

void traverse(int pData[], int length, int number) 

{ 

    int index; 

    if(0 == length) 

        return; 

    for(index = 0; index < length; index++){ 

        gAllData[gTotal ++] = pData[index]; 

        if(1 == number) 

            print(gAllData, gTotal); 

        else 

            traverse(pData + (index + 1), length - (index + 1), number -1); 

        gAllData[-- gTotal] = 0; 

    } 

} 

void traverse(int pData[], int length, int number)

{

       int index;

       if(0 == length)

              return;

       for(index = 0; index < length; index++){

              gAllData[gTotal ++] = pData[index];

              if(1 == number)

                     print(gAllData, gTotal);

              else

                     traverse(pData + (index + 1), length - (index + 1), number -1);

              gAllData[-- gTotal] = 0;

       }

}    c）编写测试用例，验证结果

void test() 

{ 

    int data[] = {1, 2, 3, 4, 5, 6}; 

    memset(gAllData, 0, sizeof(int) * MAX_NUMBER); 

    traverse(data, sizeof(data)/sizeof(int), 4); 

} 

void test()

{

       int data[] = {1, 2, 3, 4, 5, 6};

       memset(gAllData, 0, sizeof(int) * MAX_NUMBER);

       traverse(data, sizeof(data)/sizeof(int), 4);

}

   注：我们可以通过不停修改数组data和数值number的方法，验证打印出来的数据和我们自己计算的结果是否有出入。