2024年2月10日 星期六

Python 程式練習 6 ─ 螞蟻碰撞幾次

http://4rdp.blogspot.com/2024/02/python-6.html?m=0

 


螞蟻在格子內碰撞 (Bing Image Creator)

今天剛好是 2024 龍年正月初一,祝大家龍發財!

在一個有限循環的平面間有數隻螞蟻任意自由活動,這個平面劃分 N x N 個方格,初始有 m 隻螞蟻任意散落在不同的格子內,每隻螞蟻每隔一秒鐘可以上下左右隨意移動一個格子,當移過邊界會循環到另一邊,例如 10 x 10 格子,某隻螞蟻在 (0, 0) 座標往左移一格就是 (9, 0),然後往下一格就到 (9, 9)。

因為每隻螞蟻會任意方向行動,所以某一秒鐘可能有兩隻或更多隻螞蟻停留在某一格座標中,稱為碰撞,一格有兩隻在一起為碰撞一次,三隻為碰撞三次,四隻在一起為碰撞六次,以此類推。

請設計一個程式,輸入平面 N 大小,螞蟻數量 m,給定時間 T 秒後,然後計算螞蟻們總共碰撞了多少次?N 的最大值為 10⁹,m 最大值為 2x10

這個程式設計題目是 Andy 分享給我的,考驗演算法設計,占用記憶體要少,計算效率要高,不限定用 Python 來設計。

沒有留言:

張貼留言