2俄羅斯農(nóng)夫法的乘法算法

1、實(shí)驗(yàn)報(bào)告名：俄羅斯農(nóng)夫法的乘法算法的實(shí)現(xiàn)俄羅斯農(nóng)夫法的乘法算法的實(shí)現(xiàn)問題簡介：實(shí)現(xiàn)俄羅斯農(nóng)夫法的乘法算法，算法求 m n計(jì)算方法如下：m2nm iseve n2m nm 12n nm isodd2要求不能使用乘法和除法實(shí)現(xiàn)。俄羅斯農(nóng)夫法的乘法算法的實(shí)現(xiàn)算法設(shè)計(jì)方法簡介：先對(duì)輸入的2個(gè)數(shù)判斷正負(fù)，用一個(gè)flag去記錄結(jié)果的正負(fù)。通過位運(yùn)算的&讓m去和1做與運(yùn)算，判斷m的奇偶性，分奇偶性進(jìn)行不 同的處理。用s記錄運(yùn)算的結(jié)果。因?yàn)椴荒苡贸顺?，所以用移位運(yùn)算的左移1位相當(dāng)乘以2,用移位運(yùn)算的右移1位相當(dāng)除以2。程序代碼:#includevoid main()int m,n,s,flag;while(

2、scanf(%d%d,&m,&n)=2)flag=0;if(m0)flag=1-flag;m=0-m;if(n=1)if(m&1=1)s+=n;m=(m-1)1;n=n1;n=n1;if(flag=0) printf(%dn,s);elseprintf(-%dn,s);算法介紹：先對(duì)輸入的 2 個(gè)數(shù)判斷正負(fù)，用一個(gè) flag 去記錄結(jié)果的正負(fù) flag=0;if(m0)flag=1-flag;m=0-m;if（n0）flag=1-flag;n=0-n;用這段代碼可以作為最后結(jié)果正負(fù)的判斷，當(dāng)flag=0 時(shí)，結(jié)果為正否則為負(fù)。然后令記錄結(jié)果的s先清零。然后不斷重復(fù)以下步驟，直到 m=1為止：“讓 m 去和 1 做 &運(yùn)算，如果結(jié)果為1,（即m為奇數(shù)）s加上n的值，m-1再右移1位（即除以 2）， n 左移 1 位（即乘以 2）。如果結(jié)果為 0, m 右移 1 位（即除以 2）, n 左移 1 位（即乘以 2）。 ”最后輸出正負(fù)，輸出結(jié)果s的值。時(shí)間分析復(fù)雜度：O（1）。實(shí)驗(yàn)數(shù)據(jù)：輸入數(shù)據(jù) 1： 39 79輸入數(shù)據(jù) 2： -39 79輸入數(shù)據(jù) 3： 1234 4321實(shí)驗(yàn)結(jié)果：輸出數(shù)據(jù) 1： 3081輸出數(shù)據(jù) 2： -3081輸出數(shù)據(jù) 3： 5332114體會(huì)：用俄羅斯農(nóng)夫法的乘法算