算法簡介：

俄羅斯農(nóng)夫法的乘法算法，整數(shù)與整數(shù)相乘的方法如下：

代碼如下：

    import java.util.Scanner;  
      
      
    public class Algorithm_1 {  
      
      
        /** 
         * 實(shí)現(xiàn)俄羅斯農(nóng)夫法的乘法算法 
         *  
         * @param args 
         */  
        public static void main(String[] args) {  
            Scanner sc = new Scanner(System.in);  
            int m, n, flag,res;  
            while (true) {  
                m = sc.nextInt();  
                n = sc.nextInt();  
                flag = 0;res=0;  
                if (m < 0) {  
                    m = 0 - m;  
                    flag = 1;  
                }  
                if (n < 0) {  
                    n = 0 - n;  
                    flag = 1 - flag;  
                }  
                while (m >= 1) {  
                    if ((m & 1) == 1) {// odd  
                        res+=n;  
                        m=(m-1)>>1;  
                        n=n<<1;  
                    }  
                    else{  
                        m=m>>1;  
                        n=n<<1;  
                    }  
                }  
                  
                if(0 == flag){  
                    System.out.println("m × n = "+res);  
                }else{  
                    System.out.println("m × n = -"+res);  
                }  
                  
            }  
        }  
    }  
    /* 
     * 測試數(shù)據(jù)： 
     * 輸入：0 0 輸出：0 
     * 輸入：13 18 輸出：234 
     * 輸入：-13 18 輸出：-234 
     * 輸入：13 -18 輸出：-234 
     * 輸入：-13 -18 輸出：234 
     */  

算法分析：

首先，對輸入的兩個(gè)整數(shù)m和n進(jìn)行正負(fù)判斷，我的程序中用到的是flag來標(biāo)記正負(fù)的；既然不能用*/ %等等這些復(fù)雜的運(yùn)算符，那通常的做法是用位運(yùn)算來進(jìn)行乘除；然后，m× n 得分奇數(shù)和偶數(shù)兩種情況來進(jìn)行不同的處理。

    具體思路：flag判斷正負(fù)：當(dāng)m>0, n>0 時(shí)，flag=0；

當(dāng)m>0, n<0 時(shí)，flag=1；

當(dāng)m<0, n>0 時(shí)，flag=1；

當(dāng)m<0, n<0 時(shí)，flag=0；

    這里用兩個(gè)if來判斷即可列出四種情況。

    res用來存放結(jié)果。

    如果m>=1，則分兩種情況，

(1)m為奇數(shù)

    res加上n的值，然后將m-1右移一位，并將結(jié)果賦值給m，

n左移一位，并將結(jié)果賦值給n。

       (2)m為偶數(shù)

               m右移一位，并將結(jié)果賦值給m，n左移一位，并將結(jié)果賦值給n。

    一直循環(huán)以上兩個(gè)步驟，直到m的值變?yōu)?為止。

    最后的結(jié)果的絕對值是res，再加上m× n 的正負(fù)號(hào)，得出最終結(jié)果。

算法的時(shí)間復(fù)雜度：O(1)

標(biāo)簽： 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。