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

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

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

1、多個語句寫在1行〔特別是for語句〕

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

intadd(intx,inty){ returnx+y;}函數(shù)說明和函數(shù)體intmultiple(intx,inty);//函數(shù)說明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)用的過程 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)用的過程函數(shù)調(diào)用的過程函數(shù)調(diào)用的過程函數(shù)調(diào)用的過程函數(shù)調(diào)用的過程函數(shù)調(diào)用的過程參數(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ù)傳遞：傳地址〔指針方式〕 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); …… }程序運行過程程序運行過程程序運行過程程序運行過程程序運行過程程序運行過程程序運行過程函數(shù)的返回值函數(shù)執(zhí)行完以后可以向調(diào)用它的程序返回一個值，說明函數(shù)運行的狀況。很多函數(shù)的功能就是對參數(shù)進(jìn)行某種運算，之后通過函數(shù)返回值給出運算結(jié)果。函數(shù)的返回值可以有不同的類型，返回值類型在函數(shù)定義時說明。函數(shù)的返回值intmin(intx,inty);//返回值類型為int，有兩個整型參數(shù)，函數(shù)名為mindoublecalculate(inta,doubleb); //返回值類型為double，有一個整型參數(shù)，一個double型參數(shù)，函數(shù)名為calculatecharjudge(void);//返回值類型為char，沒有參數(shù)，函數(shù)名為judgevoiddoit(inttimes);//返回值類型為void，表示不返回任何值，有一個整型參數(shù)，函數(shù)名為doit函數(shù)指針的定義在C語言中，函數(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〕完成這項工作更加簡潔和方便。程序員編寫函數(shù)模板定義，編譯器根據(jù)函數(shù)調(diào)用中的參數(shù)類型自動生成不同的模板函數(shù)〔templatefunction〕來處理不同類型的調(diào)用。一個函數(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語言庫函數(shù)中的幾個帶函數(shù)參數(shù)的函數(shù)#include<stdlib.h>qsort//快速排序Bsearch//數(shù)組的二分法搜索#include<search.h>_lfind //線性搜索_lsearch//線性搜索_lfind與_lsearch不同點在于，當(dāng)找不到關(guān)鍵數(shù)據(jù)時_lfind僅會返回NULL，_lsearch會主動把該筆數(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)(還有一個__fastcall),規(guī)定了參數(shù)出入棧的順序和方法__cdecl是C/C++和MFC程序默認(rèn)使用的調(diào)用約定，也可以在函數(shù)聲明時加上__cdecl關(guān)鍵字來手工指定。采用__cdecl約定時，函數(shù)參數(shù)按照從右到左的順序入棧，并且由調(diào)用函數(shù)者把參數(shù)彈出棧以清理堆棧。因此，實現(xiàn)可變參數(shù)的函數(shù)只能使用該調(diào)用約定。由于每一個使用__cdecl約定的函數(shù)都要包含清理堆棧的代碼，所以產(chǎn)生的可執(zhí)行文件大小會比較大。__cdecl可以寫成_cdecl。qsortTheqsortfunctionimplementsaquick-sortalgorithmtosortanarrayofnumelements,eachofwidthbytes.Theargumentbaseisapointertothebaseofthearraytobesorted.qsortoverwritesthisarraywiththesortedelements.Theargumentcompareisapointertoauser-suppliedroutinethatcomparestwoarrayelementsandreturnsavaluespecifyingtheirrelationship.qsortcallsthecompareroutineoneormoretimesduringthesort,passingpointerstotwoarrayelementsoneachcall:qsortcompare(

(void

*)

elem1,

(void

*)

elem2

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

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

【輸出】

輸出包括一行，這一行只包含一個整數(shù)，即在限定時間內(nèi)，多多最多可以采到花生的個數(shù)。【樣例輸入1】

672100000000000130000000070150000000090000000000

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

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

intnPeanuts;};

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

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