当前位置: IT大杂烩 > 人工智能  > 组合算法的递归实现(C版)

组合算法的递归实现(C版)

www.someabcd.com  网友分享于:May 18, 2018 11:09:07 AM

问题描述:给定一个集合x1,x2,...,xn, 输出从这n个元素中取m个的所有组合。

算法基本思想:如果xi为组合的一个元素,那么组合的下一个元素在x(i+1), x(i+2),....,Xn中选取。

递归实现如下:VC++编译测试通过。

#include 
  
   
#include 
   
    
#include 
    
     

#define MAX_LENGTH 20
char a[MAX_LENGTH]; //存储初始字符串
char r[MAX_LENGTH]; //存储组合结果

//n, 初始字符串的长度
//m, 所求组合的长度
//k, 初始集合中当前处理位置, a[k]
//index, 所求组合结果数组的索引, r[index]
void combination(int n, int m, int k, int index)
{
    int i;
    if(index == m) //输出组合结果
    {
        for(i = 0; i < m; ++i)
            printf("%c", r[i]);
        printf("\n");
        return;
    }

    for(i = k; i < n; ++i)
    {
        r[index] = a[i];
        combination(n, m, i + 1, index + 1);//注意第三个参数是i + 1
    }
}

int main(int argc, char** argv)
{
    strcpy(a, "abcde");
    combination(5, 3, 0, 0);
    system("pause");
    return 0;
}
    
   
  
发布此文章仅为传递网友分享,不代表本站观点,若侵权请联系我们删除,本站将不对此承担任何责任。
Copyright ©2018  IT大杂烩  版权所有  京ICP备11030978号-1 网站地图