回 帖 发 新 帖 刷新版面

主题:求助,组合问题。从n个数中选出m个数的全部组合。新手求指导。

如题。用递归算法,自己想了老半天还是没有一点头绪。求算法思想,无代码也可。

回复列表 (共1个回复)

沙发

[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]

我来回复

您尚未登录,请登录后再回复。点此登录或注册