| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 834 人关注过本帖
标题:[求助]请教一个算法或程序
只看楼主 加入收藏
peterico
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-11-24
收藏
 问题点数:0 回复次数:11 
[求助]请教一个算法或程序


有如下问题:

输入一个任意正整数n,由小于该整数的所有非负整数构成的一个数列{0,1,2,3,n-1},
要求输出该数列的所有子集。
例如:输入3
即要输出:{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}

请指点,谢谢!

搜索更多相关主题的帖子: 算法 整数 
2006-11-24 00:55
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
应该是组合问题

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2006-11-24 15:40
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 

回朔可以吧,效率很低.
a[i]=1;表示i被选中.
a[i]=0表示i没有被选种.
void Backtract(int t)
{
if(t>n)
{
判断输出a[i]中为1的i.
}
for(int i=0;i<n;i++)
{
a[t]=i;
if(当前i与前面被选中要大)
Backtract(t+1);
}
}


倚天照海花无数,流水高山心自知。
2006-11-24 17:18
qqlilichong
Rank: 1
等 级:新手上路
帖 子:18
专家分:0
注 册:2006-11-20
收藏
得分:0 
很难的问题,我也很想知道答案.
2006-11-24 20:09
peterico
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2006-11-24
收藏
得分:0 

斑竹的算法我有点晕:)
此题为应聘软件工程师的一道笔试题,我把它列出来,请大家多出出主意,有没有更好的容易理解的算法/


海阔凭你跃,天高任我飞: http://peterico./
2006-11-26 14:06
我不是郭靖
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:494
专家分:6
注 册:2006-10-4
收藏
得分:0 

列出所有子集的方法有很多

下边介绍一种用二进制对应关系列出所有字集的方法:
拿{1,2,3}为例

{} 对应000 //0表示不在集合中,1表示在
{1} 对应100
{2} 010
{3} 001
{1,2} 110
{1,3} 101
{2,3} 011
{1,2,3} 111

所以{1,2,3}的所有字集与3位二进制数是对应的.
也即产生二进制数,就可以产生所有字集.



2006-11-26 14:51
剑风曲
Rank: 1
等 级:新手上路
帖 子:69
专家分:0
注 册:2006-11-16
收藏
得分:0 
我很喜欢6楼的方法~~~~~很好的方法~~实现起来也简单~
2006-11-26 16:28
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
像楼上一样的,回朔法就是这个样子.

倚天照海花无数,流水高山心自知。
2006-11-26 16:29
剑风曲
Rank: 1
等 级:新手上路
帖 子:69
专家分:0
注 册:2006-11-16
收藏
得分:0 
斑竹的代码偶看是看懂了,不过我自己实现的时候没用回朔.
用了一个十进制转二进制的方法(带余除2).
cin>>n;
for(i=0;i<2^n;i++){//每次循环为一个子集
while(i){
if(i%2)cout<<t;
t++;
i=i/2;
}//用二进制判断
}

实现里面2^n可以用循环写
2006-11-26 16:47
我不是郭靖
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:494
专家分:6
注 册:2006-10-4
收藏
得分:0 
以下是引用剑风曲在2006-11-26 16:47:08的发言:


实现里面2^n可以用循环写

2^n 就是 1<<n


2006-11-26 17:08
快速回复:[求助]请教一个算法或程序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.039315 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved