計(jì)算思維與智能應(yīng)用基礎(chǔ)計(jì)算機(jī)學(xué)院程序設(shè)計(jì)基礎(chǔ)01算法概述02算法設(shè)計(jì)與分析03算法實(shí)現(xiàn)——程序設(shè)計(jì)語(yǔ)言目錄contents01算法概述算法與程序設(shè)計(jì)基礎(chǔ)計(jì)算機(jī)系統(tǒng)的全部功能都是通過(guò)軟件來(lái)體現(xiàn)，軟件的主體是程序，而程序則是對(duì)涉及的相關(guān)數(shù)據(jù)，根據(jù)算法編程實(shí)現(xiàn)。3.1算法概述使用計(jì)算機(jī)來(lái)解決問(wèn)題時(shí)，必須按預(yù)先設(shè)計(jì)好的一系列可操作或可計(jì)算的步驟來(lái)完成任務(wù)，將這種解決問(wèn)題的步驟和方法稱為算法。程序設(shè)計(jì)語(yǔ)言Pascal之父，著名的計(jì)算機(jī)科學(xué)家沃斯（NicklausWirth）有一句名言：程序=算法+數(shù)據(jù)結(jié)構(gòu)算法與程序設(shè)計(jì)基礎(chǔ)算法的基本特征算法描述工具算法的控制結(jié)構(gòu)算法的評(píng)價(jià)指標(biāo)01020304算法與程序設(shè)計(jì)基礎(chǔ)算法的基本特征1）確定性2）可行性3）有窮性4）有0個(gè)或多個(gè)輸入5）有1個(gè)或多個(gè)輸出算法與程序設(shè)計(jì)基礎(chǔ)算法的描述工具算法的自然語(yǔ)言描述算法與程序設(shè)計(jì)基礎(chǔ)算法的流程圖描述算法與程序設(shè)計(jì)基礎(chǔ)算法的偽代碼描述算法與程序設(shè)計(jì)基礎(chǔ)三種基本結(jié)構(gòu)算法與程序設(shè)計(jì)基礎(chǔ)算法的評(píng)價(jià)指標(biāo)正確性可讀性健壯性算法執(zhí)行的效率5.算法占用的空間存儲(chǔ)量時(shí)間復(fù)雜度空間復(fù)雜度02算法設(shè)計(jì)與分析算法與程序設(shè)計(jì)基礎(chǔ)算法設(shè)計(jì)思想及常用算法如何設(shè)計(jì)算法解決遇到的問(wèn)題？其實(shí)很多時(shí)候并不需要大家從零開(kāi)始設(shè)計(jì)一個(gè)新算法，經(jīng)過(guò)幾十年的發(fā)展，計(jì)算機(jī)科學(xué)家們已經(jīng)設(shè)計(jì)了很多巧妙的經(jīng)典算法。在實(shí)際問(wèn)題解決中可以發(fā)現(xiàn)，很多復(fù)雜的問(wèn)題都是由基本算法操作組合而成，掌握常見(jiàn)的經(jīng)典算法思想，對(duì)于問(wèn)題解決時(shí)應(yīng)用和設(shè)計(jì)算法有非常大的裨益。本節(jié)給大家介紹常用的經(jīng)典算法思想。算法與程序設(shè)計(jì)基礎(chǔ)枚舉算法求最值算法排序算法查找算法遞歸算法其他常見(jiàn)的算法策略010203040506常見(jiàn)的算法算法與程序設(shè)計(jì)基礎(chǔ)枚舉算法我國(guó)古代數(shù)學(xué)家張丘建在《算經(jīng)》中提出“百錢買百雞”問(wèn)題：一個(gè)人有一百文錢，打算買一百只雞。到市場(chǎng)一看，公雞五文錢一只，母雞三文錢一只，小雞一文錢三只。請(qǐng)問(wèn)有多少種買法，才能剛好用一百文錢買一百只雞？設(shè)x，y，z分別為公雞、母雞和小雞的只數(shù)，可列出下面的方程：x+y+z=1005x+3y+z/3=100兩個(gè)方程怎么解三個(gè)未知數(shù)呢？這類問(wèn)題在計(jì)算機(jī)科學(xué)中就是典型的枚舉法問(wèn)題。算法與程序設(shè)計(jì)基礎(chǔ)基本思想：首先依據(jù)題目的部分條件確定答案的大致范圍，然后在這范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到全部情況驗(yàn)證完為止。若某個(gè)情況驗(yàn)證符合題目的條件，則為該問(wèn)題的一個(gè)答案，若全部情況驗(yàn)證完后均不符合題目的條件，則該問(wèn)題無(wú)解。由于x，y，z為正整數(shù)，雞的總數(shù)是100，可以初步確定x，y，z的取值范圍：（1）x的取值范圍為0～100（2）y的取值范圍為0～100（3）z的取值范圍為0～100遍歷x，y，z的所有可能組合，遍歷完所有可能的組合，也就找到了問(wèn)題的所有解。算法與程序設(shè)計(jì)基礎(chǔ)枚舉算法能解決許多實(shí)際問(wèn)題，是一種最直接最簡(jiǎn)單的算法，但也是最耗時(shí)的一種算法，它用時(shí)間上的犧牲換來(lái)解的全面性保證。因此，枚舉法也叫窮舉法。在枚舉算法中，枚舉對(duì)象的選擇是非常重要的，它直接影響著算法的時(shí)間復(fù)雜度，選擇適當(dāng)?shù)拿杜e對(duì)象、縮小枚舉范圍都可以獲得更高的效率。（1）x的取值范圍縮小為0～20（2）y的取值范圍縮小為0～33（3）當(dāng)x和y確定后，z=100-x-y算法與程序設(shè)計(jì)基礎(chǔ)求最值算法在現(xiàn)實(shí)生活中,我們經(jīng)常遇到尋找最大值或最小值問(wèn)題,比如期末考試結(jié)束后，找出總分第一名的同學(xué)。求最值問(wèn)題也有經(jīng)典的算法思路，以在n個(gè)數(shù)中求最大值和最小值為例，算法思路如下：定義兩個(gè)變量分別存放最大值和最小值，假設(shè)變量名為max和min。一般將n個(gè)數(shù)中的第1個(gè)數(shù)賦給max和min作為初始值，然后將剩下的每個(gè)數(shù)分別與max和min比較，如果這個(gè)數(shù)比max大，說(shuō)明max里存放的不是最大值，則將新的最大值賦給max；如果這個(gè)數(shù)比min小，說(shuō)明min里存放的不是最小值，則將新的最小值賦給min，即讓max中總是放當(dāng)前已經(jīng)比較過(guò)的最大數(shù)，讓min中總是放當(dāng)前比較過(guò)的最小值，這樣當(dāng)所有數(shù)都比較完時(shí)，在max中放的就是n個(gè)數(shù)中的最大數(shù)，在min中放的就是n個(gè)數(shù)中的最小數(shù)。算法與程序設(shè)計(jì)基礎(chǔ)排序算法排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組無(wú)序的數(shù)據(jù)序列調(diào)整為有序的數(shù)據(jù)序列。生活中經(jīng)常遇到需要排序的情況，比如期末考試后，老師需要對(duì)班級(jí)同學(xué)的成績(jī)按總分降序排個(gè)序；奧運(yùn)會(huì)的金牌榜上，需要對(duì)每個(gè)國(guó)家獲得獎(jiǎng)牌的情況進(jìn)行排序；網(wǎng)上書城的圖書排行榜需要列出近1個(gè)月內(nèi)銷量Top10的暢銷書，等等。所有這些都可以利用排序算法實(shí)現(xiàn)。算法與程序設(shè)計(jì)基礎(chǔ)0201選擇排序?qū)⒁唤Mn個(gè)數(shù)按從小到大的順序升序排序，選擇排序的思想是對(duì)每組數(shù)，每次都找出當(dāng)前最小的數(shù)，放在該組數(shù)的第一個(gè)位置，然后對(duì)剩下的數(shù)繼續(xù)重復(fù)這個(gè)操作，n個(gè)數(shù)，排序的輪數(shù)需要執(zhí)行n-1輪，直到最后一組數(shù)只剩下一個(gè)數(shù)為止。冒泡排序通過(guò)相鄰元素之間的交換，使較小的元素逐步從序列的后端移到序列的前端，使較大的元素從序列的前端移到后端。這就像水底的氣泡不斷向上“冒”一樣，因此稱為“冒泡排序”。算法與程序設(shè)計(jì)基礎(chǔ)第1輪：835241找到最小數(shù)1交換到第1個(gè)位置原始數(shù)據(jù)：835241

第2輪：135248找到最小數(shù)2交換到第2個(gè)位置第3輪：125348找到最小數(shù)3交換到第3個(gè)位置第4輪：123548找到最小數(shù)4交換到第4個(gè)位置第5輪：123458找到最小數(shù)5交換到第5個(gè)位置最后結(jié)果123458總結(jié)：n個(gè)數(shù)據(jù)需要“查找-交換”n-1次。選擇排序算法與程序設(shè)計(jì)基礎(chǔ)122331234588352452418241583145813458第一輪183524原始數(shù)據(jù)第二輪第三輪第四輪第五輪最終結(jié)果總結(jié)：n個(gè)元素的數(shù)據(jù)序列要進(jìn)行n-1輪冒泡。沉底了冒泡排序算法與程序設(shè)計(jì)基礎(chǔ)順序查找的基本思想是：從表的一端開(kāi)始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值K比較。若當(dāng)前掃描到的關(guān)鍵字與K相等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于K的結(jié)點(diǎn)，則查找失敗。查找算法1.順序查找假定有100個(gè)無(wú)序的數(shù)據(jù)，存放于一維數(shù)組v(1)…v(100)中?，F(xiàn)要求查找這些數(shù)據(jù)里面有沒(méi)有值為K的數(shù)據(jù)元素，若找到就給出其所在位置，若沒(méi)找到則給出相應(yīng)提示信息。24算法與程序設(shè)計(jì)基礎(chǔ)2.二分查找

二分查找又稱折半查找，它是一種效率比較高的查找方法。但是這種查找方法的前提是線性表“已經(jīng)排好序”，排序可以是升序也可以是降序。二分查找的基本思想：

設(shè)數(shù)組V(low…h(huán)igh)已按升序排序。將數(shù)組中間位置的關(guān)鍵字與查找關(guān)鍵字比較：若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找。重復(fù)這一過(guò)程直到查找成功，或直至當(dāng)前的查找區(qū)間為空為止。算法與程序設(shè)計(jì)基礎(chǔ)對(duì)給定的有序數(shù)列{3,5,11,17,21,23,28,30,32,50}，按二分查找算法，查找關(guān)鍵字為30的數(shù)據(jù)元素。需查找?guī)状尾拍苷业?？如果?00個(gè)數(shù)，需要查找?guī)状尾拍苷业?？如果查找關(guān)鍵字為31的數(shù)據(jù)元素，需要查找?guī)状?？mid351117212328303250lowhighmidlowmidlowhigh算法與程序設(shè)計(jì)基礎(chǔ)二分查找的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，只要檢查中間項(xiàng)就可鎖定搜索關(guān)鍵字位于哪一半，這樣一來(lái)，每猜一次相當(dāng)于將待查找的目標(biāo)范圍減少一半。再看超市的例子，如果采用二分搜索方式在1萬(wàn)件貨品中查找，現(xiàn)在僅需要14次搜索，快到讓人無(wú)法察覺(jué)。二分查找也有缺點(diǎn)，那就是要求待查表為有序表，且插入刪除元素較困難。因此，二分查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表?！舅?/p>

考】算法與程序設(shè)計(jì)基礎(chǔ)遞歸算法遞歸就是回推加上遞推的過(guò)程：遞歸必須具備兩個(gè)條件：①問(wèn)題本身具有遞歸性質(zhì)；②遞歸必需有結(jié)束條件，即遞歸出口遞歸的思維方式：每次重復(fù)問(wèn)題本身，但又比上一次簡(jiǎn)單一些，直到問(wèn)題簡(jiǎn)單到直接可以說(shuō)出答案，如1!=1。所以說(shuō)遞歸算法就是直接或間接地調(diào)用原算法本身的一種算法。算法與程序設(shè)計(jì)基礎(chǔ)64片金片按規(guī)則從A針移到C針需要移多少次？若每秒移1個(gè)金片，多長(zhǎng)時(shí)間內(nèi)能移完？算法與程序設(shè)計(jì)基礎(chǔ)甲乙丙設(shè)3個(gè)圓盤從小到大依次稱為1、2、3號(hào)盤算法與程序設(shè)計(jì)基礎(chǔ)甲設(shè)3個(gè)圓盤從小到大依次稱為1、2、3號(hào)盤乙丙算法與程序設(shè)計(jì)基礎(chǔ)甲乙丙設(shè)3個(gè)圓盤從小到大依次稱為1、2、3號(hào)盤算法與程序設(shè)計(jì)基礎(chǔ)甲乙丙設(shè)3個(gè)圓盤從小到大依次稱為1、2、3號(hào)盤算法與程序設(shè)計(jì)基礎(chǔ)把這個(gè)問(wèn)題抽象出來(lái)，就是把n個(gè)盤子借助B針從A針移到C針。解決的方法如下：移動(dòng)的過(guò)程可分解為三個(gè)步驟：第1步：把A上的n-1個(gè)圓盤移到B上；第2步：把A上的一個(gè)圓盤移到C上；第3步：把B上的n-1個(gè)圓盤移到C上。算法與程序設(shè)計(jì)基礎(chǔ)ABC算法與程序設(shè)計(jì)基礎(chǔ)ABC算法與程序設(shè)計(jì)基礎(chǔ)漢諾塔：n個(gè)盤片的移動(dòng)次數(shù)n個(gè)盤子的漢諾塔問(wèn)題需要移動(dòng)的盤子數(shù)是n-1個(gè)盤子的漢諾塔問(wèn)題需要移動(dòng)的盤子數(shù)的2倍加1即:h(n)=2×h(n-1)+1=2×(2×h(n-2)+1）+1=22×h(n-2)+2+1=23×h(n-3)+22+2+1……………=2n-1×h(1)+2n-2+…+22+2+1=2n-1假如每秒移1個(gè)盤片，共需多長(zhǎng)時(shí)間呢？需要5845億年以上。算法與程序設(shè)計(jì)基礎(chǔ)遞歸應(yīng)用遞歸作為一種算法在程序設(shè)計(jì)中被廣泛應(yīng)用，它常常把一個(gè)大型的復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解。缺陷用遞歸算法解決一些復(fù)雜問(wèn)題時(shí)，往往在形式上更加簡(jiǎn)潔，易于理解，但是遞歸方法的運(yùn)行效率較低，時(shí)間和空間復(fù)雜度都比較高。03算法的實(shí)現(xiàn)—程序設(shè)計(jì)語(yǔ)言算法與程序設(shè)計(jì)基礎(chǔ)計(jì)算機(jī)語(yǔ)言也稱為程序設(shè)計(jì)語(yǔ)言(ProgramLanguage)，即編寫計(jì)算機(jī)程序所用的語(yǔ)言。程序是根據(jù)算法編寫的。算法設(shè)計(jì)好后，這時(shí)候就需要選擇一種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言，編寫程序?qū)崿F(xiàn)算法功能。機(jī)器語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言算法與程序設(shè)計(jì)基礎(chǔ)算法與程序設(shè)計(jì)基礎(chǔ)主流的程序設(shè)計(jì)方法1.結(jié)構(gòu)化程序設(shè)計(jì)方法1965年荷蘭學(xué)者迪克斯特拉（E.W.Dijikstra）最早提出了“結(jié)構(gòu)化程序設(shè)計(jì)”思想。1）自頂向下2）逐步細(xì)化3）模塊化設(shè)計(jì)4）結(jié)構(gòu)化程序設(shè)計(jì)方法限制使用GOTO語(yǔ)句算法與程序設(shè)計(jì)基礎(chǔ)2.面向?qū)ο蟪绦蛟O(shè)計(jì)方法面向?qū)ο蟪绦蛟O(shè)計(jì)（object-orientedprogramming，縮寫OOP）方法起源于面向?qū)ο蟮木幊陶Z(yǔ)言。20世紀(jì)60年代后期，以挪威奧斯陸大學(xué)和挪威計(jì)算機(jī)中心研制的SIMULA語(yǔ)言為標(biāo)志，出現(xiàn)了類和對(duì)象的概念，類作為語(yǔ)言機(jī)制用來(lái)封裝數(shù)據(jù)的相關(guān)操作。進(jìn)入20世紀(jì)80年代后，出現(xiàn)了一大批面向?qū)ο蟮木幊陶Z(yǔ)言，如Smalltalk語(yǔ)言、C++語(yǔ)言、Java語(yǔ)言等。1）對(duì)象、屬性和方法2）類3）封裝性4）繼承性5）多態(tài)性算法與程序設(shè)計(jì)基礎(chǔ)良好的程序設(shè)計(jì)風(fēng)格應(yīng)考慮以下因素：1）源程序文檔化2）語(yǔ)句的結(jié)構(gòu)應(yīng)該簡(jiǎn)單直接，不要為提高效率而復(fù)雜化3）輸入數(shù)據(jù)前要有提示信息，輸出信息符合規(guī)范Python基礎(chǔ)Lifeisshort,youneedPython荷蘭人Guido發(fā)明1989正式發(fā)布1991Python2.0發(fā)布2000Python3.0發(fā)布2008Python3.112023Python語(yǔ)言的歷史Python基礎(chǔ)開(kāi)發(fā)效率高

學(xué)習(xí)難度低

擴(kuò)展性好移植性好資源豐富

可以在任何安裝解釋器的計(jì)算機(jī)環(huán)境中執(zhí)行；可以不經(jīng)修改地實(shí)現(xiàn)跨平臺(tái)運(yùn)行?？梢约蒀、C++、Java等語(yǔ)言編寫的代碼，所以Python又稱為膠水語(yǔ)言。Python的標(biāo)準(zhǔn)庫(kù)功能很強(qiáng)大，再加上不同應(yīng)用領(lǐng)域眾多開(kāi)源的第三方程序庫(kù)，給開(kāi)發(fā)者提供了很多便利。Python的語(yǔ)法較為簡(jiǎn)單，容易學(xué)習(xí)容易理解，同時(shí)網(wǎng)絡(luò)上學(xué)習(xí)資源也很豐富。相同功能程序，Python代碼量只是其他編程語(yǔ)言的若干分之一。Python語(yǔ)言的特性Python基礎(chǔ)Python語(yǔ)言是一個(gè)通用編程語(yǔ)言，可用于編寫各領(lǐng)域的應(yīng)用程序，這為該語(yǔ)言提供了廣闊的應(yīng)用空間。從科學(xué)計(jì)算、數(shù)據(jù)處理到人工智能、網(wǎng)絡(luò)爬蟲、機(jī)器人等，Python語(yǔ)言都能夠發(fā)揮重要作用，而且很出色。Python基礎(chǔ)

/downloads/