枚举——完美立方

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. 枚举

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

2. 完美立方

形如$a^3 = b^3 + c^3 + d^3$的等式被称为完美立方等式。例如$12^3 = 6^3 + 8^3 + 10^3$

问题:编写程序,对任给的正整数N(N<=100),寻找所有的四元组(a, b, c, d),使得$a^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)。

求解:

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

  • 方法一:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/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
  • 输出
1
2
3
4
5
6
7
8
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.
  • 方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/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
  • 输出
1
2
3
4
5
6
7
8
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,记得给个star。

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

参考资料

  1. 程序设计与算法(二)算法基础
如果有收获,可以请我喝杯咖啡!