在Python中编写的翻转n个开关后将打开的开关数进行计数的程序
假设有一个数字n,在一个房间里有n个开关,而且所有的开关都是关闭的。现在有n个人按以下方法翻转开关 −
- 第一个人翻转所有开关的开关(也就是所有的开关)
- 第二个人翻转2的倍数的那些开关(2、4、6、…)
- 第i个人翻转i的倍数的那些开关。
我们必须找出最终将打开的开关数量。
所以,如果输入为n = 5,则输出将为2,因为最初所有开关都是关闭的[0,0,0,0,0],第一个人翻转所有开关[1,1,1,1,1],第二个人翻转这样的开关[1,0,1,0,1],然后第三个人做[1,0,0,0,0],第四个人做[1,0,0,1,0]
为解决这个问题,我们将遵循以下步骤 −
- l:=0,r:=n
- 当l<= r时,执行以下内容
- mid:= l +(r-l)/ 2
- 如果mid ^ 2 ≦ n<(mid +1)^ 2,则
- 返回中间值
- 否则,当n<mid ^ 2时,那么
- r:= mid
- 否则,
- l:= mid +1
让我们看一下以下实现以更好地理解 −
更多Python相关文章,请阅读:Python 教程
示例
class Solution:
def solve(self, n):
l, r = 0, n
while l <= r:
mid = l + (r - l) // 2
if mid * mid <= n < (mid + 1) * (mid + 1):
return mid
elif n < mid * mid:
r = mid
else:
l = mid + 1
ob = Solution()
n = 5
print(ob.solve(n))
输入
5
输出
2