枚举——生理周期

1. 枚举

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

2. 生理周期

  • 问题描述 人有体力、情商、智商的高峰日子,它们分别每隔23天、28天和33天出现一次。对于每个人,我们想知道何时三个高峰落在同一天。给定三个高峰出现的日子p,e和i(不一定是第一次高峰出现的日子),再给定另一个指定的日子d,你的任务是输出日子d之后,下一次三个高峰落在同一天的日子(用距离d的天数表示)。例如:给定日子为10,下次出现三个高峰同一天的日子是12,则输出2。
  • 输入 输入四个整数:p,e,i和d。p,e,i分别表示体力、情感和智力高峰出现的日子。d是给定的日子,可能小于p,e或i。所有给定日子是非负的并且小于或等于365,所求的日子小于或等于21252。
  • 输出 从给定日子起,下一次三个高峰同一天的日子(距离给定日子的天数)。
  • 输入样例 0 0 0 0 0 0 0 100 5 20 34 325 4 5 6 7 283 102 23 320 203 301 203 40 -1 -1 -1 -1 四个-1表示输入结果,四个数字分别表示p,e,i,d。
  • 输出样例 Case 1: the next triple peak occurs in 21252 days. Case 2: the next triple peak occurs in 21152 days. Case 3: the next triple peak occurs in 19575 days. Case 4: the next triple peak occurs in 16994 days. Case 5: the next triple peak occurs in 8910 days. Case 6: the next triple peak occurs in 10789 days.
  • 解法一
#!/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

参考资料

  1. 程序设计与算法(二)算法基础

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏思考的代码世界

Python编程从入门到实践之条件判断|第4天

在日常开发中需要用到如果怎么样就怎么样,否则就怎么样的逻辑。主要采用if语句来实现的。

3507
来自专栏企鹅号快讯

编码,深浅copy

encode,decode在python2中使用的一些迷糊,python3中更容易理解 要理解encode和decode,首先我们要明白编码,字符和二进制的相关...

3196
来自专栏技术之路

c++基础 使用智能指针

三个智能指针模板(auto_ptr、unique_ptr和shard_ptr)都定义了类似指针的对象(c++11已将auto_ptr摒弃),可以将new获得(直...

1745
来自专栏软件开发 -- 分享 互助 成长

快速排序

如果说希尔排序是简单插入排序的升级,堆排序是简单选择排序的升级,那么快速排序就是冒泡排序的升级了。相对于冒泡排序,快速排序增大了记录比较和移动的距离,将关键字较...

1866
来自专栏苦逼的码农

Unicode与UTF-8的区别

要弄清Unicode与UTF-8的关系,我们还得从他们的来源说起,下来我们从刚开始的编码说起,直到Unicode的出现,我们就会感觉到他们之间的关系

1192
来自专栏企鹅号快讯

Python数据类型之字典

大家好 今天我们来共同探讨 Python的另外一种数据类型 字典 技术要点: 字典的定义 字典的基本使用 字典的特性 对于常规字典的定义 相信大家应该很熟悉 常...

35814
来自专栏鬼谷君

python datetime模块用strftime 格式化时间

471
来自专栏zhisheng

干货分享:让你分分钟学会 javascript 闭包 一像素

闭包,是 javascript 中重要的一个概念,对于初学者来讲,闭包是一个特别抽象的概念,特别是ECMA规范给的定义,如果没有实战经验,你很难从定义去理解它。...

3315
来自专栏fangyangcoder

leetcode(一)

问题描述看图1,大致意思是最初自己手上是没有任何钱,一杯柠檬水5刀,买家有三种给法(5,10,20),在给定的input,也就是money的序列,问你是否找的开...

962
来自专栏java学习

面试题19(关于return的用法)

执行下列代码的输出结果是? public class Demo { public static void main(String args[]) { int...

2864

扫码关注云+社区