算法作业:求一个集合中所有子集元素之和 | 您所在的位置:网站首页 › 集合的所有子集的元素 › 算法作业:求一个集合中所有子集元素之和 |
问题描述:
求一个集合中所有子集元素之和。如{1,2,3,4,5,6,7,8,9,10……n} 算法分析:由于集合中元素具有无序性, 所以集合中每个元素在子集中出现的次数是相同的。这样的话,问题就简单了,求所有子集元素的和就可以简化为求每个元素在子集中出现的次数*全集中所有元素的和。全集中所有元素的和好求,就是n*(n+1)/2。 集合中任何一个元素出现的次数,比如1,我们可以这样来求: 首先一个集合的子集个数是2n,这个都学过,我就不推导了。 我们想求 1 出现 的次数,不好求,我们可以转化为求 1 不出现的次数,1 不出现的次数就是原来集合中除了元素 1 的元素的集合的子集个数。不明白??举个例子 {1,2,3,4}这个集合子集的个数是24,除去 1 之后集合就变为 {2,3,4}这个集合的子集个数是23,也就是说只有这些集合中没有 1 ,我们想求的 1 出现的个数就是24-23 所以在含n个元素的集合中,任何一个元素在子集中出现的次数就是2n-2n-1=2n-1 所以集合中所有元素之和sum=(n*(n+1)/2)*(2n-1) 代码实现:![]() } ![]() 博主ma6174对本博客文章(除转载的)享有版权,未经许可不得用于商业用途。转载请注明出处http://www.cnblogs.com/ma6174/ 对文章有啥看法或建议,可以评论或发电子邮件到[email protected] 本文转自ma6174博客园博客,原文链接:http://www.cnblogs.com/ma6174/archive/2012/03/03/2378095.html ,如需转载请自行联系原作者 |
CopyRight 2018-2019 实验室设备网 版权所有 |