算法大整數(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：算法策略的選擇采用蠻力算法開始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=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)（注釋）void CBigCountDlg:ChangeToInt() /將字符串存儲(chǔ)的大整數(shù)轉(zhuǎn)化為整形數(shù)組存儲(chǔ)每位數(shù)組存儲(chǔ)6位UpdateData();int len_op1,len_op2;

3、/存放兩個(gè)字符串長(zhǎng)度且len_op1存放較長(zhǎng)字符串的長(zhǎng)度len_op1=m_operate1.GetLength();len_op2=m_operate2.GetLength();if(len_op10;i=i-6) /數(shù)組的每個(gè)元素存放6個(gè)字符串if(i5) /num1中存放較長(zhǎng)的字符串m_operate1 num1t1=atoi(m_operate1.Mid(i-5,6); t1+;else break;if(t1!=m1)num1t1=atoi(m_operate1.Mid(0,i+1);int t2=0;for(int j=len_op2-1;j0;j=j-6) /num2存放字符串m

4、_operate2if(j5) 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=;jin=0;for( i=0;i100;i+) /初始化num1i=num2i=heni=0; ChangeToInt(); /將字符型大整數(shù)轉(zhuǎn)化為整數(shù)數(shù)組存儲(chǔ)for(j=0;j=0) /有進(jìn)位jin=1;else

5、/沒(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(int l=j-1;l=0;l-)if(henl10)bb.Format(%d,henl);bb=00000+bb;else if(henl100)bb.Format(%d,henl);bb=0000+bb;else if(henl1000)bb.Format(%d,henl);bb=000+bb;else if(henl10000)bb.Format(%d,henl);bb=00+b

6、b;else if(henl100000)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ù)組中除最高位的一位并沒(méi)有達(dá)到6位時(shí)如123應(yīng)該輸出000123而不是123.。解決方法判斷大小在數(shù)前加0。二：

7、實(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為低位是否向此位借位。若 chai0則修正為chai+=1000000;且jie=1。3：算法策略的選擇：采用蠻力法。4：程序流程圖開始 以字符形式輸入兩個(gè)大整數(shù)m_operate1,m_operate2將m

8、_operate1和m_operate2轉(zhuǎn)化為整形數(shù)組的形式存儲(chǔ)每位6位。Num1,num2,m1,m2為兩個(gè)數(shù)組的長(zhǎng)度。int j=0聲明變量并初始化判斷im1？ Nchai=num1i-num2i-jie; Y 從高位到低位找到cha中第一位不為0的下標(biāo)記位beginchai0&(i!=m1-1) N輸出結(jié)果 將hen中的元素由高位到低位轉(zhuǎn)化為字符串輸出jie=0;(不需要借位)jie=1;（需要借位）chai+=1000000; Y結(jié)束i+ 5：算法時(shí)間復(fù)雜度與空間復(fù)雜度（推導(dǎo)過(guò)程）6：程序?qū)崿F(xiàn)（注釋）void CBigCountDlg:OnButtonCut() /實(shí)現(xiàn)兩個(gè)大整數(shù)的減法

9、for(int q=0;qlen_op1)comp=1;ChangeToInt();int jie=0;for(int i=0;im1;i+)chai=num1i-num2i-jie;if(chai=0;p-)if(chap!=0)begin=p;break;CString aa,bb;aa.Format(%d,chabegin);for(int l=begin-1;l=0;l-)if(chal10)bb.Format(%d,chal);bb=00000+bb;else if(chal100)bb.Format(%d,chal);bb=0000+bb;else if(chal1000)bb.F

10、ormat(%d,chal);bb=000+bb;else if(chal10000)bb.Format(%d,chal);bb=00+bb;else if(chal100000)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)題算法策略；算法的方法

11、）相減的結(jié)果課能為0，但結(jié)果是存在數(shù)組中的，判斷是否為0應(yīng)從最高為一次檢驗(yàn)數(shù)組中的每一位。三：實(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：算法策略的選擇 采用蠻力

12、法4：程序流程圖開始 以字符形式輸入兩個(gè)大整數(shù)m_operate1,m_operate2聲明變量并初始化 從高位到低位找到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é)束判斷t1m2？ N Ybuffert1=(at1*b+jin)%10000; jin=(at1*b+jin)/10000;判斷t1m1？t1+; N Y判斷jin!=0？處理最高位進(jìn)位jic+i=jin;t1+; buffert1=

13、jin; yt1-;Len=t1;為buffer數(shù)組的長(zhǎng)度C為當(dāng)前處理的num2數(shù)組元素的下標(biāo)，i=0判斷i9999？ N Yj+;jic+i=jic+i-10000; jin=1;5：算法時(shí)間復(fù)雜度與空間復(fù)雜度（推導(dǎo)過(guò)程）6：程序?qū)崿F(xiàn)（注釋）void 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();if(len_op10;i=i-4

14、)if(i3) num1t1=atoi(m_operate1.Mid(i-3,4); t1+;else break;if(t1!=m1)num1t1=atoi(m_operate1.Mid(0,i+1);int t2=0;for(int j=len_op2-1;j0;j=j-4)if(j3) 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;i100;i+) /初始化

15、num1i=num2i=jii=bufferi=0;ChangeToInt4(); /將字符串表示的大整數(shù)存入長(zhǎng)整形數(shù)組for(int t1=0;t1=0;j-)if(jij!=0)begin=j;break;aa=bb=;aa.Format(%d,jibegin);for(int l=begin-1;l=0;l-)if(jil10)bb.Format(%d,jil); bb=000+bb;else if(jil100)bb.Format(%d,jil);bb=00+bb;else if(jil=len_da2-1? N Ycha=len_da1-len_da2;記錄兩數(shù)相差的位數(shù)。若data

16、1比data2從高位開始算起大。則減去data2若小data2與data1從其第二高位開始相減。從高位到低位找到count 中第一位不為0的下標(biāo)記位begin 若data1中較高位出現(xiàn)0，則修正len_da1的大小輸出結(jié)果 將count中的元素由高位到低位轉(zhuǎn)化為字符串輸出hu=len_da1-1;結(jié)束5：算法時(shí)間復(fù)雜度與空間復(fù)雜度（推導(dǎo)過(guò)程）6：程序?qū)崿F(xiàn)（注釋） int CBigCountDlg:Jian(int l,int lon) /從被除數(shù)中減去除數(shù) int buffer100=0;int jie=0; int di=l-lon+1; /di記錄被除數(shù)與除數(shù)開始相減的位數(shù)for(int

17、i=0;ilen_da2;i+)bufferdi+i=data1di+i-data2i-jie;if(bufferdi+i0&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=0;k-) if(data1k=0) xiao+; else break; len_da1-=xiao; return 1;void CBigCountDlg:OnButtonDive()

18、for(int k=0;k100;k+) /初始化num1k=num2k=countk=0; UpdateData();len_da1=m_operate1.GetLength();len_da2=m_operate2.GetLength();for(int i=0;ilen_da1;i+) /每位存儲(chǔ)一位data1len_da1-i-1=atoi(m_operate1.Mid(i,1);for(int j=0;j=len_da2-1;)cha=len_da1-len_da2;xing=Jian(hu,len_da2);if(xing=-1) Jian(hu,len_da2+1); cha-;countcha+;hu=l