免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2999 | 回复: 5

[C] C实现多个数组选元素的组合迭代回溯的问题 [复制链接]

论坛徽章:
0
发表于 2013-06-02 21:46 |显示全部楼层
20可用积分
本帖最后由 pp1984829 于 2013-06-02 21:47 编辑



如图二维数组
@a = {
(a,b,c,d,e)
(f,g,h,i,j,k)
(l,m,n,o,p)
(q,r,s,t,u)
(v,w,x,y,z)
}

题目是从二维数组的每一行的数组中选出一个元素,列举出所有的组合方式.
例如可行组合(a,f,l,q,v),(b,h,o,s,z)等。
现在我用递归回溯的算法解出了答案,但是遇到很比较大的数组时效率很低,想求迭代回溯的实现方法提高效率。@a二维数组是我列举的例子,实际场景中二维数组的元素个数未知为n.

类似于这个C的题目:从m个数里面选择n个数的组合


41@YRM7GZK77N`$FJWN3}6Q.jpg














五、回溯法   

    回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。






希望高手能出手,给出迭代回溯的代码,非常感谢!

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2013-06-03 08:39 |显示全部楼层
每行有5个元素,共有5行,所以一共有5^5=3125种组合方式
所以代码简单,如下
  1. for( size_t i=0; i<3125; ++i )
  2. {
  3.     int r0 = i/625%5;
  4.     int r1 = i/125%5;
  5.     int r2 = i/25%5;
  6.     int r3 = i/5%5;
  7.     int r4 = i/1%5;
  8.     // 以上代码当然可以用一个for循环来做

  9.     printf( "%d %d %d %d %d\n", buf[0][r0], buf[0][r1], buf[0][r2], buf[0][r3], buf[0][r4] );
  10. }
复制代码

论坛徽章:
0
发表于 2013-06-03 08:59 |显示全部楼层
回复 2# bruceteen

非常感谢您的答复,但是实际场景中二维数组的元素数是不确定的,所有就没有办法知道到底用几个for循环,所以需要迭代回溯,动态规划的那种。


   

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2013-06-03 09:22 |显示全部楼层
pp1984829 发表于 2013-06-03 08:59
回复 2# bruceteen
非常感谢您的答复,但是实际场景中二维数组的元素数是不确定的,所有就没有办法知道到底用几个for循环,所以需要迭代回溯,动态规划的那种。

你到底看了我的代码没有? 哪来的“几个for循环”?

论坛徽章:
0
发表于 2013-06-03 10:01 |显示全部楼层
回复 4# bruceteen

好吧,我看错了,但是我还是想要迭代回溯的代码,不过还是谢谢你。


   

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2013-06-03 11:54 |显示全部楼层
递归本来就慢, 没办法的.

你可以手写解开1-2层递归, 可以缩减递归的次数.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP