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

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

1 引言

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

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

2 问题描述

图2.1

3 算法描述

通过评测用例规模可以知道，问题时间复杂度为N（109），不能直接暴力解决，那么就需要寻找规律，利用其它算法解答。根据杨辉三角定义可知，其数值是二项式系数（组合数）在三角形中的几何排列（n的数值为第n行），根据题目要求可知，输出答案为第一次出现的位置，根据图3.1可知，只需求解左半部分即可。

图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 resdef 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 Truek = 16for i in range(k): k -=1 if(check(k)): break

5 结语

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。