- 論壇徽章:
- 0
|
已知正整數(shù)m, 一定存在一個(gè)非負(fù)整數(shù)n, 使得2的n次方小于等于m, 并且m小于2的n+1次方, 即2^n <= m < 2^(n+1); (不等式 1)
現(xiàn)求a/b！ a, b都為正整數(shù)！ 可設(shè)a = bm + r, m為商，r為余數(shù), 滿足 0<= r < b。 又根據(jù)上面的不等式1，
有 (b*(2^n) + r) <= (bm + r) < (b*(2^(n+1)) + r); 而 0 <= r < b;
b*(2^n) <= (b*(2^n) + r) <= a < (b*(2^(n+1)) + r) < (b*(2^(n+1)) + b);
有 b * (2^n) <= a < b * (2^(n+1)) + b; (不等式 2) 其實(shí)不等式2的右邊可縮小范圍為 a < b*(2^(n+1));
因?yàn)槿绻?a >= b*(2^(n+1)), 則m >= 2^(n+1) 明顯與不等式1矛盾. 我們有 b*(2^n) <= a < b*(2^(n+1)); (不等式3）
利用不等式3可求得2^n 和2^(n+1), 然后再利用折半查找（當(dāng)然也可以用其它更好的方法）查找滿足條件的m！
除法的非遞歸算法偽代碼如下：
Divide: a, b
//注意所有變量和常量都是任意長(zhǎng)整數(shù)，它們之間的各種操作和比較都應(yīng)另外實(shí)現(xiàn)，這里的描述只是為了方便說(shuō)明
if(a < b) return 0;
power1 = 1; power2= 2; n = 0; value1 = b * power1; value2 = b * power2;
while( !(value1 <= a && a < value2)) //利用不等式3，得到2^n和2^(n+1)
{
power1 = power2; power2 *= 2; //power1,power2 分別代表2^n和2^(n+1)
value1 = b * power1; // value1 = b * (2^n)
value2 = b * power2; // value2 = b * (2^(n+1))
n++; // 通過n來(lái)估計(jì)m有多大,當(dāng)然n遠(yuǎn)比m小得多
}
//從2^n到2^(n+1)中折半查找,總共有2^n+1個(gè)元素(當(dāng)然2^(n+1)不會(huì)
low = power1; high = power2;
while(low<=high){
mid = (low + high) / 2; //這里另外寫一個(gè)除以2的函數(shù)(比較簡(jiǎn)單)，不過也啟發(fā)我們可以用遞歸實(shí)現(xiàn)，可能又不一樣了
if(0 <= (a - b * mid) && (a - b * mid) < b) return mid; //找到m
else if((a - b * mid) < 0) high = mid; //繼續(xù)在前半?yún)^(qū)進(jìn)行查找
else low = mid; //繼續(xù)在后半?yún)^(qū)進(jìn)行查找
}
以上就是我的一點(diǎn)思路，提出來(lái)讓大家看看，希望大牛們給提提意見��！( 前面說(shuō)了那么多，只是為了讓大家更好理解，敬請(qǐng)?jiān)彛?
當(dāng)然本人是個(gè)菜鳥，編程能力不行，只好寫偽代碼，也不知寫得對(duì)不對(duì)，請(qǐng)大家不要砸雞蛋石頭，多提點(diǎn)寶貴意見！謝謝�。� |
|
免費(fèi)注冊(cè)
發(fā)表于 2008-05-14 01:50
