




已閱讀5頁,還剩26頁未讀, 繼續免費閱讀
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第一章高精度計算,1,利用計算機進行數值計算,有時會遇到這樣的問題:有些計算要求精度高,希望計算的數的位數可達幾十位甚至幾百位,雖然計算機的計算精度也算較高了,但因受到硬件的限制,往往達不到實際問題所要求的精度。我們可以利用程序設計的方法去實現這樣的高精度計算。介紹常用的幾種高精度計算的方法。高精度計算中需要處理好以下幾個問題:(1)數據的接收方法和存貯方法數據的接收和存貯:當輸入的數很長時,可采用字符串方式輸入,這樣可輸入數字很長的數,利用字符串函數和操作運算,將每一位數取出,存入數組中。另一種方法是直接用循環加數組方法輸入數據。voidinit(inta)/傳入一個數組strings;cins;/讀入字符串sa0=s.length();/用a0計算字符串s的位數for(i=1;i=10)ci%=10;+ci+1;減法借位:if(aibi)-ai+1;ai+=10;ci=ai-bi;乘法進位:ci+j-1=ai*bj+x+ci+j-1;x=ci+j-1/10;ci+j-1%=10;(4)商和余數的求法商和余數處理:視被除數和除數的位數情況進行處理.,3,【例1】高精度加法。輸入兩個正整數,求它們的和。【分析】輸入兩個數到兩個變量中,然后用賦值語句求它們的和,輸出。但是,我們知道,在C+語言中任何數據類型都有一定的表示范圍。而當兩個被加數很大時,上述算法顯然不能求出精確解,因此我們需要尋求另外一種方法。在讀小學時,我們做加法都采用豎式方法,如圖1。這樣,我們方便寫出兩個整數相加的算法。,如果我們用數組A、B分別存儲加數和被加數,用數組C存儲結果。則上例有A1=6,A2=5,A3=8,B1=5,B2=5,B3=2,C4=1,C3=1,C2=1,C1=1,兩數相加如圖2所示。,4,因此,算法描述如下:intc100;voidadd(inta,intb)/a,b,c都為數組,分別存儲被加數、加數、結果inti=1,x=0;/x是進位while(i=a數組長度)|(i=b數組的長度)ci=ai+bi+x;/第i位相加并加上次的進位x=ci/10;/向高位進位ci%=10;/存儲第i位的值i+;/位置下標變量,5,通常,讀入的兩個整數用可用字符串來存儲,程序設計如下:#include#include#includeusingnamespacestd;intmain()chara1100,b1100;inta100,b100,c100,lena,lenb,lenc,i,x;memset(a,0,sizeof(a);memset(b,0,sizeof(b);memset(c,0,sizeof(c);gets(a1);gets(b1);/輸入加數與被加數lena=strlen(a1);lenb=strlen(b1);for(i=0;i=lena-1;i+)alena-i=a1i-48;/加數放入a數組for(i=0;i=lenb-1;i+)blenb-i=b1i-48;/加數放入b數組lenc=1;x=0;,6,while(lenc=1;i-)coutci;/輸出結果coutendl;return0;,7,【例2】高精度減法。輸入兩個正整數,求它們的差。【算法分析】類似加法,可以用豎式求減法。在做減法運算時,需要注意的是:被減數必須比減數大,同時需要處理借位。高精度減法的參考程序:#include#include#includeusingnamespacestd;intmain()inta256,b256,c256,lena,lenb,lenc,i;charn256,n1256,n2256;memset(a,0,sizeof(a);memset(b,0,sizeof(b);memset(c,0,sizeof(c);,8,printf(Inputminuend:);gets(n1);/輸入被減數printf(Inputsubtrahend:);gets(n2);/輸入減數if(strlen(n1)n2時,返回正整數;n1n2時,返回負整數/處理被減數和減數,交換被減數和減數strcpy(n,n1);/將n1數組的值完全賦值給n數組strcpy(n1,n2);strcpy(n2,n);cout-;/交換了減數和被減數,結果為負數lena=strlen(n1);lenb=strlen(n2);for(i=0;i=lena-1;i+)alena-i=int(n1i-0);/被減數放入a數組for(i=0;i=1;i-)coutci;/輸出結果coutendl;return0;,10,【例3】高精度乘法。輸入兩個正整數,求它們的積。【算法分析】類似加法,可以用豎式求乘法。在做乘法運算時,同樣也有進位,同時對每一位進行乘法運算時,必須進行錯位相加,如圖3、圖4。分析c數組下標的變化規律,可以寫出如下關系式:ci=ci+c”i+由此可見,ci跟ai*bj乘積有關,跟上次的進位有關,還跟原ci的值有關,分析下標規律,有ci+j-1=ai*bj+x+ci+j-1;x=ci+j-1/10;ci+j-1%=10;,11,高精度乘法的參考程序:#include#include#includeusingnamespacestd;intmain()chara1100,b1100;inta100,b100,c100,lena,lenb,lenc,i,j,x;memset(a,0,sizeof(a);memset(b,0,sizeof(b);memset(c,0,sizeof(c);gets(a1);gets(b1);lena=strlen(a1);lenb=strlen(b1);for(i=0;i=lena-1;i+)alena-i=a1i-48;for(i=0;i=1;i-)coutci;coutb;lena=strlen(a1);for(i=0;is;/讀入字符串sa0=s.length();/用a0計算字符串s的位數for(i=1;i0;i-)coutai;coutbi)return1;if(ai=0)ci+;jian(a,tmp);/用減法來模擬while(c00,22,intmain()memset(a,0,sizeof(a);memset(b,0,sizeof(b);memset(c,0,sizeof(c);init(a);init(b);chugao(a,b,c);print(c);print(a);return0;,23,【例6】回文數【問題描述】若一個數(首位不為零)從左向右讀與從右向左讀都是一樣,我們就將其稱之為回文數。例如:給定一個10進制數56,將56加65(即把56從右向左讀),得到121是一個回文數。又如,對于10進制數87,STEPl:8778=165STEP2:165561=726STEP3:7266271353STEP4:1353+3531=4884在這里的一步是指進行了一次N進制的加法,上例最少用了4步得到回文數4884。寫一個程序,給定一個N(2N10或N=16)進制數M求最少經過幾步可以得到回文數。如果在30步以內(包含30步)不可能得到回文數,則輸出“Impossible”【輸入樣例】:987【輸出樣例】:6【算法分析】N進制運算1、當前位規范由%10改為%n2、進位處理由/10改為/n3、其他運算規則不變,24,【參考程序】#include#includeusingnamespacestd;intn,a101,b101,ans,i;voidinit(inta)/將數串s轉化為整數數組astrings;cinns;/讀入字符串smemset(a,0,sizeof(a);/數組a清0a0=s.length();/用a0計算字符串s的位數for(i=1;i=0,25,voidjia(inta)/整數數組a與其反序數b進行n進制加法運算for(inti=1;i0)a0+;/修正新的a的位數(a+b最多只能的一個進位)intmain()init(a);if(check(a)cout0endl;return0;ans=0;/步數初始化為0while(ans+=30)jia(a);if(check(a)coutansendl;return0;coutImpossible;/輸出無解信息return0;,26,【上機練習】,1、求N!的值【問題描述】用高精度方法,求N!的精確值(N以一般整數輸入)。【輸入樣例】ni.in10【輸出樣例】ni.out36288002、求A/B高精度值【問題描述】計算A/B的精確值,設A,B是以一般整數輸入,計算結果精確小數后20位。【輸入樣例】ab.in43【輸出樣例】ab.out4/3=1.33333333333333333333【輸入樣例】ab.in65【輸出樣例】ab.out6/5=1.2,27,3、求n累加和【問題描述】用高精度方法,求s=1+2+3+n的精確值(n以一般整數輸入)。【輸入樣例】ja.in10【輸出樣例】ja.out554、階乘和(sum.pas)【問題描述】已知正整數N(N=100),設S=1!+2!+3!+.N!。其中!表示階乘,即N!=1*2*3*(N-1)*N,如:3!=1*2*3=6。請編程實現:輸入正整數N,輸出計算結果S的值。【輸入樣例】sum.in4【輸出樣例】sum.out335、高精度求積(MULTIPLY.PAS)【問題描述】輸入兩個高精度正整數M和N(M和N均小于100位)。【問題求解】求這兩個高精度數的積。【輸入樣例】MULTIPLY.IN363【輸出樣例】MULTIPLY.OUT108,28,6、天使的起誓(YUBIKILI.pas)【問題描述】TENSHI非常幸運的被選為掌管智慧之匙的天使。在正式任職之前,她必須和其他新當選的天使一樣,要宣誓。宣誓儀式是每位天使各自表述自己的使命,她們的發言稿被放在N個呈圓形排列的寶盒中。這些寶盒按順時針方向被編上號碼、N-1、N。一開始天使們站在編號為N的寶盒旁。她們各自手上都有一個數字,代表她們自己的發言稿所在的盒子是從號盒子開始按順時針方向的第幾個。例如:有個盒子,那么如果TENSHI手上的數字為,那么她的發言稿所在盒子就是第個。現在天使們開始按照自己手上的數字來找發言稿,先找到的就可以先發言。TENSHI一下子就找到了,于是她最先上臺宣誓:“我將帶領大家開啟NOI之門”TENSHI宣誓結束以后,陸續有天使上臺宣誓。可是有一位天使找了好久都找不到她的發言稿,原來她手上的數字M非常大,她轉了好久都找不到她想找的寶盒。【問題求解】請幫助這位天使找到她想找的寶盒的編號。【輸入格式】從文件YUBIKILI.IN的第一、二行分別讀入正整數N和M,其中N、M滿足2N108,2M101000【輸出格式】把所求寶盒的編號輸出到文件YUBIKILI.OUT,文件只有一行(包括換行符)。,樣例一YUBIKILI.IN79,YUBIKILI.OUT2,樣例二YUBIKILI.IN11108,YUBIKILI.OUT9,29,7、Hanoi雙塔問題(Noip2007)【問題描述】給定A、B、C三根足夠長的細柱,在A柱上放有2n個中間有孔的圓盤,共有n個不同的尺寸,每個尺寸都有兩個相同的圓盤,注意這兩個圓盤是不加區分的(下圖為n=3的情形)。現要將這些圓盤移到C柱上,在移動過程中可放在B柱上暫存。要求:(1)每次只能移動一個圓盤;(2)A、B、C三根細柱上的圓盤都要保持上小下大的順序;任務:設An為2n個圓盤完成上述任務所需的最少移動次數
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025初三升高一數學暑假銜接講義25講含答案(必修一內容)2.2 基本不等式 -(必修第一冊)含答案
- 政治●廣東卷丨2022年廣東省普通高中學業水平選擇性考試政治試卷及答案
- 考研復習-風景園林基礎考研試題附參考答案詳解【培優a卷】
- 考研復習-風景園林基礎考研試題(易錯題)附答案詳解
- 風景園林基礎考研資料試題及參考答案詳解【滿分必刷】
- 《風景園林招投標與概預算》試題A帶答案詳解(預熱題)
- 2025-2026年高校教師資格證之《高等教育法規》通關題庫附答案詳解ab卷
- 2023國家能源投資集團有限責任公司第一批社會招聘筆試備考題庫含答案詳解(基礎題)
- 2025福建晉園發展集團有限責任公司權屬子公司招聘7人筆試備考題庫完整答案詳解
- 2025年黑龍江省五常市輔警招聘考試試題題庫含答案詳解(b卷)
- 《教師禮儀》課程教學大綱
- 平行線新初一在線英語暑期分班測(劍橋think體系)測試題
- 卡通風青春畢業季PPT模板課件
- 心電監護課件精品PPT課件
- 具有車架結構車輛的怠速震動分析外文文獻翻譯、中英文翻譯
- 上公司人力資源管理制度非常全面
- 小學數學命題研究
- summer-vibe-的中英歌詞
- 天津友發鋼管集團有限公司鋼管
- 水工建筑物水閘課程設計
- 七年級英語知識競賽
評論
0/150
提交評論