枚举——完美立方

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 条评论
登录 后参与评论

相关文章

来自专栏小小挖掘机

PySpark之RDD入门最全攻略!

众所周知,Spark的核心是RDD(Resilient Distributed Dataset)即弹性分布式数据集,属于一种分布式的内存系统的数据集应用。Spa...

1.4K6
来自专栏行者悟空

Spark核心数据结构RDD的定义

1984
来自专栏写代码的海盗

spark在yarn-cluster上面执行报错

在单机模式下执行成功的spark程序,在yarn上面就报错。异常信息如下: 1 14/08/14 02:05:42 INFO DAGScheduler: Co...

3055
来自专栏小樱的经验随笔

【BZOJ】初级水题列表——献给那些想要进军BZOJ的OIers(自用,怕荒废了最后的六月考试月,刷刷水题,水水更健康)

BZOJ初级水题列表——献给那些想要进军BZOJ的OIers 代码长度解释一切! 注:以下代码描述均为C++ RunID User Problem Res...

4229
来自专栏别先生

Spark核心RDD、什么是RDD、RDD的属性、创建RDD、RDD的依赖以及缓存、

1:什么是Spark的RDD??? RDD(Resilient Distributed Dataset)叫做分布式数据集,是Spark中最基本的数据抽象,它代...

34610
来自专栏Albert陈凯

3.2 弹性分布式数据集

3.2 弹性分布式数据集 本节简单介绍RDD,并介绍RDD与分布式共享内存的异同。 3.2.1 RDD简介 在集群背后,有一个非常重要的分布式数据架构,即弹性...

38510
来自专栏大数据学习笔记

Spark2.x学习笔记:7、Spark应用程序设计

7、 Spark应用程序设计 7.1 基本流程 1.创建SparkContext对象 每个Spark应用程序有且仅有一个SparkContext对象,封装了...

2488
来自专栏Albert陈凯

Spark详解02Job 逻辑执行图Job 逻辑执行图

Job 逻辑执行图 General logical plan ? GeneralLogicalPlan.png 典型的 Job 逻辑执行图如上所示,经过下面四个...

34811
来自专栏星汉技术

原 荐 Spark框架核心概念

3748
来自专栏王小雷

Spark学习之键值对(pair RDD)操作(3)

Spark学习之键值对(pair RDD)操作(3) 1. 我们通常从一个RDD中提取某些字段(如代表事件时间、用户ID或者其他标识符的字段),并使用这些字段为...

20710

扫码关注云+社区