Python程式：找出直線段上整數座標點的個數

假設我們有兩個點 (p1, q1) 和 (p2, q2)。我們需要找出在連線這兩個點的直線上，有多少個整數座標點（x 和 y 值都是整數）。程式會返回點的個數。

例如，如果輸入 p1 = 3, q1 = 3, p2 = 6, q2 = 6，則輸出為 2。如果我們畫出直線，可以看到點 (5,5) 和 (6,6) 位於直線上。

為了解決這個問題，我們將遵循以下步驟：

• 定義一個函式 `gcd_find()`。它將接收 x, y 作為引數。
  • 如果 y 等於 0，則
    • 返回 x
  • 返回 `gcd_find(y, x mod y)`

在主函式中，執行以下操作：

• 返回 `gcd_find(|p2 - p1| , |q2 - q1|) - 1`

示例

讓我們來看下面的實現來更好地理解：

def gcd_find(x,y):
   if y == 0:
      return x
   return gcd_find(y,x % y)

def solve(p1,q1,p2,q2):
   return gcd_find(abs(p2 - p1),abs(q2 - q1)) - 1

print(solve(3,3,6,6))

輸入

3,3,6,6

輸出

2

Arnab Chakraborty

更新於：2021年10月23日

226 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習