石榴姐的小迷弟 2015-12-22 04:23 采纳率: 0%
浏览 2618

求大神指导调用递归函数中的栈是怎么运行的

回溯法与树的遍历
回溯法:其求解过程实质是一个先序遍历一棵“状态树”的过程,只是这棵树不是遍历前预先建立的,而

是隐含在遍历过程中。

题目描述:求含n个元素的集合的幂集。

例:A={1,2,3},则A的幂集为{{1,2,3},{1,2},{1, 3},{2,3},{1},{2},{3},{}}

解题思路:求幂集的过程可看成是依次对集合A中的元素进行取或舍的过程。

  1.   选择合适的数据结构——假设以线性表表示集合。
    
  2.   树根结点表示幂集元素的初始状态(空集),叶子结点表示终结状态(幂集的元素),第i层表
    

示已对前i-1个元素进行了取舍的当前状态

编码:

#include "stdafx.h"
#include< iostream.h>

#define N 10

typedef struct
{
int data[N];
int length;
}SqList;

//输出线性表B
void Output(SqList& B)
{
int i;
if(B.length ==0)
cout<<"空集\n";
else
{
for(i=0;i<B.length ;i++)
cout<<B.data [i]<<"\t";
cout<<endl;
}

}

//求集合A的幂集,其中B为暂存幂集元素的线性表,i表示从第i个元素开始取舍,当
//i>n时则求得幂集的一个元素,并输出
void GetPowerSet(int i,SqList A,SqList& B)
{
int x,k,j;
if(i>=A.length )
Output(B);
else
{
x=A.data [i];
k=B.length ;
B.data [k]=x;
B.length ++;
GetPowerSet(i+1,A,B);
B.length --;
GetPowerSet(i+1,A,B);
}
}
A={1,2,3},则A的幂集为{{1,2,3},{1,2},{1, 3},{2,3},{1},{2},{3},{}}

int main(int argc, char* argv[])
{
SqList A,B;
int i;
cout<<"输入A集合的元素个数\n";
cin>>A.length ;
cout<<"输入A集合的元素\n";
for(i=0;i cin>>A.data [i];
B.length =0;
GetPowerSet(0,A,B);

return 0;
}

我不解的是第一次执行完output函数后该怎么办,如果继续执行下面的语句,即b.length--和递归函数,那第二次输出的集合显然与答案不符,求大神指点,我记得老师说过还有什么出栈的过程,求指导

  • 写回答

4条回答 默认 最新

  • lm_whales 2015-12-22 05:51
    关注

    1)输出的结果,并不是{{1,2,3},{1,2},{1, 3},{2,3},{1},{2},{3},{}}
    虽然 幂集的每个子集都是对的,但是输出顺序并非这个顺序。
    2)并非每次递归调用都会输出
    3) 输出和不输出之间,递归的步数,并非一致的

    评论

报告相同问题?

悬赏问题

  • ¥50 swiftui @query 报错
  • ¥50 怎么解决刷卡或扫码后,点击软件输入框,win10屏幕键盘不会自动弹出的问题
  • ¥15 如何使用arcgispro的训练深度模型,发现water和nowater精度为0?(相关搜索:深度学习)
  • ¥20 matlab作业不太懂呀有问题能给个代码吗
  • ¥15 自制电路图为何无法驱动ESP01S?
  • ¥15 前端加access数据库
  • ¥15 ARCGIS 多值提取到点 ERROR 999999
  • ¥15 mysql异常断电, [MY-011971] [InnoDB]
  • ¥15 uni.onBluetoothDeviceFound熄屏不运行
  • ¥15 求PHDA糖尿病并发症数据集,有偿