Lintcode 730 所有子集的和

简介: 已知:给一整数 n, 我们需要求前n个自然数形成的集合的所有可能子集中所有元素的和。示例:给出 n = 2, 返回 6可能的子集为 {{1}, {2}, {1, 2}}. 子集的元素和为 1 + 2 + 1 + 2 = 6给出 n = 3, 返回 24可能的子集为 {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}子集的和为:1 + 2 + 3 + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24思路:其实这更像是一个数学问题,而不是代码问题。

已知

给一整数 n, 我们需要求前n个自然数形成的集合的所有可能子集中所有元素的和。

示例

给出 n = 2, 返回 6
可能的子集为 {{1}, {2}, {1, 2}}. 
子集的元素和为 1 + 2 + 1 + 2 = 6

给出 n = 3, 返回 24
可能的子集为 {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
子集的和为:
1 + 2 + 3 + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24

思路

其实这更像是一个数学问题,而不是代码问题。以4为例子,取一个数,则取1的可能性为1种,取两个数字,则取1的可能性为3种,取三个数字,则取1的可能性为3种,
取四个数字,可能性为1种,则1总共计算了 1+3+3+1 共8次, 其他三个数字也是8次。 所以,结合上面两个示例,很容易可以推的: 当已知n的值时,我们会取里面的每个数字2^(n-1)次

上述分析来源:http://blog.csdn.net/mio_bass/article/details/78797298

根据上述分析,求解的公式就是

公式解析:因为最后把所有子集的所有项累加的表达式里面,1~n的每一个数都有机会出现2^(n-1)次,所以求和表达式就变为:

最终变为上面第一个公式。

利用第一个公式求解就非常方便了。

 

补充:

对于“会取里面的每个数字2^(n-1)次”的另一种解析可以如下进行:

集合里面有1~n共n个元素。构造子集的时候,对每个元素而言都有取或不取两种选择,所以子集数目共有2^(n-1)个。

讨论这些子集:原集合的元素ai只有选和不选两种情况,故所有子集分两类:包含ai的子集和不包含ai的子集。每一类的子集个数都是2^(n-1)个。

所以最后面计算累加和的时候需要累加ai的次数是2^(n-1)次,也就是元素ai对累加和的贡献是ai*2^(n-1)。

每一个元素出现的次数都是2^(n-1)次,所以上述第二个公式即可推出来。

 

代码比较简单就不写了。

 

 

其他参考:

http://blog.csdn.net/zhaohengchuan/article/details/78716365

http://blog.csdn.net/u010005161/article/details/52175525

 

目录
打赏
0
0
0
0
8
分享
相关文章
|
3月前
|
SQL
从合计值倒推出初始日期的极简方法
本文介绍了一种通过计划入库量和入库后库存倒推初始零库存日期的方法,并补充每日入库前的库存(UPDATED_CUSTQTY)。以 2 月 26 日为例,通过逐日倒推计算每条记录的入库前库存,直到找到零或负库存的起始日。传统 SQL 实现复杂,因缺乏天然序号需借助窗口函数。而 SPL 提供更直观的解决方案:加载数据逆序排序、过滤指定日期前记录、循环修改每条记录的入库前库存值,最终返回完整数据,代码简洁高效。
构建高效运维体系:从监控到自动化的全方位实践
在当今信息技术飞速发展的时代,运维作为保障信息系统稳定运行的关键环节,其重要性不言而喻。本文将围绕如何构建一个高效的运维体系进行深入探讨,内容涵盖从监控、日志分析到自动化运维工具的选择与应用,以及在实际工作中的经验和案例分享。通过本文的介绍,读者将能够了解到如何在复杂多变的技术环境中,确保系统的高可用性、高性能和安全性,为业务连续性提供坚实保障。
人工智能:引领未来生活与工作的变革力量
本文探讨了人工智能(AI)在医疗、交通、金融和教育等领域的应用及其带来的变革与前景。从疾病诊断、自动驾驶到个性化学习,AI正深刻改变我们的生活与工作方式。同时,文章分析了AI引发的就业问题、数据安全、隐私保护及伦理法律挑战,并提出通过教育培训、加强监管和完善规范来应对这些难题。总结指出,尽管存在挑战,但AI的未来发展潜力巨大,将为社会带来更高效便捷的服务,引领我们走向更美好的未来。
推荐引擎离线算法与在线算法的探索与实践
推荐引擎是现代互联网产品中至关重要的组成部分。离线算法和在线算法分别负责处理大量数据的预处理和模型训练,以及快速响应用户的实时请求。通过合理的架构设计和算法选择,可以构建出高效且个性化的推荐系统,从而提升用户体验,增加用户满意度和留存率。未来,随着技术的发展,推荐引擎将更加智能化和个性化,为用户提供更加精准的服务。
新技术趋势与应用:探讨新兴技术如区块链、物联网、虚拟现实等的发展趋势和应用场景
【9月更文挑战第5天】随着科技的飞速发展,新兴技术如区块链、物联网、虚拟现实等正在改变我们的生活。本文将探讨这些技术的发展趋势和应用场景,以及它们如何影响我们的生活和工作。我们将通过实例和代码示例来深入了解这些技术的发展和应用。
107 5
142 推荐系统架构(淘宝和京东)
142 推荐系统架构(淘宝和京东)
323 0
IEEE SLT 2022论文解读|基于多帧跨通道注意力机制的多说话人语音识别
‍近期,阿里巴巴达摩院高校AIR合作论文“MFCCA:Multi-frame cross-channel attention for multi-speaker ASR in multi-party meeting scenario”被IEEE SLT 2022接收。该论文考虑到麦克风阵列不同麦克风接收信号的差异,提出了一种多帧跨通道注意力机制,该方法对相邻帧之间的跨通道信息进行建模,以利用帧级和通道级信息的互补性。
1064 0
外骨骼机器人混战:程天科技做“深”,傅利叶智能做“广”
外骨骼机器人商用范围愈加广泛,产业发展不断提速。
151 0
《云上新势力 CLOUD IMAGINE》——Part 2 演讲/文章合集——文章7:《基于倚天的视频云原生业务新范式》(2)
《云上新势力 CLOUD IMAGINE》——Part 2 演讲/文章合集——文章7:《基于倚天的视频云原生业务新范式》(2)
231 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等