1 回答

TA貢獻1772條經驗 獲得超6個贊
N*M(N行,M列)的矩形,內部是一個個的網格;
2*2:經過2個 ? 3*2:經過4個 4*2:經過4個
2*3:經過4個 ??3*3:經過3個 4*3:經過6個
2*4:經過4個 ??3*4:經過6個 4*4:經過4個
2*5:經過6個 ??3*5:經過7個 4*5:經過8個
不多寫了,可以發現:
1:如果M和N沒有公約數,那么經過的正方形個數就是M+N-1
? ? ?畫圖比較容易發現這一點,N*M一共含有N-1橫邊和M-1條豎邊,左上角的一個矩形是一定經過的,之后這條斜線想要進入下一個矩形,必須要經過一條內部的邊(橫邊或者豎邊),一共經過經過N-1+M-1條內部邊(因為每走一步必定經過一個邊),也就是N-1+M-1個矩形加上最左上角的一個矩形,這就是N+M-1個矩形。
2:如果M和N有公約數,那么經過的正方形個數就是M+N-(M和N的最大公約數)
? ? 其實這一點就是這條斜線經過正方形交點的情況,有多少個正方形的交點位于這條線上?是(M和N的最大公約數)-1個點,首先把這條線稍微偏移一點來避開這些交點,那么經過的矩形是M+N-1個;但是這種偏移會在每一個交點位置上添加一個經過的矩形,可以在紙上畫一下,很好理解,因為一共有(M和N的最大公約數)-1個交點,也就是多出了(M和N的最大公約數)-1個矩形。減掉這些多的矩形就可以得到實際經過的矩形數:
M+N-1-((M和N的最大公約數)-1) =?M+N-(M和N的最大公約數);
?
其實1和2可以合并起來,經過的矩形數目是:M+N-(M和N的最大公約數),問題轉換為求M和N的最大公約數,這應該就不難了。
添加回答
舉報