您现在的位置是:首页 > 技术教程 正文

算法第三期——二分法(Python)

admin 阅读: 2024-03-24
后台-插件-广告管理-内容页头部广告(手机)

目录

1、二分法

1.1、引导:猜数游戏

1.1.1、猜数游戏代码 

1.2、二分法的使用条件

1.3、二分法的复杂度

2、整数二分

2.1、在单调递增序列中查找x或者x的后继

求中间值的方法:

代码演示(记忆)

2.2、在单调递增序列中查找x或者x的前驱

求中间值的方法:

代码演示(记忆)

2.3 对比两种写法

二分法应用场景

二分的本质 

简易二分模板(推荐!不需要考虑前驱和后继)

整数二分例题:分巧克力

1、暴力法

2、二分法

方法对比 

整数二分例题:跳石头

二分法套路题:最小值最大化、最大值最小化 

代码演示

整数二分例题:青蛙过河 

思路: 

代码: 

3、实数二分

实数例题:一元三次方程求解 

【暴力法】求解

【二分法】求解

二分法难点

二分法习题


1、二分法

        在一个有序序列中查找某个元素,在之前我们可以使用暴力法来遍历序列,直至找到该元素,复杂度是O(n),但其实可以利用序列有序的特征进行折半查找。
 二分法:把一个长度为n的有序序列上O(n)的查找时间,优化到了O(logn)

  • 二分法:折半搜索
  • 二分的效率:很高,O(logn)
  • 例如猜数游戏,若n= 1000万,只需要猜\(log_{2} 10^{7}\)=24次 

理论背景:非线性方程的求根问题

  • 满足方程: f(x)=0的数x称为方程的根。
  • 非线性方程:指f(x)中含有三角函数、指数函数或其他超越函数。很难或者无法求得精确解。二分法是一种求解的方法

1.1、引导:猜数游戏

 一个[1,100]内的数字,只需猜7次:
>50?是。[1,100]二分,中位数50,下一步猜[51,100]

>75?否。[51,100]二分,中位数75,下一步猜[51,75]

>63?否。[51,75]二分,...
>56?否。[51,63]二分,...

>53?是。
>54?否。

=54?是。这个数是54

【图解】:在1~10内找到7 

1.1.1、猜数游戏代码 

        首先确定左端点和右端点,如果左端点<右端点就一直循环,不断更新中间值mid = (right + left) // 2。如果目标点在左半区, 右端点往中间靠right = mid,如果目标点在右半区, 左端点往中间靠left = mid+1,直到循环结束,左端点或者右端点就是目标值。

  1. def bin_search(a, n, x): # 在数组a中找数字x,返回位置
  2. left = 0 # 二分法的左端点
  3. right = n # 二分法的右端点
  4. while left < right: # 右端点大于左端点则继续二分
  5. mid = (right + left) // 2 # 折半前的中间点。//:整除
  6. # mid = left + (right + left)//2 # C++有溢出问题,Python没有
  7. if a[mid] >= x:
  8. right = mid # 小于中间点则中间点作为右端点
  9. else: # a[mid] < x,只是大于,所以要left = mid + 1
  10. left = mid + 1 # 大于中间点则中间点作为左端点
  11. print('[', left, right, ']') # 打印猜数的过程
  12. return left
  13. n = 100
  14. a = [0] + [i for i in range(1, 101)] # #初始化1~100
  15. test = 54 # #猜54这个数
  16. pos = bin_search(a, n, test) # 二分搜索
  17. print("test=", a[pos])

1.2、二分法的使用条件

  • 上下界[a, b]确定
  • 函数在[a,b]内单调

1.3、二分法的复杂度

  • n次二分后,区间缩小到(b - a)/\(2^{n}\)
  • 给定a、b和精度要求\(\xi\),可以算出二分次数n,即满足(b -a)/\(2^{n}\)<\(\xi\)
  • 二分法的复杂度是O(logn)。
  • 例如,如果函数在区间[0,100000]内单调变化,要求根的精度是10-8,那么二分次数是44次 

2、整数二分

操作的序列中都是整数,如果处理不当可能陷入死循环。。。

2.1、在单调递增序列中查找x或者x的后继

        在单调递增数列a[ ]中查找某个数x,如果数列中没有X,找比它大的下一个数

求中间值的方法:

  • mid = (left+right)//2
  • mid = left+(right-left)//2

  • a[mid]>=x时:x在mid的左边,新的搜索区间是左半部分,left不变,更新right = mid
  • a[mid]时:x在mid的右边,新的搜索区间是右半部分,right不变,更新left = mid + 1
  • 代码执行完毕后,left = right,两者相等,即答案所处的位置。 

代码演示(记忆)

  1. # 查找57
  2. def bin_search(a, n, x): # 在数组a中找数字x,返回位置
  3. left = 0 # 二分法的左端点
  4. right = n # 二分法的右端点 0~n-1:左闭右开[0,n)
  5. while left < right: # 右端点大于左端点则继续二分
  6. mid = (right + left) // 2 # 折半前的中间点。//:整除
  7. if a[mid] >= x:
  8. right = mid # 小于中间点则中间点作为右端点
  9. else: # a[mid] < x,只是大于,所以要left = mid + 1
  10. left = mid + 1 # 大于中间点则中间点作为左端点
  11. return left
  12. n = 200
  13. a = [0] + [i for i in range(2, 202,2)]
  14. test = 57
  15. pos = bin_search(a, n, test) # 二分搜索
  16. print("find =", a[pos]) # find = 58

结果:查找57,返回58 ;查找58,返回58 

注意:若序列中存在多个x,会返回x第一次出现的下标

  1. def bin_search1(a,n,x):
  2. l,r = 0,n
  3. while l
  4. mid = (l+r)//2
  5. if a[mid]>=x:
  6. r=mid
  7. else:
  8. l=mid+1
  9. return l
  10. a = [1,2,2,3,5,5,5,6,7]
  11. print(bin_search1(a,len(a),5)) # 返回5第一次出现的下标:4

 Python标准库:bisect_left()                  两个参数:序列、目标值

  1. # 找4
  2. from bisect import *
  3. a = [1,2,2,3,5,5,5,6,7]
  4. print(bisect_left(a,4))
  5. # import bisect
  6. # print(bisect.bisect_left(a,4))

2.2、在单调递增序列中查找x或者x的前驱

        在单调递增数列al]中查找某个数x,如果数列中没有x,找比它小的前一个数

求中间值的方法:

  • mid = (left+right+1)//2            # 这里需要+1
  • mid = left+(right-left+1)//2

  • a[mid] <=x时,x在mid的右边,新的搜索区间是右半部分,所以right不变,更新left = mid;
  • a[mid]>x时,x在mid的左边,新的搜索区间是左半部分,所以left不变,更新right = mid -1
  •  代码执行完毕后,left = right,两者相等,即答案所处的位置。 

代码演示(记忆)

  1. def bin_search(a, n, x):
  2. left = 0
  3. right = n
  4. while left < right:
  5. mid = (left+right+1)//2 # 不加上1会陷入死循环
  6. if a[mid] <= x:left = mid
  7. else: right = mid - 1
  8. return left
  9. n = 200
  10. a = [0] + [i for i in range(2, 202,2)]
  11. test = 57 # # 猜57或57的后继
  12. pos = bin_search(a, n, test) # 二分搜索
  13. print("find =v ", a[pos]) # find = 56

结果:查找57,返回56;查找56,返回56

注意:若序列中存在多个x,会返回x最后一次出现的下标

  1. def bin_search2(a,n,x):
  2. l,r = 0,n
  3. while l
  4. mid = (l+r+1)//2
  5. if a[mid]<=x:
  6. l = mid
  7. else:
  8. r = mid-1
  9. return l
  10. a = [1,2,2,3,5,5,5,6,7]
  11. print(bin_search2(a,len(a),5)) # 返回5最后一次出现的下标:6

和Python标准库bisect_right()不同,bisect_right()返回的下标是应该插入的位置,例如目标值为4的话返回的是下标4,目标值为5的话默认插入在最后一个5后面。关系:bisect_right()比我们自己手写的代码bin_search2(a,n,x)返回的下标+1。

2.3 对比两种写法

注意下面红色标注部分

 二分法应用场景

  1. 存在一个有序的数列上;
  2. 能够把题目建模为在有序数列上查找一个合适的数值。

二分的本质 

        序列中的元素可以按某个规定的check()方法分为两个部分:一部分的check()为True,另一部分的check()为False。二分完成后,L和R分别指向所属区域的临界位置。()

简易二分模板(推荐!不需要考虑前驱和后继)

假设:L指向check()=True的部分(≤目标值),R指向check()=False的部分(>目标值),假设可以根据题目需要来确定。 

二分完成后,L和R分别指向所属区域的临界位置(终止条件:l+1=r).
注意:左端点和右端点的初始化要定义在范围外,l, r = -1, n + 1

  1. def check():
  2. # 具体的check函数
  3. pass
  4. def bin_search(a, n, x):
  5. l, r = -1, n + 1
  6. while l + 1 != r:
  7. mid = (l+r) // 2
  8. if check(mid):
  9. l = mid
  10. else:
  11. r = mid
  12. return (l or r) # 选取需要的部分进行返回

举例:套用这个模板把区间划分成≤5和>5两块,返回左边界:5的最后一个的下标。

  1. # 把边界划分成≤5和>5两块
  2. def bin_search2(a,n,x):
  3. l,r = -1,n # 左闭右开[0,n):范围0~n-1
  4. while l + 1 != r:
  5. mid = (l+r)//2
  6. if a[mid]<=x:
  7. l = mid
  8. else:
  9. r = mid
  10. return l # 返回左边界
  11. a = [1,2,2,3,5,5,5,6,7]
  12. print(bin_search2(a,len(a),5)) # 6

若想返回5的第一个的下标,把区间划分成<5和≥5,返回右边界r。修改部分代码即可:

  1. # 将上面的代码中间修改成这部分代码
  2. if a[mid]>=x:
  3. r = mid
  4. else:
  5. l = mid
  6. return r # 返回右边界

整数二分例题:分巧克力

2017年第八届蓝桥杯省赛lanqi ao0J题号99

题目描述

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力,其中第 i 块是 Hi​×Wi 的方格组成的长方形。为了公平起见,

小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足:

  1. 形状是正方形,边长是整数;

  2. 大小相同;

例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小明计算出最大的边长是多少么?

输入描述

第一行包含两个整数 N,K (1≤N,K≤10^5)。

以下 N 行每行包含两个整数Hi​,Wi​ (1≤Hi​,Wi​≤10^5)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述

输出切出的正方形巧克力最大可能的边长

输入输出样例

输入

  1. 2 10
  2. 6 5
  3. 5 6

输出

2

切出的巧克力尽可能大,满足:(1)形状是正方形,边长是整数;(2)大小相同。 

1、暴力法

边长从1开始到最大边长d,每个值都试一遍,一直试到刚好够分的最大边长为止。编码:边长初始值d=1,然后d=2.3,4,...一个个试。
复杂度:n个长方形,长方形的最大边长d。check()计算量是O(n),做d次check(),总复杂度0(n* d),n和d的最大值是\(10^{5}\),超时。 

  1. def check(d): # 检查够不够分
  2. num=0 # 切成的份数
  3. for i in range(n): # 遍历每一块巧克力
  4. num += (h[i]//d)*(w[i]//d) # 将每一块巧克力切下来的份数进行统计。巧克力长宽要整除d哦!
  5. if num>=k: # 够分
  6. return True
  7. else: # 不够分
  8. return False
  9. h = [0]*100010
  10. w = [0]*100010
  11. n,k = map(int,input().split())
  12. for i in range(n):
  13. h[i],w[i] = map(int,input().split())
  14. d=1 # 正方形边长,从最小的边长开始试
  15. while True:
  16. if check(d):
  17. d+=1 # 边长从1开始,一个个地暴力试
  18. else: # 当前的d不满足,所以下面输出的时候d要-1(前一个d满足)
  19. break
  20. print(d-1)

2、二分法

        一个个试边长d太慢,用二分,按前面的“猜数游戏”的方法猜d的取值,因为d从小到大是一个有序数列。

暴力法需要做d次eheck();二分法只需要做O(ogd)次eheck(),总复杂度O(nlogd)。

  1. def check(d):
  2. num = 0
  3. for i in range(n):
  4. num += (w[i] // d) * (h[i] // d)
  5. if num >= k:
  6. return True
  7. else:
  8. return False
  9. h = [0] * 100010 # 边界最好比题目要求的大一点,避免边界上出了问题
  10. w = [0] * 100010
  11. n, k = map(int, input().split())
  12. for i in range(n):
  13. h[i], w[i] = map(int, input().split())
  14. L, R = 1,100010
  15. while L < R:
  16. mid = (L + R) // 2
  17. if check(mid): # 数量满足要求就把左端点提高到中间点
  18. L = mid + 1
  19. else: # 数量不满足要求就把右端点降低到中间点
  20. R = mid
  21. print(L - 1)

上面代码有点麻烦,用简易二分模板来写: 

  1. def check(d):
  2. num = 0
  3. for i in range(n):
  4. num += (w[i] // d) * (h[i] // d)
  5. if num >= k:
  6. return True
  7. else:
  8. return False
  9. h = [0] * 100010 # 边界最好比题目要求的大一点,避免边界上出了问题
  10. w = [0] * 100010
  11. n, k = map(int, input().split())
  12. for i in range(n):
  13. h[i], w[i] = map(int, input().split())
  14. L, R = 0,100010
  15. while L + 1 != R:
  16. mid = (L + R) // 2
  17. if check(mid): # 数量满足要求就把左端点提高到中间点
  18. L = mid
  19. else: # 数量不满足要求就把右端点降低到中间点
  20. R = mid
  21. print(L)

方法对比 

整数二分例题:跳石头

题目来源:跳石头 - 蓝桥云课 (lanqiao.cn)

题目描述:

一年一度的"跳石头"比赛又要开始了!

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M 块岩石(不能移走起点和终点的岩石)。

输入描述:

输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离起点和终点之间的岩石数,以及组委会至多移走的岩石数

接下来 N 行,每行一个整数,第 i 行的整数 Di​(0第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

其中,0≤M≤N≤5×10^4,1≤L≤10^9。

输出描述:

输出只包含一个整数,即最短跳跃距离的最大值

输入输出样例:

输入

  1. 25 5 2
  2. 2
  3. 11
  4. 14
  5. 17
  6. 21

输出

4

二分法套路题:最小值最大化、最大值最小化 

        在n块岩石中移走m个石头,有很多种移动方法。在第i种移动方法中,剩下的石头之间的距离,有一个最小距离ai。在所有移动方法的最小距离ai中,问最大的ai是多少?在所有可能的最小值中,找最大的那个,就是“最小值最大化。

  • 暴力法:找所有的组合,在n块岩石中选m个石头的组合\(C_{n}^{m}\)。情况太多,显然会超时...
  • 二分法:不去找搬走石头的各种组合,而是给出一个距离d,检查能不能搬走m块石头而得到最短距离d。把所有的d从小到大都试一遍,肯定能找到一个最短的d。用二分法找这个d即可。

代码演示

 用二分法找一个最小距离d。函数check(d)函数检查d这个距离是否合适。

函数check(d):检查距离d是否合适(贪心法
        把前后两块石头距离<d,将第i块石头(两块之间较后一块)搬走,前后两块石头距离≥d的留下 ,并将位置从前一块转移到第i块(后一块),如果移走的石头不超过m块,则返回True,可以提高距离d,如果移走的石头超过m块,不符合题意,则返回False,应该减小距离d。

【图解】:把前后两块石头距离<d,不满足最小距离的要求,所以pos不变,stone[i+1],相当于将第i块石头(两块之间较后一块)搬走,下次还是比较从原来pos开始到stone[i+1]这段距离。(pos不变则认为是同一段距离)

 【图解】:前后两块石头距离≥d的留下 ,因为当前距离满足≥最小距离d,所以并将位置pos从前一块转移到第i块(两块之间较后一块),准备比较下一段距离。

  1. def check(d):
  2. num = 0 # num:最终移走的石头数
  3. pos = 0 # 起点坐标
  4. for i in range(0, n): # 0到n-1作为石头下标
  5. if stone[i] - pos < d: # 后面的石头距离位置pos的距离<d,第i块可以搬走
  6. num += 1
  7. else: # 当后面石头距离位置pos的距离≥d,不能搬走,
  8. pos = stone[i] # 位置pos变成后面的石头
  9. if num <= m: # 不超过上限m块(最多移走m块),符合题意,可以增大距离d
  10. return True
  11. else: # 移走超过m块石头,不合题意,应该减小距离d
  12. return False
  13. len, n, m = map(int, input().split())
  14. stone = []# 第i块石头到起点的距离
  15. # 读入每块石头与起点的距离
  16. for i in range(n):
  17. t = int(input()) # 也可以不用t,直接stone.append(int(input)))
  18. stone.append(t)
  19. # 二分法找最小距离d
  20. L, R = 0, len # 确定左右端点
  21. # 只能查找x或者x的前驱,不能找后继,因为后继就不是最小值了
  22. while L < R: # 这部分只套用二分法的前驱写法
  23. mid = (L + R +1) // 2
  24. if check(mid): # 将左端点提高到中点
  25. L = mid
  26. else:
  27. R = mid - 1 # 将右端点减小到中点
  28. print(L)

用简易二分模板来写: 

  1. def check(d):
  2. num = 0 # num:最终移走的石头数
  3. pos = 0
  4. for i in range(0, n): # 0到n-1作为石头下标
  5. if stone[i] - pos < d: # 后面的石头距离位置pos的距离<d,第i块可以搬走
  6. num += 1
  7. else: # 当后面石头距离位置pos的距离≥d,不能搬走,
  8. pos = stone[i] # 位置pos变成后面的石头
  9. if num <= m: # 不超过上限m块(最多移走m块),符合题意,可以增大距离d
  10. return True
  11. else: # 移走超过m块石头,不合题意,应该减小距离d
  12. return False
  13. len, n, m = map(int, input().split())
  14. stone = []# 第i块石头到起点的距离
  15. # 读入每块石头与起点的距离
  16. for i in range(n):
  17. t = int(input()) # 也可以不用t,直接stone.append(int(input)))
  18. stone.append(t)
  19. # 二分法找最小距离d
  20. L, R = -1, len + 1 # 确定左右端点
  21. # 只能查找x或者x的前驱,不能找后继,因为后继就不是最小值了
  22. while L +1 != R: # 这部分只套用二分法的前驱写法
  23. mid = (L + R) // 2
  24. if check(mid): # 将左端点提高到中点
  25. L = mid
  26. else:
  27. R = mid # 将右端点减小到中点
  28. print(L)

整数二分例题:青蛙过河 

 2022年第十三届蓝桥杯省赛,lanqiao0J题号2097

问题描述

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上(某次跳跃后使石头高度下降到 0 是允许的)。

小青蛙一共需要去学校上 x 天课, 所以它需要往返 2x 次。当小青蛙具有 一个跳跃能力 y 时, 它能跳不超过 y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 天课。

输入格式

输入的第一行包含两个整数 n,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x 才是实际过河的次数。

第二行包含 n−1 个非负整数 H1​,H2​,⋯,Hn−1​, 其中 Hi​>0 表示在河中与 小青蛙的家相距 i 的地方有一块高度为 Hi​ 的石头, Hi​=0 表示这个位置没有石 头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力

样例输入

  1. 5 1
  2. 1 0 1 0

样例输出

4

样例说明

由于只有两块高度为 1 的石头,所以往返只能各用一块。第 1 块石头和对岸的距离为 4,如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。

评测用例规模与约定

对于 30% 的评测用例, n≤100;

对于 60% 的评测用例, n≤1000;

对于所有评测用例, 1≤n≤10^5,1≤x≤10^9,1≤Hi​≤10^4 。

思路: 

  • 往返累计2x次相当于单向走2x次
  • 跳跃能力越大,越能保证可以通过2x次
  • 用二分法找到一个最小的满足条件的跳跃能力。
  • 设跳跃能力为mid,每次能跳多远就跳多远,用二分法检查mid是否合法。

        题目要求的是能上完学的最小的跳跃能力,所以我们可以想到用二分法来找出最小跳跃能力,定义check()函数来判断能否上完学。难的是check函数 首先想一个必要条件,如果check(y)返回True,那么对于所有以i开始长度为y的区间区间中所有数之和必然不少于2x。可以想象,因为最多跨y个长度,因此来回肯定都要经过这个区间,这个区间肯定要能被踩至少2x次 这个条件也是充分条件,因为如果所有长度为y的区间都能至少踩2x次,那么肯定能够完成2x次来回。 

【图解】例如看下面的图,起点和终点之间有若干个长度为mid的区间,若青蛙的跳跃能力=mid,这每到对岸一次,都必须经过每个区间,那么来回就是必须经过每个区间两次,上学x天就应该经过2x次每个区间2x次,如果区间内石头高度和小于2x(不能踩2x次),则不能上完学,应该提高跳跃能力,如果区间内石头高度和≥2x,则可以上完学,减少跳跃能力以找到最低跳跃能力。

        上面的区间是从起点开始,长度为y的区间,但其实这是不充分的,因为所有区间向右移动1个位置后,所有区间的是新的区间(区间内的石头高度变了),这些新的区间也需要满足区间内石头高度和≥2x。当所有长度为mid的区间都能至少踩2x次,那么肯定能够完成2x次来回。

代码: 

  1. def check(mid):
  2. for i in range(mid,n):
  3. if sum[i] - sum[i-mid] < 2*x: # 长度为mid的区间和<2x
  4. return False # 跳不过去
  5. return True # 全部区间长度都≥2x,则能跳过去
  6. n, x = map(int, input().split())
  7. h = list(map(int, input().split()))
  8. sum = [0,h[0]]
  9. for i in range(1, len(h)):
  10. sum.append(h[i] + sum[i])
  11. L=0
  12. R =100000
  13. while L +1 != R:
  14. mid=(L+R) //2
  15. if check(mid): R = mid # 能跳过去,减少跳跃能力
  16. else: L = mid # 不能跳过去,提高跳跃能力
  17. print(R) # 能跳过去的最小跳跃能力

3、实数二分

与整数二分法相比,实数二分容易多了,不用考虑整数的取整问题。
两种写法: while、for 

  1. eps = 0.00001 #精度
  2. while right - left > eps: # 区间>精度,说明达不到精度值,继续二分
  3. mid = (left+right)/2 # 实数二分的话这里是/,整数二分是//
  4. if check(mid): #判定
  5. right = mid
  6. else:
  7. left = mid
  1. for i in range(100): # 做100次二分,精度:1/2^100
  2. mid = (left+right)/2#判定
  3. if check(mid):
  4. right = mid
  5. else:
  6. left = mid

实数例题:一元三次方程求解 

题目描述

有形如:ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根(根的范围在 −100 至 100 之间),且根与根之差的绝对值 ≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后 2 位。

提示:记方程 f(x)=0,若存在 2 个数 x1​ 和 x2​,且x1​

输入描述

输入一行,4 个实数 a,b,c,d。

输出描述

输出一行,3 个实根,从小到大输出,并精确到小数点后 2 位。

输入输出样例

输入

1 -5 -4 20

输出

-2.00 2.00 5.00

【暴力法】求解

  • 本题数据范围小,可以用暴力法模拟。
  • 元三次方程有3个解,用暴力法,在根的范围[-100,100]内一个个试,因为两个之间距离≥1,所以分成两百个小区间,一个区间内部最多只能有一个解。答案只要求3个精度为2位小数的实数,那每个小区间再分成100份,精度为0.01。那么只需要试200*100 = 20000次就行了。
  • 判断一个数是解的方法:如果函数值是连续变化的,且函数值在解的两边分别是大于0和小于0,那么解就在它们中间。例如函数f(i)和f(j)分别大于、小于0,那么解就在[i,j]内。

 【二分法】求解

如果题目要“精确到小数点后6位”,上面的暴力法需要计算200*\(10^{6}\)次,超时了

二分法:题目给了一个很好的条件: 根与根之差的绝对值大于等于1。那么所有的[i,i+1]小区间(200个小区间)内做二分查找就行。

  1. def y(x): return a*x*x*x+b*x*x+c*x+d
  2. a,b,c,d = map(float,input().split()) # 不能用int,因为输入有浮点数。
  3. # n = input().split()
  4. # a,b,c,d = eval(n[0]),eval(n[1]),eval(n[2]),eval(n[3]) # eval 将字符串转成对应数值(整型、浮点型...)
  5. for i in range(-100,100):
  6. left,right=i,i+1 # 在每个[i,i+1]小区间内做二分
  7. y1,y2=y(left),y(right) # 计算区间端点的值
  8. if y1==0: # y1==0就是解
  9. print("{:.2f}".format(left),end=" ") # 注意输出格式:保留两位小数
  10. if y1*y2<0: # 在这区间内有解
  11. #while (right-left) >= 1e-10: #精确到小数点后两位小数,要往后多求几位
  12. for i in range(100): # 100次二分:在这个区间内求解
  13. mid =(left+right)/2
  14. if y(mid)*y(right) <=0: left = mid
  15. else: right = mid
  16. print("{:.2f}".format(right),end=" ")

二分法难点

  1. 要把题目信息建模为可以使用二分法解决的问题,二分法可以解决一般最值问题。
  2. 怎么写一个check函数(根据题目要求)
  3. 二分法本身取整的问题(参考上面介绍过的整数二分)。如果用的是简易二分模板其实这里不需要考虑这个

二分法习题

可以在蓝桥杯官网:题库 找到下面这些题目

  本文参考罗勇军老师的蓝桥云课

标签:
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

在线投稿:投稿 站长QQ:1888636

后台-插件-广告管理-内容页尾部广告(手机)
关注我们

扫一扫关注我们,了解最新精彩内容

搜索