算法大整數(shù)的四則運(yùn)算

1、姓名： 胡雙興 學(xué)號(hào)：090610213 班級(jí)：090413一：實(shí)驗(yàn)題目： 大整數(shù)加法1問(wèn)題分析： 處理多位整數(shù)的加法，這些整數(shù)無(wú)法在計(jì)算機(jī)硬件允許的范圍內(nèi)表示和處理。2：數(shù)學(xué)模型輸入時(shí)以字符串的形式表示大整數(shù)。采用數(shù)組存放大整數(shù)，每位數(shù)組存放6位。Num1,num2存放兩個(gè)加數(shù)。Hen存放和，jin表示進(jìn)位。則heni=num1i+num2i+jin,此時(shí)的jin表示的是來(lái)自低位的進(jìn)位。若heni超過(guò)1000000，則heni修正為heni-1000000,且jin=1。.3：算法策略的選擇采用蠻力算法開(kāi)始4：程序流程圖以字符形式輸入兩個(gè)大整數(shù)m_operate1,m_operate2聲明變

2、量并初始化將m_operate1和m_operate2轉(zhuǎn)化為整形數(shù)組的形式存儲(chǔ)每位6位。Num1,num2,m1,m2為兩個(gè)數(shù)組的長(zhǎng)度。int j=0判斷j<m1? Nhenj=num1j+num2j+jin-1000000;從低位開(kāi)始相加每位都當(dāng)成有進(jìn)位處理 Y 判斷jin=1?處理最高位進(jìn)位判斷henj>=0)？（有無(wú)進(jìn)位） Nhenj=1;henj=num1j+num2j+jin;jin=0;無(wú)進(jìn)位 Y Yj-;jin=1;有進(jìn)位 j+;輸出結(jié)果 將hen中的元素由高位到低位轉(zhuǎn)化為字符串輸出結(jié)束5：算法時(shí)間復(fù)雜度與空間復(fù)雜度（推導(dǎo)過(guò)程）6：程序?qū)崿F(xiàn)（注釋?zhuān)﹙oid CBigC

3、ountDlg:ChangeToInt() /將字符串存儲(chǔ)的大整數(shù)轉(zhuǎn)化為整形數(shù)組存儲(chǔ)每位數(shù)組存儲(chǔ)6位UpdateData();int len_op1,len_op2;/存放兩個(gè)字符串長(zhǎng)度且len_op1存放較長(zhǎng)字符串的長(zhǎng)度len_op1=m_operate1.GetLength();len_op2=m_operate2.GetLength();if(len_op1<len_op2)/若m_operate1長(zhǎng)度小于m_operate2長(zhǎng)度交換兩字符串CString temp;temp=m_operate1;m_operate1=m_operate2;m_operate2=temp;int

4、hu;hu=len_op1;len_op1=len_op2;len_op2=hu;m1=len_op1/6; /m1是m_operate1所用數(shù)組的長(zhǎng)度 if(len_op1%6!=0)m1+;m2=len_op2/6; /m2是m_operate2所用數(shù)組的長(zhǎng)度if(len_op2%6!=0)m2+;int t1=0;for(int i=len_op1-1;i>0;i=i-6) /數(shù)組的每個(gè)元素存放6個(gè)字符串if(i>5) /num1中存放較長(zhǎng)的字符串m_operate1 num1t1=atoi(m_operate1.Mid(i-5,6); t1+;else break;if(t

5、1!=m1)num1t1=atoi(m_operate1.Mid(0,i+1);int t2=0;for(int j=len_op2-1;j>0;j=j-6) /num2存放字符串m_operate2if(j>5) num2t2=atoi(m_operate2.Mid(j-5,6); t2+;elsebreak;if(t2!=m2)num2t2=atoi(m_operate2.Mid(0,j+1);void CBigCountDlg:OnButtonAdd() int jin,i,j; /jin存儲(chǔ)進(jìn)位 CString aa,bb; /存放輸出的值aa=bb=""

6、;jin=0;for( i=0;i<100;i+) /初始化num1i=num2i=heni=0; ChangeToInt(); /將字符型大整數(shù)轉(zhuǎn)化為整數(shù)數(shù)組存儲(chǔ)for(j=0;j<m1;j+) /從低位開(kāi)始相加每位都當(dāng)成有進(jìn)位處理 henj=num1j+num2j+jin-1000000;if(henj>=0) /有進(jìn)位jin=1;else /沒(méi)有進(jìn)位修正henj的值henj=num1j+num2j+jin;jin=0; if(jin=1) /處理最高位的進(jìn)位 henj=1; else j-; /輸出結(jié)果aa.Format("%d",henj);for

7、(int l=j-1;l>=0;l-)if(henl<10)bb.Format("%d",henl);bb="00000"+bb;else if(henl<100)bb.Format("%d",henl);bb="0000"+bb;else if(henl<1000)bb.Format("%d",henl);bb="000"+bb;else if(henl<10000)bb.Format("%d",henl);bb="

8、;00"+bb;else if(henl<100000)bb.Format("%d",henl);bb="0"+bb;elsebb.Format("%d",henl);aa+=bb; MessageBox(aa);7：使用方法，如如何啟動(dòng)程序，關(guān)閉程序，對(duì)輸入輸出要求可輸入兩個(gè)非負(fù)的大整數(shù)進(jìn)行運(yùn)算。8：測(cè)試數(shù)據(jù)數(shù)據(jù)及結(jié)果說(shuō)明（正確數(shù)據(jù)以及非正確數(shù)據(jù)）正確數(shù)據(jù)： 錯(cuò)誤數(shù)據(jù)：說(shuō)明：沒(méi)有在輸入大整數(shù)時(shí)判斷正負(fù)。9：總結(jié)（如調(diào)試過(guò)程中遇到的問(wèn)題算法策略；算法的方法） 輸出時(shí)按照，存放和的數(shù)組hen,由高位到低位輸出，數(shù)組中除最

9、高位的一位并沒(méi)有達(dá)到6位時(shí)如123應(yīng)該輸出000123而不是123.。解決方法判斷大小在數(shù)前加0。二：實(shí)驗(yàn)題目大整數(shù)減法1：?jiǎn)栴}分析處理多位整數(shù)的減法，這些整數(shù)無(wú)法在計(jì)算機(jī)硬件允許的范圍內(nèi)表示和處理。2：數(shù)學(xué)模型輸入時(shí)以字符串的形式表示大整數(shù)。采用數(shù)組存放大整數(shù)，每位數(shù)組存放6位。將輸入的兩個(gè)大整數(shù)處理為位數(shù)較多的一個(gè)減去位數(shù)較少的一個(gè)，若被減數(shù)比減數(shù)位數(shù)少結(jié)果前面加“-”。Num1,num2存放被減數(shù)和減數(shù)。cha存放差，jie表示借位。則chai=num1i-num2i-jie;jie為低位是否向此位借位。若 chai<0則修正為chai+=1000000;且jie=1。3：算法策略

10、的選擇：采用蠻力法。4：程序流程圖開(kāi)始 以字符形式輸入兩個(gè)大整數(shù)m_operate1,m_operate2將m_operate1和m_operate2轉(zhuǎn)化為整形數(shù)組的形式存儲(chǔ)每位6位。Num1,num2,m1,m2為兩個(gè)數(shù)組的長(zhǎng)度。int j=0聲明變量并初始化判斷i<m1？ Nchai=num1i-num2i-jie; Y 從高位到低位找到cha中第一位不為0的下標(biāo)記位beginchai<0&&(i!=m1-1) N輸出結(jié)果 將hen中的元素由高位到低位轉(zhuǎn)化為字符串輸出jie=0;(不需要借位)jie=1;（需要借位）chai+=1000000; Y結(jié)束i+ 5：

11、算法時(shí)間復(fù)雜度與空間復(fù)雜度（推導(dǎo)過(guò)程）6：程序?qū)崿F(xiàn)（注釋?zhuān)﹙oid CBigCountDlg:OnButtonCut() /實(shí)現(xiàn)兩個(gè)大整數(shù)的減法for(int q=0;q<100;q+)num1q=num2q=chaq=0;UpdateData();bool comp=0; /若comp為0則m_operate1大于或等于m_oprate2若為1則相反int len_op1,len_op2;len_op1=m_operate1.GetLength();len_op2=m_operate2.GetLength();if(len_op2>len_op1)comp=1;ChangeToI

12、nt();int jie=0;for(int i=0;i<m1;i+)chai=num1i-num2i-jie;if(chai<0&&(i!=m1-1)jie=1;chai+=1000000;elsejie=0;int begin=0; /從高位到低位找到cha中第一位部位0的下標(biāo)幾位beginfor(int p=99;p>=0;p-)if(chap!=0)begin=p;break;CString aa,bb;aa.Format("%d",chabegin);for(int l=begin-1;l>=0;l-)if(chal<

13、10)bb.Format("%d",chal);bb="00000"+bb;else if(chal<100)bb.Format("%d",chal);bb="0000"+bb;else if(chal<1000)bb.Format("%d",chal);bb="000"+bb;else if(chal<10000)bb.Format("%d",chal);bb="00"+bb;else if(chal<1000

14、00)bb.Format("%d",chal);bb="0"+bb;elsebb.Format("%d",chal);aa+=bb;if(comp)aa="-"+aa;MessageBox(aa);7：使用方法，如如何啟動(dòng)程序，關(guān)閉程序，對(duì)輸入輸出要求輸入兩個(gè)非負(fù)數(shù)的大整數(shù)的減法。8：測(cè)試數(shù)據(jù)數(shù)據(jù)及結(jié)果說(shuō)明（正確數(shù)據(jù)以及非正確數(shù)據(jù)）正確數(shù)據(jù)： 錯(cuò)誤數(shù)據(jù)：說(shuō)明：未考慮負(fù)數(shù)大整數(shù)相減的情況。9：總結(jié)（如調(diào)試過(guò)程中遇到的問(wèn)題算法策略；算法的方法）相減的結(jié)果課能為0，但結(jié)果是存在數(shù)組中的，判斷是否為0應(yīng)從最高為一次檢驗(yàn)數(shù)組

15、中的每一位。三：實(shí)驗(yàn)題目大數(shù)乘法1：?jiǎn)栴}分析處理多位整數(shù)的加法，這些整數(shù)無(wú)法在計(jì)算機(jī)硬件允許的范圍內(nèi)表示和處理。考慮，大整數(shù)與正常較小的數(shù)相乘，和兩個(gè)大整數(shù)相乘。2：數(shù)學(xué)模型輸入時(shí)以字符串的形式表示大整數(shù)。采用長(zhǎng)整形數(shù)組存放大整數(shù)，每位數(shù)組存放4位。Num1,num2存放兩個(gè)加數(shù)。ji存放積。Num2數(shù)組中的元素依次從低位到高位（相應(yīng)大整數(shù)的低位到高位）當(dāng)成正常整數(shù)與數(shù)組num1的每一位相乘。jin表示進(jìn)位。結(jié)果存放在buffer數(shù)組中。將buffer中的元素乘以相應(yīng)的權(quán)值賦值給ji數(shù)組。3：算法策略的選擇 采用蠻力法4：程序流程圖開(kāi)始 以字符形式輸入兩個(gè)大整數(shù)m_operate1,m_ope

16、rate2聲明變量并初始化 從高位到低位找到cha中第一位不為0的下標(biāo)記位begin輸出結(jié)果 將hen中的元素由高位到低位轉(zhuǎn)化為字符串輸出將m_operate1和m_operate2轉(zhuǎn)化為整形數(shù)組的形式存儲(chǔ)每位6位。Num1,num2,m1,m2為兩個(gè)數(shù)組的長(zhǎng)度。int t1=t2=0結(jié)束判斷t1<m2？ N Ybuffert1=(at1*b+jin)%10000; jin=(at1*b+jin)/10000;判斷t1<m1？t1+; N Y判斷jin!=0？處理最高位進(jìn)位jic+i=jin;t1+; buffert1=jin; yt1-;Len=t1;為buffer數(shù)組的長(zhǎng)度C為

17、當(dāng)前處理的num2數(shù)組元素的下標(biāo)，i=0判斷i<=len？ Yjic+i+=bufferi+jin;jin=0;判斷jic+i>9999？ N Yj+;jic+i=jic+i-10000; jin=1;5：算法時(shí)間復(fù)雜度與空間復(fù)雜度（推導(dǎo)過(guò)程）6：程序?qū)崿F(xiàn)（注釋?zhuān)﹙oid CBigCountDlg:ChangeToInt4() /將字符串表示的長(zhǎng)整數(shù)轉(zhuǎn)化為長(zhǎng)整形數(shù)組表示，每位數(shù)組存放4位。 UpdateData();int len_op1,len_op2;/len_op1=m_operate1.GetLength();len_op2=m_operate2.GetLength();i

18、f(len_op1<len_op2)CString temp;temp=m_operate1;m_operate1=m_operate2;m_operate2=temp;int hu;hu=len_op1;len_op1=len_op2;len_op2=hu;m1=len_op1/4; if(len_op1%4!=0)m1+;m2=len_op2/4;if(len_op2%4!=0)m2+;int t1=0;for(int i=len_op1-1;i>0;i=i-4)if(i>3) num1t1=atoi(m_operate1.Mid(i-3,4); t1+;else bre

19、ak;if(t1!=m1)num1t1=atoi(m_operate1.Mid(0,i+1);int t2=0;for(int j=len_op2-1;j>0;j=j-4)if(j>3) num2t2=atoi(m_operate2.Mid(j-3,4); t2+;else break;if(t2!=m2)num2t2=atoi(m_operate2.Mid(0,j+1);void CBigCountDlg:OnButtonMulti() for(int i=0;i<100;i+) /初始化num1i=num2i=jii=bufferi=0;ChangeToInt4(); /

20、將字符串表示的大整數(shù)存入長(zhǎng)整形數(shù)組for(int t1=0;t1<m2;t1+) /num2t1作為一個(gè)非大整數(shù)與數(shù)組num1表示的長(zhǎng)整數(shù)相乘SingleMul(num1,num2t1,t1);int begin;CString aa,bb;for(int j=99;j>=0;j-)if(jij!=0)begin=j;break;aa=bb=""aa.Format("%d",jibegin);for(int l=begin-1;l>=0;l-)if(jil<10)bb.Format("%d",jil); bb=

21、"000"+bb;else if(jil<100)bb.Format("%d",jil);bb="00"+bb;else if(jil<1000)bb.Format("%d",jil); bb="0"+bb;elsebb.Format("%d",jil);aa+=bb;MessageBox(aa);7：使用方法，如如何啟動(dòng)程序，關(guān)閉程序，對(duì)輸入輸出要求 輸入兩個(gè)非負(fù)的的大整數(shù)的乘法8：測(cè)試數(shù)據(jù)數(shù)據(jù)及結(jié)果說(shuō)明（正確數(shù)據(jù)以及非正確數(shù)據(jù)）正確數(shù)據(jù)：錯(cuò)誤數(shù)據(jù)：說(shuō)明：未考慮

22、負(fù)數(shù)參與乘法運(yùn)算的情況。9：總結(jié)（如調(diào)試過(guò)程中遇到的問(wèn)題算法策略；算法的方法） 將兩個(gè)大數(shù)相乘的情況，分解為非大整數(shù)與大整數(shù)相乘，最終分解為兩個(gè)非大整數(shù)相乘，再將所的的結(jié)果用加法整合在一起，要注意相應(yīng)的權(quán)值體現(xiàn)在數(shù)組的下表上。四：實(shí)驗(yàn)題目大整數(shù)除法1：?jiǎn)栴}分析處理多位整數(shù)的除法，這些整數(shù)無(wú)法在計(jì)算機(jī)硬件允許的范圍內(nèi)表示和處理。2：數(shù)學(xué)模型 一個(gè)較大的大整數(shù)除以一個(gè)整數(shù)，先把除數(shù)乘以相應(yīng)的權(quán)值（在后面加0）使它成為小于被除數(shù)的最大的數(shù)。則用被除數(shù)減去除數(shù)，直到被除數(shù)小于除數(shù)，記錄減去的次數(shù)，則這個(gè)次數(shù)就為商，剩余的被除數(shù)就為余數(shù)。3：算法策略的選擇采用蠻力法4：程序流程圖開(kāi)始 以字符形式輸入兩個(gè)

23、大整數(shù)m_operate1,m_operate2聲明變量并初始化將m_operate1和m_operate2轉(zhuǎn)化為整形數(shù)組的形式存儲(chǔ)每位1位。data1,data2,len_da1,len_da2為兩個(gè)數(shù)組的長(zhǎng)度。hu=len_da1-1hu>=len_da2-1? N Ycha=len_da1-len_da2;記錄兩數(shù)相差的位數(shù)。若data1比data2從高位開(kāi)始算起大。則減去data2若小data2與data1從其第二高位開(kāi)始相減。從高位到低位找到count 中第一位不為0的下標(biāo)記位begin 若data1中較高位出現(xiàn)0，則修正len_da1的大小輸出結(jié)果 將count中的元素由高位

24、到低位轉(zhuǎn)化為字符串輸出hu=len_da1-1;結(jié)束5：算法時(shí)間復(fù)雜度與空間復(fù)雜度（推導(dǎo)過(guò)程）6：程序?qū)崿F(xiàn)（注釋?zhuān)?int CBigCountDlg:Jian(int l,int lon) /從被除數(shù)中減去除數(shù) int buffer100=0;int jie=0; int di=l-lon+1; /di記錄被除數(shù)與除數(shù)開(kāi)始相減的位數(shù)for(int i=0;i<len_da2;i+)bufferdi+i=data1di+i-data2i-jie;if(bufferdi+i<0)bufferdi+i+=10; jie=1;elsejie=0; if(jie>0&&

25、lon=len_da2) /此時(shí)從被除數(shù)中取到的與除數(shù)相同長(zhǎng)度的一段比除數(shù)小 return -1; /返回-1將除數(shù)較于被除數(shù)后撤一位在相減 else /此時(shí)將buffer新負(fù)的值傳給被除數(shù) bufferdi+i=data1di+i-jie; for(int j=l-lon+1;j<=l-lon+1+len_da2;j+) data1j=bufferj; int xiao=0; /記錄被除數(shù)的長(zhǎng)度減少多少 for(int k=len_da1-1;l>=0;k-) if(data1k=0) xiao+; else break; len_da1-=xiao; return 1;void CBigCountDlg:OnButtonDive() for(int k=0;k<100;k+) /初始化num1k=num2k=countk=0; UpdateData();len_da1=m_operate1.GetLength();len_da2=m_operate2.GetLength();for(int i=0;i<