主题:求助,组合问题。从n个数中选出m个数的全部组合。新手求指导。
wo2ni2dajia2
[专家分:0] 发布于 2012-03-06 20:08:00
如题。用递归算法,自己想了老半天还是没有一点头绪。求算法思想,无代码也可。
回复列表 (共1个回复)
沙发
windy0will [专家分:2300] 发布于 2012-03-07 19:24:00
[code=c]
foo_next_sub (int const isused[], unsigned int sub)
{
返回下一个合法下标;
返回-1表示没有合法下标
}
foo_backward (int const isused[], unsigned int *i)
{
回溯
}
unsigned int
foo ( int const array[ ], unsigned int n, unsigned int m,
void (*func)(int const buf[ ], unsigned int m)
{
unsigned int count = 0;
int isused [n]= { 全部标记为未使用 };
int buf [m];
unsigned int i = 1;
buf[0] = array[0];
下标为0的元素标记为已使用
while (1)
{
if (i < m)
{
tmp = foo_next_sub (isused, i);
if (tmp < 0)
/* 没有合法下标,回溯 */
foo_backward (isused, &i);
buf[i] = array[tmp];
++i;
}
else
{
计数count 加1;
执行函数func(如打印输出什么或其他功能) // (*func)(buf, m);
把最后一个元素标记为未使用,i回退1;
如果需要,继续回溯;
if (buf[0] > n - m + 1)
/* 如果第一个元素大于 n - m + 1,表示全部列举完了*/
break;
}
}
return count;
}[/code]
我来回复