枚举——完美立方

1. 枚举

枚举是基于逐个尝试答案的一种问题求解策略。

2. 完美立方

形如a3=b3+c3+d3a^3 = b^3 + c^3 + d^3的等式被称为完美立方等式。例如123=63+83+10312^3 = 6^3 + 8^3 + 10^3

问题:编写程序,对任给的正整数N(N<=100),寻找所有的四元组(a, b, c, d),使得a3=b3+c3+d3a^3 = b^3 + c^3 + d^3,其中a,b,c,d大于1,小于等于N,且b<=c<=d。

输入:一个正整数N(N<=100)。 输出:每行输出一个完美立方。输出格式为Cube = a,Triple = (b, c, d)。

求解:

备注:判断条件边界很重要

  • 方法一:
#!/usr/bin/env python
# _*_ coding: utf-8 _*_


import sys
import math

# n = sys.argv[1]
n = 24

i = 0
for a in xrange(2, n + 1):
    for b in xrange(2, n):
        for c in xrange(b, n):
            for d in xrange(c, n):
                i += 1
                if math.pow(a, 3) == math.pow(b, 3) + math.pow(c, 3) + math.pow(d, 3):
                    print 'Cube = %d, Triple = (%d, %d, %d)' % (a, b, c, d)
print '%d iterations.' % i
  • 输出
Cube = 6, Triple = (3, 4, 5)
Cube = 12, Triple = (6, 8, 10)
Cube = 18, Triple = (2, 12, 16)
Cube = 18, Triple = (9, 12, 15)
Cube = 19, Triple = (3, 10, 18)
Cube = 20, Triple = (7, 14, 17)
Cube = 24, Triple = (12, 16, 20)
46552 iterations.
  • 方法二
#!/usr/bin/env python
# _*_ coding: utf-8 _*_


import sys
import math

# n = sys.argv[1]
n = 24

i = 0
for a in xrange(2, n + 1):
    for b in xrange(2, a):
        for c in xrange(b, a):
            for d in xrange(c, a):
                i += 1
                if math.pow(a, 3) == math.pow(b, 3) + math.pow(c, 3) + math.pow(d, 3):
                    print 'Cube = %d, Triple = (%d, %d, %d)' % (a, b, c, d)
print '%d iterations.' % i
  • 输出
Cube = 6, Triple = (3, 4, 5)
Cube = 12, Triple = (6, 8, 10)
Cube = 18, Triple = (2, 12, 16)
Cube = 18, Triple = (9, 12, 15)
Cube = 19, Triple = (3, 10, 18)
Cube = 20, Triple = (7, 14, 17)
Cube = 24, Triple = (12, 16, 20)
12650 iterations.

从上面可以看出枚举的边界不同,效率会差将近三倍。

Python源码地址:https://github.com/SnailTyan/programming-and-algorithms/blob/master/perfect_cubes.py

C++源码地址(已在POJ上Accepted):https://github.com/SnailTyan/programming-and-algorithms/blob/master/perfect_cubes.cpp

参考资料

  1. 程序设计与算法(二)算法基础

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云计算D1net

Rackspace考虑退出云领域

近期,Bloomberg新闻上发布了一条值得玩味的消息——Rackspace着眼于未来的“战略抉择”聘请了Morgan Stanley。Rackspace在云基...

3446
来自专栏大数据技术学习

大数据实用数据分析方法

波特的五种竞争力分析模型被广泛应用于很多行业的战略制定。波特认为在任何行业中,无论是国内还是国际,无论是提供产品还是提供服务,竞争的规则都包括在五种竞争力量内。...

1635
来自专栏SDNLAB

边缘计算和雾计算如何改变IoT的应用方式

关注科技领域很难跟上行业的最新趋势和新兴领域,仅以计算类型为例,随着我们处理数据的方式和位置的不断变化,我们受到了硬件和连接性方面的限制。 云计算这一术语已经在...

31610
来自专栏吉浦迅科技

您的AI产品从设想到原型就差一个Jetson TX2模组的距离

在人工智能大热的当下,拥有强大计算能力的NVIDIA走上了发展的快车道,公司Slogan也变成了“引领人工智能计算”。 凭借着在GPU领域的深耕,NVI...

4457
来自专栏SAP最佳业务实践

从SAP最佳业务实践看企业管理(115)-采购过程-询报价

image.png 报价单申请(RFQ)和报价单 通过向供应商发出报价单申请,由供货商提供报价单。报价单包括供货商提供的特定物料和服务的价格、条件以及附加信息...

3236
来自专栏腾讯大数据的专栏

大数据产品-腾讯信鸽之手游流失预测

背景 随着游戏市场竞争的日趋激烈,越来越多的游戏运营服务选择借助大数据挖掘出更多更细的用户群来进行精细化,个性化运营,从而更好的抓住用户,获得更大的收益。在游戏...

2905
来自专栏数据猿

【案例】渤海银行——在线业务自动化信用审核

1703
来自专栏人工智能头条

基于腾讯信鸽平台的手游流失用户预测模型概览

17510
来自专栏区块链大本营

BTA | 康烁:基于linux的挖矿操作系统

3125
来自专栏大数据挖掘DT机器学习

【方法】会员分层和顾客忠诚度分析

忠诚用户不仅能为网站创造持续的价值,同时也是网站品牌口碑推广的重要渠道,所以目前网站对忠诚用户愈加重视。可能很多网站或者网站分析工具对用户做了“新用...

2975

扫码关注云+社区