当前位置：网站首页>第十二届蓝桥杯《杨辉三角》-二分法

第十二届蓝桥杯《杨辉三角》-二分法

2022-08-08 12:19:00 【算法与编程之美】

1 引言

在二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

二分法的运用原理：以在一个升序（递增的序列）数组中查找一个数为例，每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

2 问题描述

c581fb4586cd98a7872f78a8e5c13abb.png

图2.1

3 算法描述

  1. 通过评测用例规模可以知道，问题时间复杂度为N（109），不能直接暴力解决，那么就需要寻找规律，利用其它算法解答。

  2. 根据杨辉三角定义可知，其数值是二项式系数（组合数）在三角形中的几何排列（n的数值为第n行），根据题目要求可知，输出答案为第一次出现的位置，根据图3.1可知，只需求解左半部分即可。

0c546889fba3074629c698364dacefb8.png

图3.1

  • （3）根据观察图3.1可知，每一个斜行是依次递增，同时再横向观察可知，组合数越靠近中间，数值越大，那么同理可得，位置越靠下方，数值便越大，因此，在解决此问题时，应该从下方开始寻找，同时可知，第1斜行的1=C（0,0），第二斜行的2=C（2,1），第三斜行的6=C（4,2）,第四斜行的20=C（6,3），那么第i斜行的起始位置 =C（2n,n）,同理，根据计算可知C（34，17）= 2×109 而C（32，16）< 108所以可以从16行开始枚举，枚举到相对于所求值小但大于下一斜行起始值，找到斜行起始值，开始使用二分法查找，因为斜行满足递增序列。

  • （4）寻求的位置，可以在查找的时候确定，N所在行 n和所在斜行 k ，然后通过等差公式 n*（n+1）/2 计算它之前数目的个数再加上 k+1。

  • （5）例如：输入整数N = 15，开始从16行枚举，只需枚举到第3斜行起始值 = 6, k = 2 ，开始二分斜行，得到实际行n = 6,因此需要k+1,结果 ans = 6*(6+1)/2 + 2 + 1 = 24。

4代码

n = int(input())
def C(a,b):  #求组合数
   res = 1
   i = a
   for o in range(1,b+1):
       res = res *i / o
       i -=1
       if res > n:
           return res
   return res
def check(k):  
#二分查找（需要找到边界值）
#左边界2k，右边界为max(l, n)取二者最大，避免右边界小于左边界
   left = 2*k
   right = max(n,left)
   while left < right:
       mid = left + right >> 1
       if C(mid,k) >= n:
           right = mid
       else:
           left = mid + 1
   if C(right,k) != n:
       return  False
   print(int((right+1)*right//2+k+1))
   return True
k = 16
for i in range(k):
   k -=1
   if(check(k)):
       break

5 结语

通过解答简单的示列问题，可以充分了解到二分算法的基本原理以及思考问题的思路。

原网站

版权声明
本文为[算法与编程之美]所创，转载请带上原文链接，感谢
https://where2go.blog.csdn.net/article/details/126220096

边栏推荐

猜你喜欢

随机推荐