北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程

程序設(shè)計(jì)實(shí)習(xí)

第四講函數(shù)指針和高精度計(jì)算主講教師：田永鴻2021年3月3日上機(jī)遇到的問(wèn)題程序風(fēng)格請(qǐng)參見第一講?程序風(fēng)格?局部常見問(wèn)題：

1、多個(gè)語(yǔ)句寫在1行〔特別是for語(yǔ)句〕

2、沒(méi)有遵循命名標(biāo)準(zhǔn)對(duì)特定問(wèn)題的分析不清晰程序設(shè)計(jì)問(wèn)題數(shù)組的分配……可以選用VisualStudio.Net2003/2005或其他編譯環(huán)境內(nèi)容提要函數(shù)調(diào)用的內(nèi)存變化示意圖函數(shù)指針程序閱讀練習(xí)程序設(shè)計(jì)練習(xí)作業(yè)C++組件C程序是由函數(shù)構(gòu)成的。程序員編寫新的函數(shù)并調(diào)用C語(yǔ)言的函數(shù)庫(kù)中的有關(guān)函數(shù)以完成具有特定功能的程序。C++程序是由類構(gòu)成的。程序員編寫新的類并使用C++標(biāo)準(zhǔn)類庫(kù)中的類來(lái)完成編程。C++標(biāo)準(zhǔn)類庫(kù)中也提供豐富的函數(shù)〔數(shù)學(xué)計(jì)算、字符串操作、字符操作、輸入輸出、錯(cuò)誤檢查等〕供程序員使用。函數(shù)在C和C++程序中都是一個(gè)非常重要的內(nèi)容。數(shù)學(xué)函數(shù)庫(kù)例：計(jì)算并輸出900.0的平方根，用如下語(yǔ)句：cout<<sqrt(900.0);說(shuō)明：sqrt()是庫(kù)函數(shù)，包含在頭文件math.h中；在調(diào)用sqrt()之前必須用#include<math.h>語(yǔ)句數(shù)學(xué)函數(shù)庫(kù)在math.h中還有以下函數(shù)：ceil(x)向上取整floor(x)向下取整exp(x)log(x)底數(shù)為elog10(x)pow(x,y)x的y次方sqrt(x)sin(x)cos(x)tan(x)fabs(x) //求浮點(diǎn)數(shù)的絕對(duì)值fmod(x,y) //雙精度數(shù)取模，即x/y的余數(shù)庫(kù)函數(shù)及頭文件C語(yǔ)言中的一些庫(kù)函數(shù)<assert.h>//設(shè)定插入點(diǎn)<ctype.h>//字符處理<float.h>//浮點(diǎn)數(shù)處理<limits.h>//定義各種數(shù)據(jù)類型最值常量<math.h>//定義數(shù)學(xué)函數(shù)<stdio.h>//定義輸入／輸出函數(shù)<stdlib.h>//定義雜項(xiàng)函數(shù)及內(nèi)存分配函數(shù)<string.h>//字符串處理<time.h>//定義關(guān)于時(shí)間的函數(shù)庫(kù)函數(shù)及頭文件C語(yǔ)言中的一些庫(kù)函數(shù)<iostream.h>或<iostream>//數(shù)據(jù)流輸入／輸出<iomapip.h>//參數(shù)化輸入／輸出<fstream.h>//文件輸入／輸出<errno.h>//定義錯(cuò)誤碼<wchar.h>//寬字符處理及輸入／輸出<wctype.h>//寬字符分類每個(gè)頭文件中包含一組函數(shù)，使用哪個(gè)頭文件中的函數(shù)就必須在程序中用#include語(yǔ)句包含哪個(gè)頭文件。函數(shù)的定義函數(shù)的定義語(yǔ)句如下：返回值類型函數(shù)名〔[參數(shù)1類型參數(shù)名1,參數(shù)2類型參數(shù)名2,…]〕{ 語(yǔ)句1；//語(yǔ)句可能與參數(shù)有關(guān) 語(yǔ)句2；//語(yǔ)句可能與參數(shù)有關(guān) …… return返回值；//如果返回值類型為void，那么不用返 //回語(yǔ)句}函數(shù)定義的例子下面是一個(gè)函數(shù)定義的例子：

intadd(intx,inty){ returnx+y;}函數(shù)說(shuō)明和函數(shù)體intmultiple(intx,inty);//函數(shù)說(shuō)明voidmain(){ inta=0,b=0; scanf("%d%d",&a,&b); printf("%d\n",multiple(a,b));//函數(shù)調(diào)用}intmultiple(intx,inty){ //函數(shù)體 returnx*y;}函數(shù)的調(diào)用 intadd(intx,inty){ returnx+y; } intminus(intx,inty){ returnx-y; }函數(shù)的調(diào)用voidmain(){ intn1,n2; scanf(“%d%d〞,&n1,&n2); n1=add(n1,n2); n2=minus(n1,n2); if(n1>0&&n2>0) printf(“%d\n〞,add(n1,n2)); elseprintf(“%d\n〞,minus(n1,n2)); }函數(shù)調(diào)用的過(guò)程 intmax(intx,inty){ if(x>=y)returnx; elsereturny;} voidmain(){ intx=0,y=0,z=0; x=20; y=45; intz=max(x,y); …… }函數(shù)調(diào)用的過(guò)程函數(shù)調(diào)用的過(guò)程函數(shù)調(diào)用的過(guò)程函數(shù)調(diào)用的過(guò)程函數(shù)調(diào)用的過(guò)程函數(shù)調(diào)用的過(guò)程參數(shù)傳遞：傳值和傳地址A程序可以向B程序傳遞某些數(shù)值，也可以向B程序傳遞內(nèi)存地址。參數(shù)傳遞：傳值intmax(intx,inty){ if(x>=y)returnx; elsereturny;}voidmain(){ intx=0,y=0,z=0; x=20; y=45; intz=max(x,y); ……}參數(shù)傳遞：傳地址〔指針?lè)绞健?intswap(int*x,int*y){ inttmp=0; tmp=*x; *x=*y; *y=tmp;}參數(shù)傳遞：傳地址〔引用方式〕 voidmain(){ inta=0,b=0; a=20; b=45; if(a<b)swap(&a,&b); …… }程序運(yùn)行過(guò)程程序運(yùn)行過(guò)程程序運(yùn)行過(guò)程程序運(yùn)行過(guò)程程序運(yùn)行過(guò)程程序運(yùn)行過(guò)程程序運(yùn)行過(guò)程函數(shù)的返回值函數(shù)執(zhí)行完以后可以向調(diào)用它的程序返回一個(gè)值，說(shuō)明函數(shù)運(yùn)行的狀況。很多函數(shù)的功能就是對(duì)參數(shù)進(jìn)行某種運(yùn)算，之后通過(guò)函數(shù)返回值給出運(yùn)算結(jié)果。函數(shù)的返回值可以有不同的類型，返回值類型在函數(shù)定義時(shí)說(shuō)明。函數(shù)的返回值intmin(intx,inty);//返回值類型為int，有兩個(gè)整型參數(shù)，函數(shù)名為mindoublecalculate(inta,doubleb); //返回值類型為double，有一個(gè)整型參數(shù)，一個(gè)double型參數(shù)，函數(shù)名為calculatecharjudge(void);//返回值類型為char，沒(méi)有參數(shù)，函數(shù)名為judgevoiddoit(inttimes);//返回值類型為void，表示不返回任何值，有一個(gè)整型參數(shù)，函數(shù)名為doit函數(shù)指針的定義在C語(yǔ)言中，函數(shù)本身不是變量，但可以定義指向函數(shù)的指針，這種指針可以被賦值、存放于數(shù)組之中，傳遞給函數(shù)及作為函數(shù)的返回值返回值類型〔*函數(shù)指針名〕〔參數(shù)表〕；例1：intsquare(int);int(*f)(int)=square;例2： voidf1(int); voidf2(int); voidf3(int);void(*f[3])(int)={f1,f2,f3};函數(shù)指針的使用#include<stdio.h>intsquare(intx){printf("0%d\n",x);return0;};int(*f)(int)=square;voidf1(intx){printf("1%d\n",x);};voidf2(intx){printf("2%d\n",x);};voidf3(intx){printf("3%d\n",x);};void(*fp[3])(int)={f1,f2,f3};voidmain(){(*f)(0);(*fp[0])(1);(*fp[1])(2);(*fp[2])(3);}函數(shù)指針作為參數(shù)傳遞intsum(inta,intb,int(*term)(int)){if(a>b)return0;return(*term)(a)+sum(a+1,b,(*term));}intterm(inta){returna;}voidmain(){cout<<sum(69,90,term)<<endl; ints=0; for(inti=69;i<=90;i++)s+=i; cout<<s<<endl;}程序閱讀理解intsum(inta,intb,int(*term)(int)){if(a>b)return0;return(*term)(a)+sum(a+1,b,(*term));}intcube_term(inta){returna*a*a;}voidmain(){cout<<sum(1,3,cube_term)<<endl;cout<<1*1*1+2*2*2+3*3*3<<endl;}程序閱讀理解#include<iostream.h>doublesum(inta,intb,double(*term)(int)){if(a>b)return0;return(*term)(a)+sum(a+1,b,(*term));}doublepi_term(inta){return(1.0/(4*(a-1)+1))*(1.0/(4*(a-1)+3));}voidmain(){ cout<<sum(2,5,pi_term)<<endl; cout<<1.0/(5*7)+1.0/(9*11)+1.0/(13*15)+1.0/(17*19)<<endl;}函數(shù)模板不同數(shù)據(jù)類型用不同程序邏輯進(jìn)行類似的操作。如果每種數(shù)據(jù)類型的程序邏輯和操作相同，那么用函數(shù)模板〔functiontemplate〕完成這項(xiàng)工作更加簡(jiǎn)潔和方便。程序員編寫函數(shù)模板定義，編譯器根據(jù)函數(shù)調(diào)用中的參數(shù)類型自動(dòng)生成不同的模板函數(shù)〔templatefunction〕來(lái)處理不同類型的調(diào)用。一個(gè)函數(shù)模板定義了一系列解決方案。template<classT>Tsum(inta,intb,T(*term)(int)){if(a>b)return0;return(*term)(a)+sum(a+1,b,(*term));}intterm1(inta){returna;}intterm2(inta){returna*a*a;}doubleterm3(inta){return(1.0/(4*(a-1)+1))*(1.0/(4*(a-1)+3));}voidmain(){ cout<<sum(1,3,term1)<<endl; cout<<sum(1,3,term2)<<endl; cout<<sum(1,3,term3)<<endl;}C語(yǔ)言庫(kù)函數(shù)中的幾個(gè)帶函數(shù)參數(shù)的函數(shù)#include<stdlib.h>qsort//快速排序Bsearch//數(shù)組的二分法搜索#include<search.h>_lfind //線性搜索_lsearch//線性搜索_lfind與_lsearch不同點(diǎn)在于，當(dāng)找不到關(guān)鍵數(shù)據(jù)時(shí)_lfind僅會(huì)返回NULL，_lsearch會(huì)主動(dòng)把該筆數(shù)據(jù)參加數(shù)組尾端。qsortvoidqsort(void*base,size_tnum,size_twidth,

int(__cdecl*compare)(constvoid*elem1,constvoid*elem2));__cdecl和__stdcall都是函數(shù)調(diào)用標(biāo)準(zhǔn)(還有一個(gè)__fastcall),規(guī)定了參數(shù)出入棧的順序和方法__cdecl是C/C++和MFC程序默認(rèn)使用的調(diào)用約定，也可以在函數(shù)聲明時(shí)加上__cdecl關(guān)鍵字來(lái)手工指定。采用__cdecl約定時(shí)，函數(shù)參數(shù)按照從右到左的順序入棧，并且由調(diào)用函數(shù)者把參數(shù)彈出棧以清理堆棧。因此，實(shí)現(xiàn)可變參數(shù)的函數(shù)只能使用該調(diào)用約定。由于每一個(gè)使用__cdecl約定的函數(shù)都要包含清理堆棧的代碼，所以產(chǎn)生的可執(zhí)行文件大小會(huì)比較大。__cdecl可以寫成_cdecl。qsortTheqsortfunctionimplementsaquick-sortalgorithmtosortanarrayofnumelements,eachofwidthbytes.Theargumentbaseisapointertothebaseofthearraytobesorted.qsortoverwritesthisarraywiththesortedelements.Theargumentcompareisapointertoauser-suppliedroutinethatcomparestwoarrayelementsandreturnsavaluespecifyingtheirrelationship.qsortcallsthecompareroutineoneormoretimesduringthesort,passingpointerstotwoarrayelementsoneachcall:qsortcompare(

(void

*)

elem1,

(void

*)

elem2

);Theroutinemustcomparetheelements,thenreturnoneofthefollowingvalues:ReturnValueDescription<0elem1lessthanelem20elem1equivalenttoelem2>0elem1greaterthanelem2習(xí)題1928題魯賓遜先生有一只寵物猴，名叫多多。這天，他們兩個(gè)正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條：“歡送免費(fèi)品嘗我種的花生！——熊字〞。魯賓遜先生和多多都很開心，因?yàn)榛ㄉ撬麄兊淖類邸Ｔ诟媸九票澈?，路邊真的有一塊花生田，花生植株整齊地排列成矩形網(wǎng)格〔如圖1〕。有經(jīng)驗(yàn)的多多一眼就能看出，每棵花生植株下的花生有多少。為了訓(xùn)練多多的算術(shù)，魯賓遜先生說(shuō)：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過(guò)你一定要在我限定的時(shí)間內(nèi)回到路邊。〞習(xí)題1928題我們假定多多在每個(gè)單位時(shí)間內(nèi)，可以做以下四件事情中的一件：從路邊跳到最靠近路邊〔即第一行〕的某棵花生植株；從一棵植株跳到前后左右與之相鄰的另一棵植株；采摘一棵植株下的花生；從最靠近路邊〔即第一行〕的某棵花生植株跳回路邊?，F(xiàn)在給定一塊花生田的大小和花生的分布，請(qǐng)問(wèn)在限定時(shí)間內(nèi)，多多最多可以采到多少個(gè)花生？注意可能只有局部植株下面長(zhǎng)有花生，假設(shè)這些植株下的花生個(gè)數(shù)各不相同。例如在圖2中的花生田里，只有位于(2,5),(3,7),(4,2),(5,4)的植株下長(zhǎng)有花生，個(gè)數(shù)分別為13,7,15,9。沿著圖示的路線，多多在21個(gè)單位時(shí)間內(nèi)，最多可以采到37個(gè)花生?！据斎搿?/p>

輸入第一行包括三個(gè)整數(shù)，M,N和K，用空格隔開；表示花生田的大小為M*N〔1<=M,N<=20〕，多多采花生的限定時(shí)間為K〔0<=K<=1000〕個(gè)單位時(shí)間。接下來(lái)的M行，每行包括N個(gè)非負(fù)整數(shù)，也用空格隔開；第i+1行的第j個(gè)整數(shù)Pij〔0<=Pij<=500〕表示花生田里植株(i,j)下花生的數(shù)目，0表示該植株下沒(méi)有花生。

【輸出】

輸出包括一行，這一行只包含一個(gè)整數(shù)，即在限定時(shí)間內(nèi)，多多最多可以采到花生的個(gè)數(shù)?！緲永斎?】

672100000000000130000000070150000000090000000000

【樣例輸出1】37【樣例輸入2】672000000000000130000000070150000000090000000000

【樣例輸出2】28解題報(bào)告解法一：每次在二維數(shù)組中找到當(dāng)前最大值的位置〔如果當(dāng)前最大值為零那么直接回去〕，判斷如果走過(guò)去摘了花生再回去，時(shí)間是否來(lái)得及。如果來(lái)得及，把當(dāng)前位置的花生數(shù)置為零，移動(dòng)到最大值的位置，累加已用時(shí)間；如果來(lái)不及就從當(dāng)前位置直接回去。解法二：先將二維數(shù)組按花生數(shù)排序，再判斷并移動(dòng)。解法2定義一個(gè)結(jié)構(gòu)數(shù)組存放花生植株信息structSNode{intr,c;

intnPeanuts;};

SNodeField[2600];自定義一個(gè)比較函數(shù)intCompareNode(constvoid*pElement1,constvoid*pElement2){SNode*pNode1,*pNode2;pNode1=(SNode*)pElement1;pNode2=(SNode*)pElement2;returnpNode2->nPeanuts-pNode1->nPeanuts;}解法2主要流程1、讀入輸入記錄的個(gè)數(shù)2、對(duì)每個(gè)輸入記錄，分別讀入各參數(shù)，并初始化Field數(shù)組3、用qsort將Field數(shù)組排序4、開始采摘初始化耗時(shí)FOR循環(huán)：從大到小偏離所有的Field數(shù)組,直至超時(shí)或超F(xiàn)ield數(shù)組中記錄個(gè)數(shù)計(jì)算所有摘取的花生數(shù)計(jì)算總耗時(shí)，加上采摘并走到下一個(gè)節(jié)點(diǎn)的時(shí)間5、輸出源程序程序設(shè)計(jì)過(guò)程提出問(wèn)題建立數(shù)學(xué)模型設(shè)計(jì)算法程序?qū)崿F(xiàn)提出問(wèn)題明確程序的條件、原始數(shù)據(jù)、輸入、處理的數(shù)據(jù)類型、輸出的形式和精度建立數(shù)學(xué)模型將原始問(wèn)題簡(jiǎn)化、抽象、轉(zhuǎn)換成適合計(jì)算機(jī)處理的數(shù)據(jù)結(jié)構(gòu)、公式選擇適宜的數(shù)據(jù)類型以及存儲(chǔ)調(diào)用方式〔需要注意的：數(shù)據(jù)的類型、數(shù)據(jù)的精度、數(shù)據(jù)的生命周期〕建立數(shù)據(jù)之間的關(guān)系即公式設(shè)計(jì)算法使用計(jì)算機(jī)可以實(shí)現(xiàn)的方法描述數(shù)據(jù)和數(shù)據(jù)之間的關(guān)系選擇適宜的程序流，使用流程圖描述程序流程序?qū)崿F(xiàn)編寫程序、調(diào)試運(yùn)行、測(cè)試驗(yàn)證、保存編譯等良好程序風(fēng)格輸入輸出聲明數(shù)據(jù)，申請(qǐng)存儲(chǔ)空間實(shí)現(xiàn)程序流高精度計(jì)算高精度計(jì)算：C/C++中int類型表示范圍：-231～231-1

unsigned類型表示范圍：0～232-1因此均不超過(guò)10位整數(shù)即使用很大數(shù)字范圍的double有時(shí)也不能滿足要求大整數(shù)的