螞蟻在格子內碰撞 (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 來設計。
沒有留言:
張貼留言