大數(shù)運算器程序設計文檔

1、 韶關(guān)學院計算機科學學院數(shù)據(jù)結(jié)構(gòu)課程設計題 目：大數(shù)運算器學生姓名：學 號：專 業(yè)：班 級： 指導教師姓名及職稱： 講師 起止時間： 年 月 年 月1.需求分析1.1課題背景及意義大數(shù)運算，顧名思義，就是很大的數(shù)值的數(shù)進行一系列的運算。隨著社會的發(fā)展，數(shù)據(jù)出現(xiàn)了指數(shù)般爆炸性增長，而在天文學，數(shù)學，遺傳學等傳統(tǒng)學科，所研究的數(shù)字往往幾百位甚至上千位，要求的精度也很高。但是在計算機中，由于字長的限制，計算機所能表示的范圍是有限的，當我們對比較小的數(shù)進行運算時，這樣的數(shù)值并沒有超出計算機的表示范圍，所以可以運算。但是當我們在實際的應用中進行大量的數(shù)據(jù)處理時，會發(fā)現(xiàn)參與運算的數(shù)往往超過計算機的基本數(shù)據(jù)

2、類型的表示范圍，比如在天文學時常運用到的“光年”這一單位，如果求距地球幾十光年的星球航天器所要到達的時間，計算機將無法對其進行運算。由于編程語言提供的基本數(shù)值數(shù)據(jù)類型表示的數(shù)值范圍有限，不能滿足較大規(guī)模的高精度數(shù)值計算，因此需要利用其他方法實現(xiàn)高精度數(shù)值的計算，于是產(chǎn)生了大數(shù)運算。大數(shù)運算主要有加、減、乘三種方法。既然在計算機中無法直接表示，那么大數(shù)到底如何進行運算呢，學習過數(shù)據(jù)結(jié)構(gòu)的都知道線性表，將大數(shù)拆分然后存儲在線性表中，不失為一個很好的辦法。1.2課題要求基本要求： 實現(xiàn)一個大整數(shù)（要求允許絕對值>232）的運算程序。要求程序讀入操作數(shù)A和B，選擇相應的加、減法或乘法運算符，然后

3、計算結(jié)果并輸出到屏幕上。選做內(nèi)容：（1）實現(xiàn)整除運算； （2）求出運算時間； （3）實現(xiàn)乘方運算； （4）圖形化操作界面。1.2.1程序規(guī)定格式（1）輸入的形式：正數(shù)的不同輸入符號位，輸入數(shù)為整型數(shù)，數(shù)位理論上為無限位。（2）程序所能達到的功能：能進行理論上無限位的數(shù)值之間所有整型數(shù)的四則運算。（3）輸出的形式：整型數(shù)據(jù)1.2.2測試的數(shù)據(jù)(1)正確的輸入以下是對兩個大數(shù)進行加減乘運算所得的正確結(jié)果：大數(shù)A：999888777666555444333222111000大數(shù)B：111222333444555666777888999000正確的運算結(jié)果：A+B：111111111111111111

4、1111111110000A-B：888666444221999777555333112000A*B：111209963037098814851876554444456814851901296370456889000000以下是對兩個大數(shù)進行除法運算所得的正確結(jié)果：大數(shù)A：999888777666555444333222111000大數(shù)B：1234567890正確的運算結(jié)果A/B：809909917280090157158(2)錯誤的輸入數(shù)A：999999999999.9數(shù)B：3錯誤的結(jié)果：33333333333332概要設計2.1問題解決的思路概述 首先是確定結(jié)構(gòu)化程序設計的流程圖，利用字符

5、串來進行比較數(shù)的大小，把程序主要分為五個部分：實現(xiàn)加法的模塊，實現(xiàn)減法的模塊，實現(xiàn)乘法的模塊，實現(xiàn)除法的模塊，實現(xiàn)求余的模塊，通過函數(shù)的嵌套調(diào)用來實現(xiàn)其功能，并通過編寫main主函數(shù)來實現(xiàn)大整數(shù)的正確輸入與正確輸出，最后通過調(diào)試程序來修改不足和優(yōu)化程序界面。2.2相關(guān)函數(shù)的的介紹與說明int sign=1; /sign 為符號位inline int compare(string str1,string str2)/定義比較兩個函數(shù)大小string ADD_INT(string str1,string str2) /加法string:size_type L1,L2;/定義L1，L2的類型int

6、int1=0,int2=0; /int2 記錄進位string:size_type tempint;/自定義tempintstring MUL_INT(string str1,string str2)/高精度乘法string DIVIDE_INT(string str1,string str2,int flag) /除法，flag=1時,返回商; flag=0時,返回余數(shù)string quotient,residue; /定義商和余數(shù)string tempstr/字符串變量string DIV_INT(string str1,string str2) return DIVIDE_INT(str

7、1,str2,1);/除法,返回商string MOD_INT(string str1,string str2) return DIVIDE_INT(str1,str2,0);/除法,返回余數(shù)printf()/顯示內(nèi)容2.3主程序的流程圖3調(diào)試分析4用戶使用說明程序運行操作步驟：(1) 運行66666.exe應用程序后出現(xiàn)主界面；(2) 首先，按下數(shù)字鍵輸入數(shù)A，按下回車鍵。在輸入數(shù)的過程中，如果發(fā)現(xiàn)輸入的某個數(shù)錯誤了，可按“退格”鍵從后往前一個個刪除掉；（3）輸入將要運算的運算符，如“加”是“+”，“減”是“-”，“乘”是“*”，“除”是“/”,“求余”是“%”；（4)輸入數(shù)B，按下回車鍵，

8、結(jié)果就會顯示在屏幕上。5測試結(jié)果 圖1程序主界面 圖2加法測試結(jié)果 圖3減法測試結(jié)果 圖4乘法測試結(jié)果 圖5除法測試結(jié)果參考文獻1嚴蔚敏，李冬梅，吳偉民 .數(shù)據(jù)結(jié)構(gòu)(C語言版) M.北京:人民郵電出版社，2011.2譚浩強 .C+面向?qū)ο蟪绦蛟O計(第二版) M.北京：中國鐵道出版社，2009.附錄:程序源碼#include <iostream>#include <string>using namespace std;inline int compare(string str1,string str2) /相等返回0，大于返回1，小于返回-1 if (str1.size(

9、)>str2.size() return 1; /長度長的整數(shù)大于長度小的整數(shù) else if (str1.size()<str2.size() return -1; else return pare(str2); /若長度相等，則頭到尾按位比較string SUB_INT(string str1,string str2);string ADD_INT(string str1,string str2) /高精度加法 int sign=1; /sign 為符號位 string str; if (str10='-') if (str20='-') sig

10、n=-1; str=ADD_INT(str1.erase(0,1),str2.erase(0,1); else str=SUB_INT(str2,str1.erase(0,1); else if (str20='-') str=SUB_INT(str1,str2.erase(0,1); else /把兩個整數(shù)對齊，短整數(shù)前面加0補齊 string:size_type L1,L2; int i; L1=str1.size(); L2=str2.size(); if (L1<L2) for (i=1;i<=L2-L1;i+) str1="0"+str

11、1; else for (i=1;i<=L1-L2;i+) str2="0"+str2; int int1=0,int2=0; /int2 記錄進位 for (i=str1.size()-1;i>=0;i-) int1=(int(str1i)-'0'+int(str2i)-'0'+int2)%10; int2=(int(str1i)-'0'+int(str2i)-'0'+int2)/10; str=char(int1+'0')+str; if (int2!=0) str=char(i

12、nt2+'0')+str; /運算后處理符號位 if (sign=-1)&&(str0!='0') str="-"+str; return str;string SUB_INT(string str1,string str2) /高精度減法 int sign=1; /sign 為符號位 string str; int i,j; if (str20='-') str=ADD_INT(str1,str2.erase(0,1); else int res=compare(str1,str2); if (res=0)

13、return "0" if (res<0) sign=-1; string temp =str1; str1=str2; str2=temp; string:size_type tempint; tempint=str1.size()-str2.size(); for (i=str2.size()-1;i>=0;i-) if (str1i+tempint<str2i) j=1; while (1) /zhao4zhong1添加 if (str1i+tempint-j='0') str1i+tempint-j='9' j+;

14、else str1i+tempint-j=char(int(str1i+tempint-j)-1); break; str=char(str1i+tempint-str2i+':')+str; else str=char(str1i+tempint-str2i+'0')+str; for (i=tempint-1;i>=0;i-) str=str1i+str; /去除結(jié)果中多余的前導0 str.erase(0,str.find_first_not_of('0'); if (str.empty() str="0" if (

15、sign=-1) && (str0!='0') str ="-"+str; return str;string MUL_INT(string str1,string str2) /高精度乘法 int sign=1; /sign 為符號位 string str; if (str10='-') sign*=-1; str1 =str1.erase(0,1); if (str20='-') sign*=-1; str2 =str2.erase(0,1); int i,j; string:size_type L1,L2

16、; L1=str1.size(); L2=str2.size(); for (i=L2-1;i>=0;i-) /模擬手工乘法豎式 string tempstr; int int1=0,int2=0,int3=int(str2i)-'0' if (int3!=0) for (j=1;j<=(int)(L2-1-i);j+) tempstr="0"+tempstr; for (j=L1-1;j>=0;j-) int1=(int3*(int(str1j)-'0')+int2)%10; int2=(int3*(int(str1j)-

17、'0')+int2)/10; tempstr=char(int1+'0')+tempstr; if (int2!=0) tempstr=char(int2+'0')+tempstr; str=ADD_INT(str,tempstr); /去除結(jié)果中的前導0 str.erase(0,str.find_first_not_of('0'); if (str.empty() str="0" if (sign=-1) && (str0!='0') str="-"+str

18、; return str;string DIVIDE_INT(string str1,string str2,int flag) /高精度除法。flag=1時,返回商; flag=0時,返回余數(shù) string quotient,residue; /定義商和余數(shù) int sign1=1,sign2=1; if (str2 = "0") /判斷除數(shù)是否為0 quotient= "ERROR!" residue = "ERROR!" if (flag=1) return quotient; else return residue ; if

19、(str1="0") /判斷被除數(shù)是否為0 quotient="0" residue ="0" if (str10='-') str1 = str1.erase(0,1); sign1 *= -1; sign2 = -1; if (str20='-') str2 = str2.erase(0,1); sign1 *= -1; int res=compare(str1,str2); if (res<0) quotient="0" residue =str1; else if (r

20、es = 0) quotient="1" residue ="0" else string:size_type L1,L2; L1=str1.size(); L2=str2.size(); string tempstr; tempstr.append(str1,0,L2-1); for (int i=L2-1;i<L1;i+) /模擬手工除法豎式 tempstr=tempstr+str1i; tempstr.erase(0,tempstr.find_first_not_of('0');/添加 if (tempstr.empty()

21、tempstr="0"/添加 for (char ch='9'ch>='0'ch-) /試商 string str; str=str+ch; if (compare(MUL_INT(str2,str),tempstr)<=0) quotient=quotient+ch; tempstr =SUB_INT(tempstr,MUL_INT(str2,str); break; residue=tempstr; /去除結(jié)果中的前導0 quotient.erase(0,quotient.find_first_not_of('0'); if (quotient.empty() quotient="0" if (sign1=-1)&&(quotient0!='0') quotient="-"+quotient; if (sign2=-1)&&(residue 0!='0') residue ="-"+residue ; if (flag=1) return quotient; else return residue ;string DIV_INT(string