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

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

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