锐客网

  1. 首页 > it技术 > >

递归|使用回溯法求所有从n个元素中取m个元素的组合

包含2个版本，第一个为递归版本，代码简洁，性能稍差。第二个为迭代版本，逻辑复杂，但性能更好。
【递归|使用回溯法求所有从n个元素中取m个元素的组合】

#include #include //#include typedef char ELE_TYPE; #define ELE_FMT "%c"//int g_count=0; //元素类型和格式符号使用宏定义,很容易改为其他数据类型，如数组类型改为int，则格式符改为"%d ". void printCombo(int idx_arr[], ELE_TYPE eArr[],int m) { int i; //g_count++; //return ; for (i=0; i n-m+i，则为超限// 这个子程序用到5个if和一个while，总共6次比较，显然，其逻辑要比上面的那个递归版本复杂的多。 // 凡事有利就有弊，这个子程序的性能要比上面的递归版本好， // 我的试验表明，将输出子程序printCombo改为只做一次整数加法，当n=28，m=14，迭代版本的性能是递归版本的130%#define M_FILL 0//填充模式 #define M_INC1//递增模式void IterativeCombos(int n, int m, int idx_arr[], ELE_TYPE eArr[] ) { int i=0; int mode=M_FILL; while (i>=0) { if (mode==M_FILL) //填充模式 { if (i==0) idx_arr[0]=0; else idx_arr[i] = idx_arr[i-1]+1; if (i == m-1) //当前焦点已经达到最大深度 { printCombo(idx_arr,eArr,m); //打印这个包含m个元素的组合 mode=M_INC; //切换为增量模式 } else//没有达到最大深度 i++; //继续填充下级节点 } else//增量模式 { idx_arr[i]++; //焦点元素递增if ( idx_arr[i] > n-m+i ) //已经超限 i--; else { if (i==m-1)//当前焦点已经达到最大深度 printCombo(idx_arr,eArr,m); //打印这个包含m个元素的组合 else { i++; //继续填充下级节点 mode=M_FILL; //切换到填充模式 } } } } }int main(int argc, char* argv[]) { int i; #define N6 #define M3ELE_TYPE eArr[N]; //定义6个数组的数组， int idx_arr[M]; //取到的3个元素的需要放在数组idx_arr中 for (i=0; i



    推荐阅读


    上一篇：unity--鼠标或者手指点击模型播放动画

    下一篇：自己用qt制作的一个具有查询功能的界面