分治法實驗報告範文
來源:瑞文範文網 2.79W
一、實驗目的及要求
利用分治方法設計大整數乘法的遞歸算法,掌握分治法的基本思想和算法設計的基本步驟。
要求:設計十進制的大整數乘法,必須利用分治的思想編寫算法,利用c語言(或者c++語言)實現算法,給出程序的正確運行結果。(必須完成)
設計二進制的大整數乘法,要求利用分治的思想編寫遞歸算法,並可以實現多位數的乘法(利用數組實現),給出程序的正確運行結果。(任選)
二、算法描述
輸入兩個相同位數的大整數u,v
輸出uv的值
判斷大整數的位數i;
w=u/10^(i/2);
y=v/10^(i/2);
x=u-w*10^(i/2);
z= v-y*10^(i/2);
然後將w,x,y,z代入公式求得最後結果
uv=wy10^i+((w+x)(y+z)-wy-xz)10^(i/2)+xz
三、調試過程及運行結果
在實驗中我遇到的問題:
原來以爲這兩個大整數的位數不同,結果題目要求是相同位數的大整數 在寫10的多少次方時,寫的是10^(i/2),10^(i),結果不對,我就將它改成了for循環語句
四、實驗總結
在本次實驗中,我知道了分治算法,以及分治算法的基本思想。我還掌握了編寫大整數乘法的算法與步驟,以及如何修改在編寫程序時遇到的問題。