枚举——完美立方

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

相关文章

来自专栏锦小年的博客

python学习笔记6.7-简化数据结构的初始化过程

我们每编写一个类的时候都需要编写一个初始化函数,那么如果编写的类当做数据结构来用,它们的初始化结构就是一样的,例如: class Stock: def ...

1856
来自专栏柠檬先生

你不知道的javaScript笔记(3)

对象 对象可以通过两种形式定义: 声明形式和构造形式 声明形式语法: var myObj = {key:value} 构造形式语法: var myObj = n...

1755
来自专栏我的博客

安卓开发之SQLite数据库操作

一、SQLiteDatabase对象 获取SQLiteDatabase对象可以使用SQLiteOpenHelper或者使用静态方法获取(具体内容可以参考开发手册...

33512
来自专栏我是业余自学C/C++的

链栈 原

链栈就是栈结构的链表形式。其他的操作和数组表示栈一摸一样。 下面是具体的代码实现:

651
来自专栏码匠的流水账

java字符全角半角转换

371
来自专栏猛牛哥的博客

OD条件与消息断点的设置方法

1414
来自专栏Albert陈凯

2018-08-23 Java工具类——全角半角字符相互转换

https://blog.csdn.net/xyw591238/article/details/51719747 https://my.oschina.net...

621
来自专栏happyJared

IDEA快捷键拆解系列(六):Code篇

  以下是关于Code导航项及其每一子项的拆解介绍,其中,加粗部分的选项是博主认为比较重要的。

662
来自专栏开发与安全

数据结构:栈的顺序存储结构

栈(stack)是限定在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom) ,栈又称为后进先出(Las...

3316
来自专栏SpringBoot

javabean 遍历

842

扫码关注云+社区