1,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),2,課程設(shè)置,算法基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算查找與排序技術(shù)資源管理技術(shù)數(shù)據(jù)庫(kù)技術(shù)應(yīng)用軟件設(shè)計(jì)與開(kāi)發(fā)技術(shù),3,學(xué)習(xí)目的,1、了解軟件技術(shù)基礎(chǔ)知識(shí)2、掌握數(shù)據(jù)結(jié)構(gòu)的概念，幾種基本結(jié)構(gòu)，查找和排序方法，能編寫正確算法。編寫簡(jiǎn)單程序。3、掌握資源管理技術(shù)的相關(guān)知識(shí),4,學(xué)習(xí)與考核,教師講授為主上機(jī)實(shí)驗(yàn)：上機(jī)語(yǔ)言c語(yǔ)言考核方式：平時(shí)成績(jī)20%+上機(jī)實(shí)驗(yàn)、完成實(shí)驗(yàn)報(bào)告20%+期末考試成績(jī)60%,5,緒論,計(jì)算機(jī)硬件及其發(fā)展計(jì)算機(jī)軟件數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫(kù)與軟件工程,6,計(jì)算機(jī)硬件及發(fā)展,發(fā)展歷史電子管晶體管集成電路超大規(guī)模集成電路發(fā)展路線及規(guī)律速度慢速度快體積大容量小體積小容量大外設(shè)少、簡(jiǎn)單外設(shè)繁多、復(fù)雜二進(jìn)制處理原則,軟件從短小、精干、講究效率到復(fù)雜可靠、兼容性強(qiáng)、結(jié)構(gòu)性好,7,計(jì)算機(jī)軟件,軟件的概念軟件是：與一系統(tǒng)（尤指計(jì)算機(jī)系統(tǒng)）有關(guān)的程序、步驟和有關(guān)文件編制的完整集合。特指特定類型計(jì)算機(jī)所使用的程序的總稱，連同與計(jì)算機(jī)或程序有關(guān)的資料，例如手冊(cè)、圖表和操作指令。功能：針對(duì)一個(gè)系統(tǒng)（計(jì)算機(jī)），合理組織工作。程序設(shè)計(jì)語(yǔ)言的發(fā)展經(jīng)歷：機(jī)器語(yǔ)言，匯編語(yǔ)言，高級(jí)語(yǔ)言，面向?qū)ο笳Z(yǔ)言軟件的發(fā)展：語(yǔ)言的發(fā)展-操作系統(tǒng)的出現(xiàn)-數(shù)據(jù)庫(kù)的出現(xiàn)-網(wǎng)絡(luò)的出現(xiàn),8,數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫(kù)與軟件工程,數(shù)據(jù)結(jié)構(gòu)：描述數(shù)據(jù)及數(shù)據(jù)元素之間的關(guān)系，數(shù)據(jù)在計(jì)算機(jī)系統(tǒng)中的存儲(chǔ)方式及數(shù)據(jù)的運(yùn)算。軟件技術(shù)基礎(chǔ)的基礎(chǔ)操作系統(tǒng)：方便用戶有效利用各種軟、硬件資源的程序的集合建造工作環(huán)境、平臺(tái)數(shù)據(jù)庫(kù)：可以共享相關(guān)數(shù)據(jù)，以一定組成方式的集合進(jìn)行數(shù)據(jù)信息處理的強(qiáng)大應(yīng)用。軟件工程：軟件設(shè)計(jì)的基本過(guò)程，思想和方法。,9,第一章算法,2019/12/18,算法的基本概念算法設(shè)計(jì)的基本方法算法的復(fù)雜度分析C語(yǔ)言簡(jiǎn)介,10,算法的基本概念,算法的基本特征（1）能行性（2）確定性（3）有窮性（4）擁有足夠的情報(bào),算法是指解題方案的準(zhǔn)確而完整的描述。,11,算法與程序,相同點(diǎn)：都是解決問(wèn)題的方法和步驟描述方法：程序使用程序設(shè)計(jì)語(yǔ)言算法使用框圖或其他語(yǔ)言聯(lián)系：程序用某種程序設(shè)計(jì)語(yǔ)言來(lái)實(shí)現(xiàn)算法,12,怎樣表示一個(gè)算法,1、用自然語(yǔ)言表示算法2、用流程圖表示算法3、用偽代碼表示算法4、用機(jī)器語(yǔ)言表示算法,13,算法設(shè)計(jì)基本方法,在數(shù)據(jù)結(jié)構(gòu)中常見(jiàn)的問(wèn)題創(chuàng)建、插入、刪除、更新、檢索、排序注意：每個(gè)問(wèn)題都有一種和多種算法找到效率最高的；以最容易理解的方式設(shè)計(jì)；設(shè)計(jì)的算法不容易出錯(cuò)或出錯(cuò)情況較少。,14,算法的基本要素,(1)對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作：a).算術(shù)運(yùn)算，加、減、乘、除等運(yùn)算；b).邏輯運(yùn)算，“與”、“或”、“非”等運(yùn)算；c).關(guān)系運(yùn)算，“大于”、“小于”、“等于”、“不等于”等運(yùn)算；d).數(shù)據(jù)傳輸，主要包括賦值、輸入、輸出等操作；(2)算法的控制結(jié)構(gòu),15,算法設(shè)計(jì)基本方法,列舉法基本思想：根據(jù)提出的問(wèn)題，列舉所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰?。特點(diǎn)：算法簡(jiǎn)單；工作量大,16,舉例：設(shè)每只母雞值3元，每只公雞值2元，兩只小雞值1元?，F(xiàn)要用100元買100只雞，設(shè)計(jì)買雞方案。,方案一假設(shè)買母雞i只，公雞j只，小雞k只。procedurebaijifori=0to100doforj=0to100dofork=0to100dom=i+j+kn=3i+2j+0.5kif(m=100)and(n=100)thenoutputI,j,kreturn,方案二procedurebaijifori=0to33doforj=0to50-1.5idok=100-i-jIf(3i+2j+0.5k=100)thenoutputI,j,kreturn,17,2、歸納法,基本思想通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。,18,2、遞歸法,基本思想為了降低問(wèn)題的復(fù)雜度，總是將問(wèn)題組成分解，最后歸納為一個(gè)最簡(jiǎn)單的問(wèn)題，當(dāng)解決這個(gè)簡(jiǎn)單問(wèn)題后，再沿著就原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸。,19,例題：用遞歸方法求n！,遞歸公式表示：,20,程序,#includeintmain()intfac(intn);intn;inty;printf(“inputanintegernumber”);scanf(“%d”,intfac(intn)intf;if(n<0)printf(“n<0,dataerror!”);elseif(n=0|n=1)f=1;elsef=fac(n-1)*n;return(f);,21,減半遞推技術(shù),所謂“減半”，是指將問(wèn)題的規(guī)模減半；所謂“遞推”，就是重復(fù)減半的過(guò)程。,舉例：設(shè)兩個(gè)二階矩陣為,需要8次乘法,兩個(gè)矩陣相乘只需要7次乘法,22,回溯法,基本思想：通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，然后沿著這個(gè)線索逐步試探，對(duì)于每一步的試探，若試探成功，就得到問(wèn)題的解，若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。,23,1.3算法的復(fù)雜度分析,算法的時(shí)間復(fù)雜度(算法的工作量)采用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量。相關(guān)因素：(1)基本運(yùn)算次數(shù)還與問(wèn)題的規(guī)模n有關(guān)。算法的工作量=f(n)(2)當(dāng)取決于某一個(gè)特性輸入時(shí)，有兩種方法來(lái)衡量工作量：平均性態(tài)最壞情況復(fù)雜性,24,舉例：采用順序搜索法，在長(zhǎng)度為n的一維數(shù)組中查找值為x的元素,平均性態(tài)分析：設(shè)需要查找的x出現(xiàn)在數(shù)組中每個(gè)位置上的可能性一樣，概率為q/n，x不在數(shù)組中的概率為1-q,比較次數(shù),平均情況下比較次數(shù),25,最壞情況是發(fā)生在需要查找的x是數(shù)組中的最后一個(gè)元素或x不在數(shù)組中的時(shí)候，此時(shí)顯然,（2）最壞情況復(fù)雜度,26,算法的空間復(fù)雜度,一般指執(zhí)行這個(gè)算法所需要的內(nèi)存空間，包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間。,