注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

【转载】求数组的真子集  

2012-10-04 20:19:31|  分类: 简单常见算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自bdgboss《求数组的真子集》
根据http://topic.csdn.net/u/20080419/23/d9beda9f-4b71-426e-8017-e9ffdfea0fa0.html 二楼的注释,使我对这个问题有了很清醒的认识,之前的想法是n个指针不断的循环,后来怎么也想不出解决方法了。

节选:
/*假设这个集合有 3个数 a b c那么它就对应一个 3位的2进制数
我们可以把它这些子集分别对应一个二进制数
子集 空集 {c}, {b}, {c,b}, {a}, {a,c}, {a,b},{a,b,c}
对应的2进制数 000, 001, 010, 011, 100, 101, 110, 111*/

不得不说能想出这个方法的人太聪明了,刚看到这个思路,赞叹不已,巧夺天工。
建立一个二进制,而后二进制循环加一,二进制的每一位分别对应着数组的每一个数,1代表有,0代表没有。

起初傻到这种程度:建立个二进制数,对二进制循环加一,写个方法判断二进制的每一位字节是0还是1。我晕 竟然有这样糟糕的想法。后来在网上找资料,怎么也找不到,才知道此方法不可。
而后我做了点改进方法大致类似:
假设数组有4个元素分别为a,b,c,d,在这里我需要一个4位的二进制数,0000,0001,0010,0011……,1111,其中二进制的最高位代表a,次高位代表b,第三位代表c,最低位代表d。1表示yes,0表示no,0000则表示空集,0001表示集合{d},0011表示集合{c,d},1101表示集合{a,b,d},1111表示集合{a,b,c,d}。至于二进制数的累加我想了个方法,1表示0001,2表示0010,3表示0011,4表示0100,以此类推1111就用15表示,而后用10进制转换2进制的方法例。
算法的具体实现在我的“破解平方数”一文中有体现,在此就不写了。
  评论这张
 
阅读(122)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017