枚举——生理周期

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

相关文章

来自专栏ml

HDUOJ-----4506小明系列故事——师兄帮帮忙

小明系列故事——师兄帮帮忙 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3276...

2727
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第8章 函数式编程(FP)(1)第8章 函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

702
来自专栏数据结构与算法

6261:汉诺塔问题

6261:汉诺塔问题 总时间限制: 1000ms 内存限制: 65536kB描述 约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的...

3445
来自专栏菜鸟程序员

Java中在特定区间产生随机数

492
来自专栏尾尾部落

[LeetCode]Max Area of Island 岛屿的最大面积 [LeetCode]Max Area of Island 岛屿的最大面积

链接:https://leetcode.com/problems/max-area-of-island/description/ 难度:Easy 题目:69...

1042
来自专栏后端技术探索

常见算法面试题

这几天在网上看到一篇关于算法面试题的博客,归纳的很好,有不少经典的题目,大部分来自《编程珠玑》、《编程之美》、《代码之美》三本书。这里给出书上的解答以及一些思考...

562
来自专栏C语言及其他语言

第一个 C 语言编译器是怎样编写的?

作者: 伯乐在线 - Chaobs 网址: http://blog.jobbole.com/94311/ 首先向C语言之父Dennis Ritchie致敬! ...

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

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

2176
来自专栏算法channel

LeetCode实战:子问题分析

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 记...

3329
来自专栏懒人开发

(1)James Stewart Calculus 5th Edition:Functions and Models

893

扫码关注云+社区