分析俄羅斯農夫的乘法

分析俄羅斯的農夫乘法

自古以來在俄羅斯的鄉村，農夫就流行一種不同於目前十進位的傳統乘法的計算，其算法如下：

(1) 將被乘數和乘數(兩個數都是正整數)放在兩行的第一列。
(2) 將第1行的正整數除以2，取商數，不計餘數；再將商數除以2，取商數，不計餘數；直至得到商數是1為止。
(3) 將第2行的正整數乘以2，取乘積；再將乘積乘以2；直至到第一行的最後一列為止。
(4) 刪除掉第二行中與第一行中的偶數位在同一列的正整數。
(5) 將第二行中留下的正整數相加，其總和就是原來被乘數和乘數的乘積。

舉例：

計算 53 × 60

俄羅斯的農夫是這樣算的

53	60
26	120
13	240
6	480
3	960
1	1920

60+240+960+1920=3180

計算 60 × 53

俄羅斯的農夫是這樣算的

60	53
30	106
15	212
7	424
3	848
1	1696

212+424+848+1696=3180

或許俄羅斯農夫的算法只是他們的經驗法則，雖然談不上是有效率的計算法，但是他們的生活智慧還是值得後人欣賞與探究，箇中道理如下：

53 × 60 = ( 26 × 2+1 ) × 60 = 26 × 120 + 60

26 × 120 = ( 13 × 2 + 0 ) × 120 = 13 × 240 + 0

13 × 240 = ( 6 × 2 + 1 ) × 240 = 6 × 480 + 240

6 × 480 = ( 3 × 2 + 0 ) × 480 = 3 × 960 + 0

3 × 960 = ( 1 × 2 + 1) × 960 = 1 × 1920 + 960

由上述可知

53 × 60 = ( 13 × 240 + 0 ) + 60 = ( ( 6 × 480 + 240 ) + 0 ) + 60 = ( ( (3 × 960 + 0 ) + 240 ) + 0 ) + 60 = ( ( ( (1 × 1920 + 960 ) + 0 ) + 240 ) + 0 ) + 60

= 1920 + 960 + 240 + 60 = 3180

請輸入兩個正整數後，再按" 執行 " :