分治法實驗報告範文

一、實驗目的及要求

利用分治方法設計大整數乘法的遞迴演算法，掌握分治法的基本思想和演算法設計的基本步驟。

要求：設計十進位制的大整數乘法，必須利用分治的思想編寫演算法，利用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迴圈語句

四、實驗總結

在本次實驗中，我知道了分治演算法，以及分治演算法的基本思想。我還掌握了編寫大整數乘法的演算法與步驟，以及如何修改在編寫程式時遇到的問題。