作者:BigUncle | 来源:互联网 | 2022-12-19 19:28
【背景】有一道算法题,在直角坐标系的第一象限内,NxN的区域内有多少个能与原点直线相连又不经过其他整数点的点我本来想根据数据推理总结出数学公式来,但是归纳了半天还没弄出来还浪费了时间,还
【背景】有一道算法题,在直角坐标系的第一象限内,NxN的区域内有多少个能与原点直线相连又不经过其他整数点的点
我本来想根据数据推理总结出数学公式来,但是归纳了半天还没弄出来还浪费了时间,还不如直接编程解决。我的思路如下:
NxN的区域内的整数点与原点相连构成直线斜率各不相同,只要算出有多少个不同的斜率就能得到有多少个不被挡住的点
斜率我准备直接通过点坐标(x,y)y/x得到,但是python2与python3除法处理不同,而变成平台默认是Python2,这就比较坑了
在python3中a/b就是a除以b的实际值,而python2中a/b是取整
我们要使Python2中的除法是其真实值而不是取整,我们可以这样:
from __future__ import division
下面就是我们的完整代码了:
from __future__ import division
def count(N):
result = []
for x in range(1, N + 1):
for y in range(0, N + 1):
degree = y / x
if degree not in result:
result.append(degree)
return len(result)+1
N = int(raw_input())
s = count(N)
print(s)
但是可惜可以没有提交上去>_<