Python程式：計算圓形管道中球體碰撞次數

假設，在一個圓形管道中有n個球體。管道長100米，最初，每個球體在管道中距離我們稱之為起點的某一點i米。現在，這些球體開始在管道內以不同的方向做圓周運動。球體在管道內以每秒0.1米的速度運動。當兩個球體在某一點相遇時，就會發生碰撞，球體會改變運動方向。如果這個過程持續很長時間，比如10^9 + 6秒；我們需要找出球體發生碰撞的次數。球體與起點的初始距離作為輸入給出。

因此，如果輸入類似於input_array = [0, 10]，則輸出將為400000。

有兩個球體，它們的初始距離從起跑線開始作為輸入給我們。如果它們的方向相同，它們永遠不會發生碰撞。但是，如果它們的方向不同，它們會在一段時間內發生碰撞。一個球體與另一個球體恰好碰撞400000次。

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

對列表input_array進行排序
size := input_array的大小
lap_count := (10^5)*2
output := 2 * lap_count * floor(size / 2) * (size - floor(size / 2))
stop := 0
for i in range 0 to size - 1, do
if stop不等於1，則
- if input_array[i] + 1等於input_array[i+1]，則
  - output := output + 2
  - stop := 1
- 否則，
  - stop := 0
否則，
- stop := 0
return output

示例

讓我們看看以下實現以獲得更好的理解：

線上演示

def solve(input_array):
   input_array.sort()
   size = len(input_array)
   lap_count = (10**5)*2
   output = 2*lap_count*(size//2)*(size - size//2)
   stop = 0
   for i in range(size - 1):
      if stop != 1:
         if input_array[i] + 1 == input_array[i+1]:
            output+=2
            stop = 1
         else:
            stop = 0
      else:
         stop = 0
   return output
print(solve([0, 10]))

輸入

[0, 10]

輸出

Arnab Chakraborty

更新於：2021年5月18日

187 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習