算法技能树2-蓝桥杯-python实现测试次数(摔手机)-动态规划(DP)

2021/12/21 11:20:00

本文主要是介绍算法技能树2-蓝桥杯-python实现测试次数(摔手机)-动态规划(DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 1、题目描述
  • 2、python解题
  • 1、知识点总结

1、题目描述

x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。
x星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。
特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n
为了减少测试次数,从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?

2、python解题

n = 1000
i = 0
f2 = [0]*105
f3 = [0]*105

while f3[i] < n:
    i += 1
    f2[i] = f2[i-1] +i
    f3[i] = f3[i-1] +f2[i-1] + 1
print(i)

运行结果:
在这里插入图片描述

1、知识点总结

动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。(来源于百度)



这篇关于算法技能树2-蓝桥杯-python实现测试次数(摔手机)-动态规划(DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程