枚举——完美立方

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

相关文章

来自专栏DevOps时代的专栏

特性分支与特性开关哪家强?

分支管理策略对一个研发团队发布高质量的软件至关重要。在本文中,我们将探讨同一代码库中多任务并行开发时的解决方案,以及它们之间的优缺点。一般意义上来说冲突合并成本...

93300
来自专栏西安-晁州

TortoiseGit记住用户名&密码

配置并安装好git之后鼠标右键: ? ? 在全局配置文件末尾添加一行: [credential]       helper = store *主意保存时以utf...

26200
来自专栏运维前线

win10+hexo+github搭建个人博客

win10+hexo+github搭建个人博客 参考:https://hexo.io/,博客用于记录自己的学习工作历程 参考以下步骤安装 1、搭建环境准...

30660
来自专栏漫漫深度学习路

git 常用流程

git 常用流程 关于 ssh key 第1步:创建SSH Key。在用户主目录下,看看有没有.ssh目录,如果有,再看看这个目录下有没有id_rsa和id_r...

22650
来自专栏IMWeb前端团队

hexo 博客利用 github 分支同步源文件

hexo 是一个优秀的静态博客工具,唯一的不足就是源文件无法同步,让人几乎只能在一台电脑上写博客,为了解决这个问题,我们可以使用 Github 来管理我们...

291100
来自专栏梦里茶室

git/github 笔记

2016-1-9 创建github repos并提交修改 在[这里](https://github.com/new)创建一个repos, 进入终端,cd到一个...

22390
来自专栏IMWeb前端团队

Git 介绍

一,理解 Git 1,分布式版本控制 Git 版本控制系统的设计思想是"去中心化"。传统的 CVS 、SVN 等工具采用的是 C/S 架构,只有一个中心代码仓库...

22380
来自专栏运维前线

使用Gitlab创建git项目

使用Gitlab创建git项目 登录gitlab系统,访问自己的gitlab.example.com,然后使用gitlab用户,登录 ? 第一次登录需要重新修改...

1.9K80
来自专栏运维前线

实现Shell脚本自动备份Gitlab档案并同步到远程

实现脚本自动备份Gitlab档案并同步到远程 参考:Gitlab的备份与恢复 Gitlab服务器与备份服务器进行密钥配对,免密使用scp传输Gitlab备...

53260
来自专栏社区的朋友们

Git 的基本操作、开发流程、实用技巧总结

Git 仓库主要是由是三部分组成:本地代码,缓存区,提交历史,这几乎是所有操作的本质,但是为了文章更加简单易懂,就不围绕这块展开了,有兴趣的可以去了解下。

1.5K30

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励