枚举——生理周期

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

相关文章

来自专栏菩提树下的杨过

MSDN官方的ASP.Net异步页面的经典示例代码

示例1.演示异步获取一个网址的内容,处理后显示在OutPut这一Label上 using System; using System.Web; using S...

2115
来自专栏跟着阿笨一起玩NET

去除DataTable中重复字段

               DataTable tbl = new DataTable();                 tbl.Columns.Add(...

801
来自专栏菩提树下的杨过

winform中linkLabel的用法(示例)

private void Form1_Load(object sender, EventArgs e)         {             this...

1965
来自专栏xingoo, 一个梦想做发明家的程序员

windows程序设计-第四章 system1.c

/*---------------------------------------------------- SYSMETS1.C -- System M...

26010
来自专栏谈补锅

记录C#常用的代码片段

using Newtonsoft.Json; using Newtonsoft.Json.Linq;

1142
来自专栏听雨堂

想修改CSS

      下载了一个“通用”的CSS文件,本来想偷懒的,结果发现有问题,就是它用的颜色是变量定义的,无法识别。我又找不到在哪里可以定义。 BODY{     ...

22010
来自专栏跟着阿笨一起玩NET

[C#]工具类—FTP上传下载

  不错的文章:http://www.cnblogs.com/greatverve/archive/2012/03/03/csharp-ftp.html

1531
来自专栏c#开发者

jquery easyui datagrid mvc server端分页排序筛选的实现

1自定义一个ModelBinder public class filterRule { public string field { g...

4239
来自专栏c#开发者

C# : row-clickable GridView and get and set gridview rows using JavaScript

Complete C# code: ---------------- using System; using System.ComponentModel; ...

3126
来自专栏我和未来有约会

silverlight向服务器post数据类

using System; using System.Net; using System.Windows; using System.Windows.Co...

2055

扫码关注云+社区