算法與數(shù)據(jù)結(jié)構(gòu)任課教師：戴韡自我介紹戴韡，數(shù)學(xué)博士，中央財(cái)經(jīng)大學(xué)金融工程系講師。目前主要研究方向是不確定理論，包括不確定理論框架下的金融問題，例如投資組合選擇，期權(quán)定價(jià)等。Email:

教材選擇教材選用《C語言程序設(shè)計(jì)：現(xiàn)代方法》〔著〕《數(shù)據(jù)結(jié)構(gòu)和算法分析——C語言描述》〔〕考核標(biāo)準(zhǔn)期中小測 30分大作業(yè) 30分考試

40分出勤

5分什么是“算法〞與“數(shù)據(jù)結(jié)構(gòu)〞？圖靈獎(jiǎng)得主NiklausWirth說: 算法+數(shù)據(jù)結(jié)構(gòu)=程序算法〔algorithm〕：對操作的描述。數(shù)據(jù)結(jié)構(gòu)〔datastructure〕：對數(shù)據(jù)的描述?！八惴ㄅc數(shù)據(jù)結(jié)構(gòu)〞的應(yīng)用求解模型，解決現(xiàn)實(shí)中的問題教學(xué)安排第一學(xué)期根本的C語言教學(xué)算法分析鏈表、棧、隊(duì)列樹第二學(xué)期算法設(shè)計(jì)圖論算法排序算法高級數(shù)據(jù)結(jié)構(gòu)算法的概念廣義地說，為解決一個(gè)問題而采取的方法和步驟，就稱為“算法〞。對同一個(gè)問題，可以有不同的解題方法和步驟例：求方法1：1+2，+3，+4，一直加到100加99次方法2：100+(1+99)+(2+98)+…+(49+51)+50=100+49×100+50加51次為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇適宜的算法。希望方法簡單，運(yùn)算步驟少。計(jì)算機(jī)算法可分為兩大類別：數(shù)值運(yùn)算算法：求數(shù)值解，例如求方程的根、求函數(shù)的定積分等。非數(shù)值運(yùn)算：包括的面十分廣泛，最常見的是用于事務(wù)管理領(lǐng)域，例如圖書檢索、人事管理、行車調(diào)度管理等。例1:求1×2×3×4×5

步驟1：先求1×2，得到結(jié)果2步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6步驟3：將6再乘以4，得24步驟4：將24再乘以5，得120如果要求1×2×…×1000，那么要寫999個(gè)步驟S1：使p=1S2：使i=2S3：使p×i，乘積仍放在變量p中，可表示為：p×i->pS4：使i的值加1，即i+1->i。S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否那么，算法結(jié)束。最后得到p的值就是5!的值?？梢栽O(shè)兩個(gè)變量：一個(gè)變量代表被乘數(shù)，一個(gè)變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結(jié)果,算法可改寫：S1：1->pS2：3->iS3：p×i->pS4：i+2->iS5：假設(shè)i≤11，返回S3。否那么，結(jié)束。

如果題目改為：求1×3×5×……×1000算法只需作很少的改動：用這種方法表示的算法具有通用性、靈活性。S3到S5組成一個(gè)循環(huán)，在實(shí)現(xiàn)算法時(shí)要反復(fù)屢次執(zhí)行S3，S4，S5等步驟，直到某一時(shí)刻，執(zhí)行S5步驟時(shí)經(jīng)過判斷，乘數(shù)i已超過規(guī)定的數(shù)值而不返回S3步驟為止。此時(shí)算法結(jié)束，變量p的值就是所求結(jié)果。例2

判定2000～2500年中的每一年是否閏年，將結(jié)果輸出。

分析：閏年的條件是：(1)能被4整除，但不能被100整除的年份都是閏年，如1996,2004年是閏年；(2)能被100整除，又能被400整除的年份是閏年。如1600,2000年是閏年。不符合這兩個(gè)條件的年份不是閏年。設(shè)y為被檢測的年份，算法可表示如下：S1：2000yS2：假設(shè)y不能被4整除，那么輸出y“不是閏年〞。然后轉(zhuǎn)到S6。S3：假設(shè)y能被4整除，不能被100整除，那么輸出y“是閏年〞。然后轉(zhuǎn)到S6。S4：假設(shè)y能被100整除，又能被400整除，輸出y“是閏年〞，否那么輸出“不是閏年〞。然后轉(zhuǎn)到S6。S5:輸出y“不是閏年〞。S6：y+1yS7：當(dāng)y≤2500時(shí)，轉(zhuǎn)S2繼續(xù)執(zhí)行，如y＞2500，算法停止。以上算法中每做一步都分別別離出一些范圍(巳能判定為閏年或非閏年)，逐步縮小范圍，直至執(zhí)行S5時(shí)，只可能是非閏年。

例3

對一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。概念：所謂素?cái)?shù)，是指除了1和該數(shù)本身之外，不能被其它任何整數(shù)整除的數(shù)。例如，13是素?cái)?shù)。因?yàn)樗荒鼙?，3，4，…，12整除。分析：判斷一個(gè)數(shù)n(n≥3)是否素?cái)?shù)的方法：將n作為被除數(shù)，將2到(n-1)各個(gè)整數(shù)輪流作為除數(shù)，如果都不能被整除，那么n為素?cái)?shù)。算法如下

：S1：輸入n的值S2：i=2〔i作為除數(shù)〕S3：n被i除，得余數(shù)rS4：如果r=0，表示n能被i整除，那么打印n“不是素?cái)?shù)〞，算法結(jié)束。否那么執(zhí)行S5S5：i+1->iS6：如果i≤n-1，返回S3。否那么打印n“是素?cái)?shù)〞。然后結(jié)束。

實(shí)際上，n不必被2到(n-1)的整數(shù)除，只需被2到n/2間整數(shù)除，甚至只需被2到之間的整數(shù)除即可。算法的特性一個(gè)算法應(yīng)該具有以下特點(diǎn)：有窮性確定性有效性流程圖美國國家標(biāo)準(zhǔn)化協(xié)會ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號：起止框判斷框處理框輸入/輸出框注釋框流向線連接點(diǎn)判斷素?cái)?shù)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的存儲內(nèi)存塊？線形存取順序樹圖C語言C語言是國際上廣泛流行的高級語言。C語言是在B語言的根底上開展起來的。B〔BCPL〕語言是1970年由美國貝爾實(shí)驗(yàn)室設(shè)計(jì)的,并用于編寫了第一個(gè)UNIX操作系統(tǒng),在PDP7上實(shí)現(xiàn)。優(yōu)點(diǎn)：精練,接近硬件，缺點(diǎn)：過于簡單,數(shù)據(jù)無類型。1973年貝爾實(shí)驗(yàn)室的D.M.Ritchie在B語言的根底上設(shè)計(jì)出了C語言，對B取長補(bǔ)短，并用之改寫了原來用匯編編寫的UNIX，(即UNIX第5版〕，但僅在貝爾實(shí)驗(yàn)室使用。1975年UNIX第6版發(fā)布,C優(yōu)點(diǎn)突出引起關(guān)注。1977年出現(xiàn)了《可移植C語言編譯程序》，推動了UNIX在各種機(jī)器上實(shí)現(xiàn)，C語言也得到推廣，其開展相輔相成。1978年影響深遠(yuǎn)的名著《TheCProgrammingLanguage》由BrianW.Kernighan和DennisM.Ritchie合著,被稱為標(biāo)準(zhǔn)C。之后，C語言先后移植到大、中、小、微型計(jì)算機(jī)上,已獨(dú)立于UNIX和PDP，風(fēng)行世界,成為最廣泛的幾種計(jì)算機(jī)語言之一。C語言特點(diǎn)〔1〕語言簡潔、緊湊,使用方便、靈活。32個(gè)關(guān)鍵字、9種控制語句,程序形式自由〔2〕運(yùn)算符豐富。34種運(yùn)算符〔3〕數(shù)據(jù)類型豐富,具有現(xiàn)代語言的各種數(shù)據(jù)結(jié)構(gòu)。〔4〕具有結(jié)構(gòu)化的控制語句，是完全模塊化和結(jié)構(gòu)化的語言。〔5〕語法限制不太嚴(yán)格,程序設(shè)計(jì)自由度大?！?〕允許直接訪問物理地址,能進(jìn)行位操作,能實(shí)現(xiàn)匯編語言的大局部功能,可直接對硬件進(jìn)行操作。兼有高級和低級語言的特點(diǎn)。〔7〕目標(biāo)代碼質(zhì)量高,程序執(zhí)行效率高。只比匯編程序生成的目標(biāo)代碼效率低10％-20%?！?〕程序可移植性好(與匯編語言比)。根本上不做修改就能用于各種型號的計(jì)算機(jī)和各種操作系統(tǒng)。問題：既然有了面向?qū)ο蟮腃++語言，為什么還要學(xué)習(xí)C語言？解釋1：C++是由于開發(fā)大型應(yīng)用軟件的需要而產(chǎn)生的，并不是所有的人都要去編寫大型軟件；解釋2：面向?qū)ο蟮母资敲嫦蜻^程。C++是面向?qū)ο蟮恼Z言，C是面向過程的，C++學(xué)起來比C語言困難，所以不太適合程序設(shè)計(jì)的初學(xué)者。補(bǔ)充：程序的設(shè)計(jì)面向程序：自頂向下，逐步求精。面向?qū)ο螅鹤韵露希鸩椒e累。

簡單的C語言程序介紹#include<stdio.h>void

main(){

printf("ThisisaCprogram.\n");}/*文件包含*//*主函數(shù)*//*函數(shù)體開始*//*輸出語句*//*函數(shù)體結(jié)束*/說明：main-主函數(shù)名，void-函數(shù)類型每個(gè)C程序必須有一個(gè)主函數(shù)main{}是函數(shù)開始和結(jié)束的標(biāo)志,不可省每個(gè)C語句以分號結(jié)束使用標(biāo)準(zhǔn)庫函數(shù)時(shí)應(yīng)在程序開頭一行寫：

#include<stdio.h>說明：

本程序的作用是輸出一行信息:ThisisaCprogram.例1.求兩數(shù)之和

#include<stdio.h>

voidmain()/*求兩數(shù)之和*/

{

inta,b,sum;/*聲明，定義變量為整型*/

/*以下3行為C語句*/

a=123;b=456;

sum=a+b;

printf(″sumis%d＼n″,sum);

}說明：

/*……*/表示注釋。注釋只是給人看的,對編譯和運(yùn)行不起作用。所以可以用漢字或英文字符表示，可以出現(xiàn)在一行中的最右側(cè)，也可以單獨(dú)成為一行。說明：

輸出一行信息:sumis579例2.求3個(gè)數(shù)中較大者。

#include<stdio.h>

voidmain()/*主函數(shù)*/

{

intmax(intx,inty);/對被調(diào)用函數(shù)max的聲明*/

inta,b,c;/*定義變量a、b、c*/

scanf(″％d,％d″,&a,&b);/*輸入變量a和b的值*/

c=max(a,b);/*調(diào)用max函數(shù),將得到的值賦給c*/

printf(″max=％d\\n″,c);/*輸出c的值*/

}程序運(yùn)行情況如下：8,5↙(輸入8和5賦給a和b)max=8(輸出c的值)intmax(intx,inty){intz;if(x>y)z=x;elsez=y;return(z);}max(int

x,int

y);max(a,b);

說明：本程序包括main和被調(diào)用函數(shù)max兩個(gè)函數(shù)。max函數(shù)的作用是將x和y中較大者的值賦給變量z。return語句將z的值返回給主調(diào)函數(shù)main。簡單的C語言程序介紹C程序：(1)C程序是由函數(shù)構(gòu)成的。這使得程序容易實(shí)現(xiàn)模塊化。(2)一個(gè)函數(shù)由兩局部組成:函數(shù)的首部：例2中的max函數(shù)首部intmax(intx,inty)函數(shù)體：花括號內(nèi)的局部。假設(shè)一個(gè)函數(shù)有多個(gè)花括號,那么最外層的一對花括號為函數(shù)體的范圍。函數(shù)體包括兩局部：聲明局部：inta,b,c;可缺省執(zhí)行局部：由假設(shè)干個(gè)語句組成?？扇笔『唵蔚腃語言程序介紹注意：函數(shù)的聲明局部和執(zhí)行局部都可缺省，例如：voiddump(){}這是一個(gè)空函數(shù),什么也不做,但是合法的函數(shù)。簡單的C語言程序介紹小結(jié)：(3)C程序總是從main函數(shù)開始執(zhí)行的,與main函數(shù)的位置無關(guān)。(4)C程序書寫格式自由,一行內(nèi)可以寫幾個(gè)語句,一個(gè)語句可以分寫在多行上，C程序沒有行號。(5)每個(gè)語句和數(shù)據(jù)聲明的最后必須有一個(gè)分號。(6)C語言本身沒有輸入輸出語句。輸入和輸出的操作是由庫函數(shù)scanf和printf等函數(shù)來完成的。C對輸入輸出實(shí)行“函數(shù)化〞。C語言的靈活性 發(fā)信人:zhaojk(明天到操場操到天明),信區(qū):Joke 標(biāo)題:[進(jìn)版]壓歲錢，轉(zhuǎn)載 發(fā)信站:水木社區(qū)(TueJan2423:02:322012),站內(nèi) 前過年都是我們給爸媽錢，然后爸媽再給孩子壓歲錢。

我們給100,他們就給孩子200,我們給200,他們就給孩子400,我們給500,他們就給孩子1000, 直到去年，開展到我們給1000,他們就給孩子2000, 今年，我跟媳婦一商量，決定大家都快樂點(diǎn)，我們就給了2000