考试网 >> IT认证 >> 等级 >> 等级动态 >> 常用算法设计方法3

发布时间：2006-07-25 12:02     点击：

N

Y

N

Y

N

N

Y

Y

建立根结点root

建立root的第一个孩子结点node

建树完毕？

Node是叶子？

Node是解？

处理解

回溯node=parent(node)

Node还有孩子？

建立node的孩子结点node=parent(node)

建立node的孩子结点node=parent(node)

结束

开始

    在用回溯法求解问题，也即在遍历状态空间树的过程中，如果采用非递归方法，则我们一般要用到栈的数据结构。这时，不仅可以用栈来表示正在遍历的树的结点，而且可以很方便地表示建立孩子结点和回溯过程。

    例如在组合问题中，我们用一个一维数组Stack[ ]表示栈。开始栈空，则表示了树的根结点。如果元素1进栈，则表示建立并遍历（1）结点；这时如果元素2进栈，则表示建立并遍历（1，2）结点；元素3再进栈，则表示建立并遍历（1，2，3）结点。这时可以判断它满足所有约束条件，是问题的一个解，输出（或保存）。这时只要栈顶元素（3）出栈，即表示从结点（1，2，3）回溯到结点（1，2）。

【问题】       组合问题

    问题描述：找出从自然数1，2，…，n中任取r个数的所有组合。

    采用回溯法找问题的解，将找到的组合以从小到大顺序存于a[0]，a[1]，…，a[r-1]中，组合的元素满足以下性质：

（1）       a[i+1]>a[i]，后一个数字比前一个大；

（2）       a[i]-i<=n-r+1。

    按回溯法的思想，找解过程可以叙述如下：

【程序】

# define   MAXN    100

int a[MAXN];

void comb(int m,int r)

{     int i,j;

       i=0;

       a[i]=1;

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。