枚举是基于逐个尝试答案的一种问题求解策略。
#!/usr/bin/env python
# _*_ coding: utf-8 _*_
input_data = [[0, 0, 0, 0],
[0, 0, 0, 100],
[5, 20, 34, 325],
[4, 5, 6, 7],
[283, 102, 23, 320],
[203, 301, 203, 40]]
max_days = 21252
p_circle = 23
e_circle = 28
i_circle = 33
for data in input_data:
p = data[0]
e = data[1]
i = data[2]
d = data[3]
for day in xrange(d + 1, max_days + 1):
if abs(day - p) % p_circle == 0 and abs(day - e) % e_circle == 0 and abs(day - i) % i_circle == 0:
print 'the next triple peak occurs in %d days.' % (day - d)
break
the next triple peak occurs in 21252 days.
the next triple peak occurs in 21152 days.
the next triple peak occurs in 19575 days.
the next triple peak occurs in 16994 days.
the next triple peak occurs in 8910 days.
the next triple peak occurs in 10789 days.
executed in 32ms
分析:遍历每一天,得出最终的解。
#!/usr/bin/env python
# _*_ coding: utf-8 _*_
input_data = [[0, 0, 0, 0],
[0, 0, 0, 100],
[5, 20, 34, 325],
[4, 5, 6, 7],
[283, 102, 23, 320],
[203, 301, 203, 40]]
max_days = 21252
p_circle = 23
e_circle = 28
i_circle = 33
for data in input_data:
p = data[0]
e = data[1]
i = data[2]
d = data[3]
circles = (max_days - i) // i_circle
for circle in xrange(1, circles + 1):
day = i + i_circle * circle
if (day - p) % p_circle == 0 and (day - e) % e_circle == 0:
print 'the next triple peak occurs in %d days.' % (day - d)
break
the next triple peak occurs in 21252 days.
the next triple peak occurs in 21152 days.
the next triple peak occurs in 19575 days.
the next triple peak occurs in 16994 days.
the next triple peak occurs in 8910 days.
the next triple peak occurs in 10789 days.
executed in 17ms
分析:其实中间有许多日子可以跳过。
总结:虽然枚举就是一个个去尝试,但在求解问题时往往不需要尝试每一个可能。通过一些逻辑可以合理的避免一些无用的尝试。从时间上也可以看出时间节省了大约一半。
源码地址:https://github.com/SnailTyan/programming-and-algorithms/blob/master/physical_period.py