計算機(jī)科學(xué)與工程學(xué)院張玉磊

例如：需求-無紙化考試現(xiàn)狀-當(dāng)前存在多種無紙化考試系統(tǒng)方式：利用已有的程序或軟件“過去時態(tài)”計算機(jī)解決問題的方式2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽題目（B）設(shè)計太陽能小屋：在建筑物外表面鋪設(shè)光伏電池，既可以供家庭使用，又可將剩余電量輸入電網(wǎng)。但發(fā)電效率或發(fā)電量受諸多因素的影響。參考附件提供的數(shù)據(jù)，研究光伏電池在小屋外表面的優(yōu)化鋪設(shè)問題，使發(fā)電總量盡可能大，而單位發(fā)電量的費(fèi)用盡可能小。計算機(jī)解決問題的方式例如：需求-對特定數(shù)據(jù)實(shí)現(xiàn)多種“特定”處理現(xiàn)狀-當(dāng)前不存在類似的程序或軟件方式：設(shè)計滿足用戶需求的程序或軟件“將來時態(tài)”程序設(shè)計（或軟件開發(fā)）計算機(jī)學(xué)科中的一個論斷尼克勞斯-沃思（瑞士計算機(jī)科學(xué)家）：Pascal語言之父1984年獲得圖靈獎，后回國任教。程序=算法+數(shù)據(jù)結(jié)構(gòu)4本節(jié)內(nèi)容定義特性描述方法算法設(shè)計方法特性5算法的定義Ⅰ算法:對特定問題求解方法和步驟的一種描述指令序列（程序）中文名稱：算術(shù)+方法；源于公元前1世紀(jì)《周髀算經(jīng)》，是我國最古老的天文學(xué)著作。介紹了勾股定理及其在測量上的應(yīng)用。英文名稱Algorithm[‘?lɡ?rie?m]算法:Analgorithmisaseriesofmathematicalsteps,especiallyinacomputerprogram,whichwillgiveyoutheanswertoaparticularkindofproblemorquestion.6算法的定義Ⅱ算法是否等于方法？7公認(rèn)的第一個算法-歐幾里德算法問題1：9和15的最大公約數(shù)？答案：3問題2：90和150的最大公約數(shù)？答案：30問題3：999和2555的最大公約數(shù)？答案：???問題4：正整數(shù)m和正整數(shù)n的最大公約數(shù)？答案：gcd(m,n)-greatestcommondivisor;輾轉(zhuǎn)相除法n→m，r→n，直到r=0，最大公因子為“當(dāng)前”的n。8算法“遞推”回憶：判斷兩臺計算機(jī)是否屬于同一子網(wǎng)？①

輸入IP1、SMask1和IP2、SMask2;②計算IP1+SMask1→x；③計算IP2+SMask2→y；④判斷x是否等于y:若相等輸出“是”，否則輸出“否”。①輸入m和n的值（m≥n）;②計算m除以n的余數(shù)并賦值給r；③判斷r是否為0:若為0則輸出n并結(jié)束；不為0繼續(xù)執(zhí)行；④n的值賦給m，r的值賦給n，跳轉(zhuǎn)到②步；⑤輸出n的值。9算法的特性及要求Ⅰ重要特性輸入（>=0項(xiàng)）輸出（>=1項(xiàng)）有窮性-有限步驟確定性-無歧義可行性-可分解、可實(shí)現(xiàn)10算法的特性及要求Ⅱ算法滿足的要求：正確性-不要“南轅北轍”可讀性-符合規(guī)范+注釋健壯性-易于處理“邊界值”高效性-速度快、資源少11算法的描述工具Ⅰ自然語言-“大白話”程序代碼-語言代碼偽代碼–自然語言+代碼程序流程圖-圖形描述過程12算法的描述工具-程序流程圖Ⅰ起止框輸入輸出框判斷框處理框流程線語句序列A語句序列B選擇結(jié)構(gòu)（分支結(jié)構(gòu)）順序結(jié)構(gòu)N語句序列B下一語句Y語句序列A條件N語句序列下一語句Y條件13算法的描述工具-程序流程圖Ⅱ循環(huán)結(jié)構(gòu)（當(dāng)型）循環(huán)結(jié)構(gòu)（直到型）N語句塊下一語句Y條件Y語句塊下一語句N條件14OPENPUSHCLOSENPUSHYIsitatoyNLEADN=N+1YPUSHIsitatoyN<=5YN“冰箱裝大象”問題程序流程圖15算法的設(shè)計方法Ⅰ迭代法迭代法（遞推法），利用問題本身所具有的一種遞推關(guān)系（規(guī)律）求解問題的一種方法。重復(fù)執(zhí)行一組指令，且每次通過變量的舊值推出新值。例如：①1累加到100：②斐波那契數(shù)列：自然語言描述：①變量s賦初值為0，i賦初值為1；②判讀i是否超過100，若是執(zhí)行⑤，否則執(zhí)行③③將i加到變量s中，即s=s+i；④i自增1，即i=i+1，跳轉(zhuǎn)到②⑤輸出s的值。偽代碼描述：①s=0，i=1；②dowhilei≤100 {s=s+ii=i+1}③輸出s的值。S=0,i=1Ns=s+i輸出sYi<=100i=i+1如何計算2+5+8+11…+98如何計算2-5+8-11…+98如何計算1×2×3×…×10i=2i=i+3i<10016算法的設(shè)計方法Ⅱ窮舉法根據(jù)問題中的部分約束條件列舉所有可能解的情況，通過一一驗(yàn)證,篩選符合要求的解。常用于解決“是否存在”或“有多少種可能”等類型的問題。盡可能優(yōu)化。例如：找出所有“水仙花數(shù)”（三位整數(shù)，各位數(shù)字的立方和等于該數(shù)），如153=13+53+33。作業(yè)：“百錢百雞”問題：“雞翁一值錢五，雞母一值錢三，雞雉三值錢一，百錢買百雞，各幾何？”17“水仙花數(shù)”流程圖i=100N計算百位數(shù)a、十位數(shù)b、個位數(shù)cYi<=999Ni=i+1Y輸出條件成立“百錢百雞”如何解決？18算法的設(shè)計方法Ⅲ遞歸法例如：①k的階乘:k!=k*(k-1)!(0!=1)②斐波那契數(shù)列:f(n)=f(n-1)+f(n-2)(n≧3)f(1)=1，f(2)=1作業(yè):查“漢諾塔”問題與宇宙壽命（5845億年）；查“國際象棋棋盤‘放麥子’”。一個直接或間接的調(diào)用自身的算法稱為遞歸算法。一個使用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。遞歸算法包括“遞推”（難到易）和“回歸”兩部