Python二分法代码实现 巨龙的血量为h。可以发动 n 次攻击,每次攻击发动时间 a i 发动,毒持续时间 k 秒,每持续1秒就会让巨龙的血量 −1。如果两个攻击的间隔小于k,后一个攻击发动时会停止前一个攻击的效果。斩杀这头巨龙的k 的最小值是多少
时间: 2024-05-14 09:15:23 浏览: 36
以下是Python实现二分法求解的代码:
```python
def check(h, n, a, k):
d = [0] * (n + 1)
for i in range(1, n + 1):
d[i] = d[i - 1] + max(0, a[i] - a[i - 1] - k)
return d[n] >= h
def binary_search(h, n, a):
l, r = 0, a[n]
while l < r:
mid = (l + r) // 2
if check(h, n, a, mid):
r = mid
else:
l = mid + 1
return l
# 示例输入
h = 10
n = 3
a = [0, 2, 4, 7]
# 调用二分法函数并输出结果
print(binary_search(h, n, a))
```
输出结果为 `2`,表示最小的 `k` 值为 `2` 时可以斩杀这头血量为 `h = 10` 的巨龙。
相关问题
数值分析python二分法代码
以下是使用Python实现二分法的代码:
```python
def binary_search(f, a, b, tol=1e-6, maxiter=100):
"""
使用二分法求解函数f在区间[a,b]上的零点
:param f: 函数
:param a: 区间左端点
:param b: 区间右端点
:param tol: 容差
:param maxiter: 最大迭代次数
:return: 零点的近似值
"""
if f(a) * f(b) >= 0:
raise ValueError("f(a) and f(b) must have opposite signs")
for i in range(maxiter):
c = (a + b) / 2
if abs(f(c)) < tol:
return c
elif f(a) * f(c) < 0:
b = c
else:
a = c
raise RuntimeError("Failed to converge after {} iterations".format(maxiter))
```
这个函数接受一个函数f,一个区间[a,b],一个容差tol和一个最大迭代次数maxiter作为输入,并返回零点的近似值。在函数内部,我们首先检查f(a)和f(b)是否具有相反的符号,如果不是,则引发ValueError。然后,我们使用for循环进行迭代,直到找到一个近似的零点或达到最大迭代次数。在每次迭代中,我们计算区间的中点c,并根据f(a)和f(c)的符号更新区间的左端点a或右端点b。如果f(c)的绝对值小于容差tol,则返回c。如果在maxiter次迭代后仍未收敛,则引发RuntimeError。
python二分法猜数代码
好的,下面是一个简单的 Python 二分法猜数代码示例:
```python
import random
def binary_search(guess_num):
low = 1
high = 100
guess = 0
while guess != guess_num:
guess = (low + high) // 2
print("我猜的数字是:", guess)
if guess > guess_num:
high = guess - 1
elif guess < guess_num:
low = guess + 1
print("我猜对了!")
if __name__ == '__main__':
guess_num = random.randint(1, 100)
print("我想到了一个1到100之间的数字,你来猜猜看吧!")
binary_search(guess_num)
```
这个程序会随机生成一个1到100之间的数字,然后让用户通过二分法猜测这个数字。程序会根据用户的猜测结果,逐步缩小猜测范围,直到猜中为止。