第二講簡單程序設(shè)計(jì)練習(xí)

1、程序設(shè)計(jì)實(shí)習(xí)課程 (C+ Programming Practice)程序設(shè)計(jì)實(shí)習(xí)第二講 簡單程序設(shè)計(jì)練習(xí)北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程2課堂調(diào)查o 是否學(xué)過C語言，或有過C語言編程經(jīng)驗(yàn)?o 有過C+編程經(jīng)驗(yàn)？o 是否熟練使用VC+編程環(huán)境？北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程3上次課內(nèi)容回顧o 位運(yùn)算o 函數(shù)指針o 指針和動(dòng)態(tài)內(nèi)存分配o 命令行參數(shù)o C語言標(biāo)準(zhǔn)庫函數(shù)o 程序風(fēng)格建議o 課堂測驗(yàn)北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程4內(nèi)容提要o C語言的基礎(chǔ)知識(shí)與程序架構(gòu)介紹o C語言的標(biāo)準(zhǔn)輸入輸出語句n 上節(jié)課的測驗(yàn)題講解o 程序閱讀練習(xí)o 程序設(shè)計(jì)練習(xí)o 作業(yè)o 課程練習(xí)與習(xí)題出自:PKU JudgeOnline htt

2、p:/ 一般計(jì)算機(jī)中用16位或32位來表示整數(shù),位數(shù)越多,能表示數(shù)的范圍就越大。o 整數(shù)有正負(fù)之分,為此,我們可以用一個(gè)二進(jìn)位作為符號(hào)位,一般總是最高位,當(dāng)符號(hào)位為0是表示正數(shù),符號(hào)位為1時(shí)表示負(fù)數(shù)。例如,當(dāng)我們用16位來表示一個(gè)整數(shù)時(shí),有0000 0000 0010 1011=+431000 0000 0010 1011=-43o 上述表示法,稱為整數(shù)的表示法。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程6整數(shù)也可采用表示法,對(duì)于負(fù)整數(shù)來說,符號(hào)位作為1,但絕對(duì)值部分正好與原碼相反（即0變?yōu)?,1變?yōu)?）。因此：(-43)原原=1000 0000 0010 1011(-43)反反=1111 1111 1101

3、0100而實(shí)際上,整數(shù)在機(jī)器內(nèi)大多用表示,對(duì)負(fù)整數(shù)而言,符號(hào)位仍為1,但絕對(duì)值部分卻是反碼的最低位加1得到的結(jié)果,因此(-43)補(bǔ)補(bǔ)=1111 1111 1101 0101注意,對(duì)正整數(shù)而言,其原碼、反碼、補(bǔ)碼均相同。數(shù)在計(jì)算機(jī)內(nèi)的表示北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程7 任何程序設(shè)計(jì)語言，都是由語言語言規(guī)范規(guī)范和一系列標(biāo)準(zhǔn)開發(fā)庫標(biāo)準(zhǔn)開發(fā)庫組成的。如標(biāo)準(zhǔn)C，除了語言規(guī)范外，還有很多函數(shù)庫；MS Visual C+更是提供了龐大的APIs和MFC。 學(xué)習(xí)任何程序設(shè)計(jì)語言，都是要從這兩方面著手，尤其是要能夠熟練地使用后者。程序設(shè)計(jì)語言程序設(shè)計(jì)語言開發(fā)庫北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程8p 程序結(jié)構(gòu)p 基本元素：標(biāo)識(shí)

4、符和關(guān)鍵字p 變量、常量和數(shù)據(jù)類型p 運(yùn)算符和表達(dá)式p 語句及控制流p C語言標(biāo)準(zhǔn)庫函數(shù)語言規(guī)范語言規(guī)范開發(fā)庫開發(fā)庫C程序設(shè)計(jì)語言程序設(shè)計(jì)語言北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程9o 一個(gè)C程序是由一個(gè)固定名稱為main的主函數(shù)和若干個(gè)自定義函數(shù)（可缺省）組成。編譯預(yù)處理（宏、頭文件）自定義函數(shù)聲明int main( )說明部分 /*變量定義等*/執(zhí)行部分 /*輸入/輸出/計(jì)算*/ 自定義函數(shù)C程序基本框架程序基本框架北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程10/*求圓的面積*/#define PI 3.14159 /*預(yù)編譯：宏定義*/#include /*預(yù)編譯：文件包含*/#include float getAre

5、a(float r); /*自定義函數(shù)：求面積函數(shù)*/*主函數(shù)*/int main(int argc, char* argv) float s1,s2; /*定義變量*/ float r1,r2; /*計(jì)算第1個(gè)圓的面積*/ printf(“請(qǐng)輸入第一個(gè)圓的半徑：”); /*調(diào)用stdio.h中的函數(shù)printf()，將相關(guān)內(nèi)容輸出到屏幕中去*/ scanf(%f, &r1); /*調(diào)用stdio.h中的函數(shù)scanf()，從鍵盤中輸入半徑r1的值*/ s1 = 3.14159f * r1 * r1; /*求面積*/ printf(“n第一個(gè)半徑為%f的圓的面積為：%fn”, r1,s

6、1); /*調(diào)用函數(shù)printf()，將計(jì)算的面積輸出到平面中去*/ /*計(jì)算第2個(gè)圓的面積*/ r2 = 104.6f; /*半徑為104.6*/ s2 = getArea(r2); /*調(diào)用自定義函數(shù)求圓的面積*/ printf(n第二個(gè)半徑為%f的圓的面積為：%fn, r2,s2); /*調(diào)用函數(shù)printf()，將計(jì)算的面積輸出到平面中去*/*自定義函數(shù)：求半徑為r的圓的面積*/float getArea(float r) float s; s = (float)(PI * pow(r, 2); /*利用所定義的宏P(guān)I替換3.14159，調(diào)用math.h中的求冪函數(shù)pow()*/ re

7、turn s;C程序基本框架程序基本框架北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程11n一個(gè)C程序是由一個(gè)固定名稱為main的主函數(shù)和若干個(gè)其他函數(shù)（可沒有）組成。n一個(gè)C程序必須有一個(gè)、也只能有一個(gè)主函數(shù)。n程序執(zhí)行時(shí)總是從主函數(shù)開始，在主函數(shù)內(nèi)結(jié)束。n主函數(shù)可以調(diào)用其他各種函數(shù)（包括標(biāo)準(zhǔn)庫函數(shù)和用戶自己編寫的函數(shù)），但其他函數(shù)不能調(diào)用主函數(shù)。其他函數(shù)相互之間遵循一定的規(guī)則是可以相互調(diào)用的。C程序基本框架程序基本框架主函數(shù)主函數(shù)北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程12其他函數(shù)其他函數(shù)o標(biāo)準(zhǔn)庫函數(shù)：隨C語言環(huán)境語言環(huán)境一起提供的各種標(biāo)準(zhǔn)的通用功能函數(shù)，只能調(diào)用(先文件包含先文件包含) 。例： s = (float)(PI

8、* pow(r, 2); pow(x,y) 求xy （math.h，數(shù)學(xué)函數(shù)）scanf(%f, &r1);scanf(“%f”, ) 從鍵盤中輸入數(shù)據(jù)（stdio.h，輸入輸出函數(shù)）printf(n第一個(gè)半徑為%f的圓的面積為：%fn, r1,s1);printf(“%f”, ) 往屏幕中輸出數(shù)據(jù)（stdio.h，輸入輸出函數(shù)）o自編（定義）函數(shù)：必須先定義（聲明），后調(diào)用必須先定義（聲明），后調(diào)用例： s2 = getArea(r2); C程序基本框架程序基本框架函數(shù)函數(shù)北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程13C程序基本框架程序基本框架函數(shù)函數(shù)/主函數(shù)主函數(shù)主函數(shù)main()標(biāo)準(zhǔn)庫函數(shù)自定義函

9、數(shù)自定義函數(shù)自定義函數(shù)函數(shù)的調(diào)用函數(shù)的調(diào)用北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程14n變量：變量：存放數(shù)據(jù)的容器，有不同的數(shù)據(jù)類型。n語句：語句：一個(gè)由分號(hào)（;）結(jié)尾的單一命令是一條語句（Statement），一條語句可以完成一條或若干條指令功能。如：nfloat s, r; / 變量定義語句nr = 10; / 變量賦值語句ns = 3.1416*r*r; / 執(zhí)行乘法運(yùn)算并賦值的語句n代碼段：代碼段：用大括號(hào)（ ）圍起來的多條語句構(gòu)成一個(gè)代碼段（Code block）；如：nint i;nfor (i=0; i=1; i+) nnC程序基本框架程序基本框架變量變量/語句語句/代碼段代碼段北京大學(xué)程序設(shè)計(jì)

10、實(shí)習(xí)課程15形式：形式： PI 符號(hào)常量（宏名，最好用大寫，以區(qū)別一般變量）3.14159 宏體（可以是一個(gè)表達(dá)式）o作用：用簡單符號(hào)代表宏體部份內(nèi)容（編譯時(shí)會(huì)先自動(dòng)替換），可用作常量定義或其他作用o意義：直觀/多次使用/便于修改o注意： #define 可出現(xiàn)在程序的任一位置（作用范圍：作用范圍：由此行到程序末尾），宏定義不是C語句，不必在行未加分號(hào)，否則會(huì)連分號(hào)一起置換。C程序基本框架程序基本框架預(yù)編譯處理預(yù)編譯處理北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程16編譯預(yù)處理編譯預(yù)處理文件包含文件包含形式：形式： stdio.h “頭文件”，標(biāo)準(zhǔn)前導(dǎo)文件myhead.h “頭文件”，自定義前導(dǎo)文件oC語言是一種

11、“裝配式”語言，許多常規(guī)的工作如輸入、輸出、數(shù)學(xué)函數(shù)等，往往事先由人做成各種“程序模塊”(.lib)，并將其定義存放在各種所謂“頭文件”(.h)中。o文件包含的作用，就是根據(jù)需要把相應(yīng)的某個(gè)“頭文件”定義所涉及的“程序模塊”在編譯時(shí)先整體嵌入所編的程序中。o用戶也可以將自己設(shè)計(jì)的程序模塊等做成“程序模塊”及“頭文件”，供其他程序“包含”（調(diào)用）。C程序基本框架程序基本框架預(yù)編譯處理預(yù)編譯處理北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程17n注釋注釋：為了增加程序的可讀性而附加的說明性文字，它們?cè)诰幾g時(shí)會(huì)被忽略。n/ 單行注釋，簡單的解釋語句含義. 注釋到行末n/* 多行注釋，用來說明更多的內(nèi)容，包括算法等.nn*

12、/C程序基本框架程序基本框架注釋注釋北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程18C語言是一種函數(shù)式語言，其程序基本組成是函數(shù)。每個(gè)C程序必須有一個(gè)、也只能有一個(gè)主函數(shù)main()。不管主函數(shù)在程序中的位置如何，程序執(zhí)行總是從主函數(shù)開始，在主函數(shù)內(nèi)結(jié)束。#include 語句 - 頭文件包含#define 語句 - 宏定義每個(gè)語句必須用分號(hào)“；”結(jié)束（注意是“每個(gè)語句”而不“每行語句”）。語句可以用大括號(hào)組成語句段。函數(shù)可以調(diào)用其它函數(shù) 結(jié)構(gòu)化編程/分而治之C程序基本框架程序基本框架 - 總結(jié)總結(jié)北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程19三種基本算法結(jié)構(gòu)o 順序結(jié)構(gòu)o 選擇結(jié)構(gòu)（分支結(jié)構(gòu)）o 循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)）n 當(dāng)型循環(huán)

13、（While型循環(huán)）n 直到型循環(huán)（Do-While型循環(huán)）北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程20三種基本算法結(jié)構(gòu)的共同特點(diǎn)o 只有一個(gè)入口o 只有一個(gè)出口o 結(jié)構(gòu)內(nèi)每一部分都有機(jī)會(huì)被執(zhí)行到o 結(jié)構(gòu)內(nèi)不存在“死循環(huán)”AabBABa北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程21結(jié)構(gòu)化程序設(shè)計(jì)方法o 結(jié)構(gòu)化算法n 由基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)o 結(jié)構(gòu)化程序設(shè)計(jì)方法n 自頂向下n 逐步細(xì)化n 模塊化設(shè)計(jì)n 結(jié)構(gòu)化編碼北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程22C語言的輸入輸出語句o #include n scanf( ) 將輸入讀入變量 scanf(“格式控制串”, 變量地址1 , 變量地址2, )n printf( ) 將變量內(nèi)容輸出 pr

14、intf(“格式控制串”, 待輸出項(xiàng)1 ,待輸出項(xiàng)2, )o 兩點(diǎn)注意n 格式控制串?dāng)?shù)應(yīng)和變量地址/待輸出項(xiàng)數(shù)一致n 變量地址：變量前加&字符；指針；數(shù)組名int i, nArr200, *pInt;&i, nArr, pInt北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程23輸入輸出控制o 格式控制的完整格式：% - 0 m.n l或h 格式字符n%：表示格式說明的起始符號(hào)，不可缺少。n-：有-表示左對(duì)齊輸出，如省略表示右對(duì)齊輸出n0：有0表示指定空位填0,如省略表示指定空位不填。nm.n：m指域?qū)挘磳?duì)應(yīng)的輸出項(xiàng)在輸出設(shè)備上所占的字符數(shù)。n指精度。用于說明輸出的實(shí)型數(shù)的小數(shù)位數(shù)。未指定n時(shí)，隱含

15、的精度為n=6位。nl或h：l對(duì)整型指long型，對(duì)實(shí)型指double型。h用于將整型的格式字符修正為short型。 o scanf() 和 printf()的基本格式控制符有：n%d：整數(shù)n%c：字符n%s：字符串n%f：浮點(diǎn)數(shù)n%u：無符號(hào)整數(shù)n%o, %x：八進(jìn)制/十六進(jìn)制n%e：指數(shù)北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程24輸入輸出控制o scanf()中的格式控制中，還可以控制多個(gè)輸入數(shù)據(jù)之間的分隔標(biāo)記，如：scanf(“%c,%d,%f”, &c, &n, &f)。若多個(gè)輸入控制符之間沒有任何分隔標(biāo)記，則輸入數(shù)之間以換行（回車）作為分隔，如：scanf(“%c%d%f”,

16、 &c, &n, &f)。o 在printf()中的格式控制中，還可以包含其他希望輸出字符（串），如：printf(“nThis is a %d !”, n)。o 復(fù)雜格式控制：可以進(jìn)行長度控制北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程25scanf( ) 語句# include int a;long bfloat c;char d;char e20;double f;scanf(“%d %ld %f %c %s %lf”,&a,&b,&c,&d,e,&f);北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程26scanf( ) 語句o 返回值n 0 成功讀入的數(shù)據(jù)項(xiàng)個(gè)數(shù)；

17、n 0 沒有項(xiàng)被賦值；n EOF 第一個(gè)嘗試輸入的字符是EOF(結(jié)束)。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程27printf( ) 語句printf(“%d %ld %f %c %s %lf”, a, b, c, d,e, f );printf(“%5d”,a); 至少占5個(gè)字符printf(“%ld”,b);printf(“%.2f”,c); 精確到小數(shù)點(diǎn)后兩位printf(“%5c”,d);printf(“%sn”,e); 末尾回車換行printf(“%.5lf”,f); 精確到小數(shù)點(diǎn)后5位北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程28printf( ) 語句o 返回值n 成功打印的字符數(shù)；n 返回負(fù)值為出錯(cuò)。北京大學(xué)

18、程序設(shè)計(jì)實(shí)習(xí)課程29sscanf( )o sscanf() 函數(shù)從一個(gè)字符串，而不是標(biāo)準(zhǔn)輸入中讀入；例如： char str10=12:30 am; int h,m; char tag3; sscanf(str,%d:%d %s,&h,&m,tag); printf(%d:%d %s,h,m,tag);北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程30sprintf( )o sprintf() 函數(shù)向一個(gè)字符串，而不是標(biāo)準(zhǔn)輸出中輸出；例如： char str10; int h=12,m=7; char tag3=am; sprintf(str,%d:%d %sn,h,m,tag); printf(%

19、s,str);北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程31C語言的輸入輸出語句o 在vc 中安裝 MSDN，學(xué)會(huì)使用幫助，即在源文件編輯窗中輸入待查函數(shù)名，將光標(biāo)移動(dòng)至函數(shù)名上，按F1鍵；o 除了scanf 和 printf 還可以查 getchar(), putchar()北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程32C+語言的輸入輸出語句 # include cin 變量名1 變量名2; cout 變量 常量endl;o 自動(dòng)類型檢查北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程33C+語言的輸入輸出語句cin.get ()cin.getline()cout.put()cin.read()cout.write()cin.gcout()cout

20、dec oct hex setbase(i)北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程34課堂測驗(yàn)小結(jié):校門外的樹o 解法n設(shè)置數(shù)組，初始化，將地鐵區(qū)域內(nèi)位置 改變屬性，統(tǒng)計(jì)剩余數(shù)目，輸出0123i i+1 i+2L1 1 1 1 1 1 1 1標(biāo)記數(shù)組路標(biāo)0123i i+1 i+2L1 1 1 1 0 0 1 1標(biāo)記數(shù)組路標(biāo)0123i i+1 i+2L1 1 1 1 0 0 0 1標(biāo)記數(shù)組路標(biāo)北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程35校門外的樹o 有關(guān)實(shí)現(xiàn)的細(xì)節(jié)n 數(shù)組的定義p 靜態(tài)數(shù)組， 大小為10001 足夠，可能會(huì)冗余 int trees10001; bool trees10001;p 動(dòng)態(tài)數(shù)組，int *trees

21、; trees = new intL+1; delete trees;n 初始化 #include void main()int L,i,j,M;/L為區(qū)間長度為區(qū)間長度,M為區(qū)間個(gè)數(shù)，為區(qū)間個(gè)數(shù)，i,j為循環(huán)變量為循環(huán)變量bool bTrees10001;/用一個(gè)用一個(gè)bool數(shù)組模擬樹的存在情況數(shù)組模擬樹的存在情況for (i=0;i10001;i+)bTreesi = true;scanf(%d%d,&L,&M);for (i=0;iM;i+)int nBegin,nEnd;/ 用用nBegin,nEnd存儲(chǔ)區(qū)間的起止位置存儲(chǔ)區(qū)間的起止位置scanf(%d%d,&

22、nBegin,&nEnd);for (j= nBegin;j=nEnd;j+)/移除區(qū)間內(nèi)的樹移除區(qū)間內(nèi)的樹bTreesj = false;int nCount = 0; / nCount存放剩余的樹的數(shù)量存放剩余的樹的數(shù)量for (i=0;i=L;i+) / 統(tǒng)計(jì)剩余的樹的數(shù)量統(tǒng)計(jì)剩余的樹的數(shù)量if (bTreesi) nCount +;printf(%dn,nCount);解法一:采用靜態(tài)數(shù)組#include int main()int L, M;bool *bTrees;scanf(%d%d,&L,&M);bTrees=new boolL+1; /動(dòng)態(tài)定義一個(gè)數(shù)組

23、模擬樹的存在情況動(dòng)態(tài)定義一個(gè)數(shù)組模擬樹的存在情況for(int i=0;i=L;i+) /數(shù)組初始化數(shù)組初始化bTreesi=true;for(i=0;iM;i+)int start, end;scanf(%d%d,&start,&end);for(int k = start; k = end; k+)if(bTreesk)bTrees k = false;L-; /有一棵樹被移去，則有一棵樹被移去，則L減一減一printf(%dn, L+1);delete bTrees;return 0;解法二:采用動(dòng)態(tài)數(shù)組北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程38代碼閱讀o 閱讀的目的n 讀懂別人的程序

24、是一種能力；n 更重要的是充分理解程序就是在對(duì)一個(gè)內(nèi)存區(qū)域反復(fù)做內(nèi)容上的修改，最后得到問題的解的過程。n 程序運(yùn)行的每一步結(jié)束，內(nèi)存的狀態(tài)可以視為一個(gè)現(xiàn)場，程序調(diào)試主要是通過打印現(xiàn)場的方式進(jìn)行。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程39程序閱讀練習(xí) 例1#include int main()int u4, a, b, c, x, y, z;cinu0u1u2u3;a = u0 + u1 + u2 + u3 - 5;b = u0 * (u1 - u2 / u3 + 8);c = u0 * u1 / u2 * u3;x = (a + b + 2) * 3 - u(c + 3) % 4;y = (c * 100

25、- 13) / a / (ub % 3 * 5);if (x + y) % 2 = 0) z = (a + b + c + x + y) / 2;z = (a + b + c - x - y) * 2;cout x + y - z;return 0;輸入：2 5 7 4輸出： 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程40程序閱讀練習(xí) 例2#define N 100void main( ) int number; int primeN; int i, k; prime0 = 2; number=1; for(i=3; iN; i+) for(k=0; primek*primeki) primenumber =

26、i; number+; 閱讀代碼，說出這段程序在做什么。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程41程序閱讀練習(xí) 例2#define N 100void main( ) int number; / 小于小于N的質(zhì)數(shù)個(gè)數(shù)；的質(zhì)數(shù)個(gè)數(shù)； int primeN; / 從從prime0 primenumber-1 中存放生成的質(zhì)數(shù)；中存放生成的質(zhì)數(shù)； int i, k; / 循環(huán)變量；循環(huán)變量； prime0 = 2; number=1; for(i=3; iN; i+) / 從整數(shù)從整數(shù)3開始檢查開始檢查 i 是否為質(zhì)數(shù)是否為質(zhì)數(shù)for(k=0; primek*primeki) / 如果如果 i 不能被前面的質(zhì)數(shù)整

27、除，不能被前面的質(zhì)數(shù)整除， / 則將它作為新質(zhì)數(shù)存入數(shù)組則將它作為新質(zhì)數(shù)存入數(shù)組 primenumber = i; number+; 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程42程序閱讀練習(xí) 例3#include int calculateGCD(int a, int b) if(b=0) return a; return calculateGCD(b,a%b);void main() int n,m; cin n m; cout calculateGCD(n,m) endl;輸入：5 6 輸出：輸入：72 16 輸出：輸入：20 30 輸出：北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程43o上面的求最大公約數(shù)的函數(shù)只需證明a

28、和 b的最大公約數(shù)也是b和a%b的最大公約數(shù)。o證明:1. 如果 ab, 則a%b=a kb(k為正整數(shù))，令r為a和b的公約數(shù)， 則a%b=k1r kk2r=(k1-kk2)r, k1,k2為正整數(shù) 所以r也是a%b的因子。 如果a%b和b的公約數(shù)為p，則 m1p = a km2p, a=(m1+km2)p, 則p也是a的因子。所以a%b和b 與 b和a 具有相同的公約數(shù)，它們的最大公約數(shù)也相同。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程44程序設(shè)計(jì)練習(xí) 例1：1006 生理周期o人生來就有三個(gè)生理周期，分別為體力、感情和智力周期，它們的周期長度為23天、28天和33天。o每一個(gè)周期中有一天是高峰。在高峰這天

29、，人會(huì)在相應(yīng)的方面表現(xiàn)出色。例如，智力周期的高峰，人會(huì)思維敏捷，精力容易高度集中。o因?yàn)槿齻€(gè)周期的周長不同，所以通常三個(gè)周期的高峰不會(huì)落在同一天。o對(duì)于每個(gè)人，我們想知道何時(shí)三個(gè)高峰落在同一天。對(duì)于每個(gè)周期，我們會(huì)給出從當(dāng)前年份的第一天開始，到出現(xiàn)高峰的天數(shù)（不一定是第一次高峰出現(xiàn)的時(shí)間）。o你的任務(wù)是給定一個(gè)從當(dāng)年第一天開始數(shù)的天數(shù)，輸出從給定時(shí)間開始（不包括給定時(shí)間）下一次三個(gè)高峰落在同一天的時(shí)間（距給定時(shí)間的天數(shù)）。例如：給定時(shí)間為10，下次出現(xiàn)三個(gè)高峰同天的時(shí)間是12，則輸出2（注意這里不是3）。 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程451006題o 輸入n 輸入四個(gè)整數(shù)：p, e, i和d。 p

30、, e, i分別表示體力、情感和智力高峰出現(xiàn)的時(shí)間（時(shí)間從當(dāng)年的第一天開始計(jì)算）。d 是給定的時(shí)間，可能小于p, e, 或 i。 所有給定時(shí)間是非負(fù)的并且小于365, 所求的時(shí)間小于21252 。 o 輸出n 從給定時(shí)間起，下一次三個(gè)高峰同天的時(shí)間（距離給定時(shí)間的天數(shù)）。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程461006題：問題分析o 令所求的時(shí)間為當(dāng)年的第x天，則x具有如下性質(zhì)：1) 21252 = x d2) (x-p)%23=03) (x-e)%28=04) (x-i)%33=0北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程471006題o 一個(gè)最簡單直觀的做法就是枚舉從d+1 到 21252 之間所有的數(shù)字，尋找第一個(gè)滿

31、足條件2）3）4）的數(shù)字，注意輸出時(shí)間減去d.。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程481006題o 可以做的進(jìn)一步改進(jìn)是從d+1開始逐一枚舉尋找滿足條件2）的數(shù)字a，從a開始每步加23尋找滿足條件2）3）的數(shù)字b，從b開始每步加23*28尋找滿足條件2）3）4）的數(shù)字x。x就是我們要找的數(shù)字，輸出時(shí)輸出x-d。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程491006題解題思想o 程序設(shè)計(jì)n / 讀入p, e, i, d n / j從d+1 循環(huán)到21252， 如果 (j-p)%23=0，跳出循環(huán)n / j從上次跳出循環(huán)的值循環(huán)到21252， n 如果 (j-e)%28=0，跳出循環(huán)n / j從上次跳出循環(huán)的值循環(huán)到2125

32、2， n 如果 (j-i)%33=0，跳出循環(huán)n / 輸出j-d#includeusing namespace std;int main() int p,e,i,d,j,no=1; cin p e i d; while(p!=-1 & e!=-1 & i!=-1 & d!=-1) for(j=d+1; j=21252; j+) if (j-p)%23 = 0) break; for( ; j=21252; j=j+23) if (j-e)%28 = 0) break; for( ; j=21252; j=j+23*28) if (j-i)%33 = 0) break;

33、cout Case no; cout : the next triple peak occurs in ; cout j-d days. p e i d; no+; return 0;北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程51程序設(shè)計(jì)練習(xí) 例2：1013 稱硬幣o 問題描述n 賽利有12枚銀幣。其中有11枚真幣和1枚假幣。假幣看起來和真幣沒有區(qū)別，但是重量不同。n 但賽利不知道假幣比真幣輕還是重。于是他向朋友借了一架天平。朋友希望賽利稱三次就能找出假幣并且確定假幣是輕是重。例如:如果賽利用天平稱兩枚硬幣，發(fā)現(xiàn)天平平衡，說明兩枚都是真的。如果賽利用一枚真幣與另一枚銀幣比較，發(fā)現(xiàn)它比真幣輕或重，說明它是假幣。經(jīng)

34、過精心安排每次的稱量，賽利保證在稱三次后確定假幣。 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程521013題o 輸入n 輸入有三行，每行表示一次稱量的結(jié)果。賽利事先將銀幣標(biāo)號(hào)為A-L。每次稱量的結(jié)果用三個(gè)以空格隔開的字符串表示：天平左邊放置的硬幣 天平右邊放置的硬幣 平衡狀態(tài)。其中平衡狀態(tài)用up, down, 或 even表示, 分別為右端高、右端低和平衡。天平左右的硬幣數(shù)總是相等的。 o 輸出n 輸出哪一個(gè)標(biāo)號(hào)的銀幣是假幣，并說明它比真幣輕還是重。 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程531013題o 輸入樣例1 ABCD EFGH even ABCI EFJK up ABIJ EFGH even o 輸出樣例K is

35、the counterfeit coin and it is light. 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程541013題o 問題分析n 此題并非要求你給出如何稱量的方案，而是數(shù)據(jù)已經(jīng)保證三組稱量后答案唯一。不是那道傳統(tǒng)的智商測驗(yàn)題。n 此題可以有多種解法，這里只介紹一種比較容易想到和理解的 逐一枚舉法。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程551013題o 總體構(gòu)想 逐一試探法n 對(duì)于每一枚硬幣p isLight ? n Yes. 輸出，n No. isHeavy ?-Yes. 輸出北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程561013題o 定義變量存儲(chǔ)稱量結(jié)果n char left37,right37,result37;n 數(shù)組

36、下標(biāo) 3 代表3次稱量；n 數(shù)組下標(biāo) 7 代表每次左右至多6枚硬幣，多出一個(gè)字符位置是為了方便用字符串讀取的函數(shù)。北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程571013題o 逐一枚舉硬幣的代碼 for(char c=A; c=L;c+) if( isLight(c) ) cout c is the counterfeit coin and it is light.n; break; else if( isHeavy(c) ) cout c is the counterfeit coin and it is heavy.n; break; 北京大學(xué)程序設(shè)計(jì)實(shí)習(xí)課程581013題bool isLight(char x) / 判斷硬幣x是否為輕的代碼 int i; for(i=0; i3; i+)