第6講軟件開發(fā)與軟件工程ppt課件.ppt

《第6講軟件開發(fā)與軟件工程ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第6講軟件開發(fā)與軟件工程1算法(3.3)2程序設(shè)計(jì)(3.3)3軟件工程(補(bǔ)充)開發(fā)計(jì)算機(jī)軟件的過(guò)程(1)確定并理解問(wèn)題(2)尋找解決問(wèn)題的方法與步驟，并將其表示成算法(algorithm)(3)程序設(shè)計(jì)：使用某種程序設(shè)計(jì)語(yǔ)言描述該算法及其處理的對(duì)象,并編譯成目標(biāo)程序(4)調(diào)試(debug)和運(yùn)行(run)程序，獲得問(wèn)題的解答(5)進(jìn)行評(píng)估,改進(jìn)算法和程序1.算法什么是算法？——算法是解決問(wèn)題的方法與步驟例：有三個(gè)硬幣，其中一個(gè)是偽造的，另兩個(gè)是真的，偽幣與真幣重量略有不同?，F(xiàn)在提供一座天平，如何找出偽幣呢？分析：按給定條件進(jìn)行操作明確而有序地進(jìn)行共享智能(任何人均可進(jìn)行)開始C是偽幣B是

2、偽幣A是偽幣A＝B？A＝C？是否否是ABC解決問(wèn)題必須找到算法！例1：買雞問(wèn)題公元5世紀(jì)末(南北朝)，我國(guó)古代數(shù)學(xué)家張丘建在他所撰寫的《算經(jīng)》中，提出了這樣的一個(gè)問(wèn)題：“雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問(wèn)雞翁、母、雛各幾何？”假設(shè):公雞數(shù)目為x，母雞數(shù)目為y，則小雞數(shù)目為(100-x-y)則：5x+3y+(100-x-y)/3=100，即7x+4y=100這是2元一次不定方程,共有有3組解：(4,18，78)、(8，11，81)、(12，4，84)用“枚舉法”解決買雞問(wèn)題開始NY5x+3y+z/3＝100？x+y＝100？x+y＝100？結(jié)束x=0,y=0x+

3、1x=0,y+1z=100-x-yNY輸出x,y,zNY假設(shè):公雞數(shù)目為x，母雞數(shù)目為y，則小雞數(shù)目z=100-x-y從x=0,y=0開始，反復(fù)檢查各種可能的組合是否所求答案：x=0,y=0、x=1,y=0······x=100,y=0x=0,y=1、x=1,y=1···x=99,y=1···x=0,y=99、x=1,y=99x=0,y=100直到找出全部答案為止！枚舉法也叫做“窮舉法”或Brute-force例2：貨郎擔(dān)問(wèn)題(TSP-TravelingSalesmanProblem)售貨員從城市A出發(fā)，到B、C、D等若干城市銷售貨物。已知各城市之間的距離，要求選擇一條旅行路線，使總路程最

4、短。條件：每個(gè)城市只能經(jīng)過(guò)一次，最后仍回到出發(fā)城市A。用枚舉法解決TSP問(wèn)題TSP問(wèn)題與組合爆炸4個(gè)城市，共有3！=6種路徑5個(gè)城市，共有4！=24種路徑10個(gè)城市，共有9！=36萬(wàn)種路徑50個(gè)城市，有49！=1062路徑……f(n)=(n－1)!2019年解決了15112個(gè)城市之間的TSP問(wèn)題，使用110臺(tái)計(jì)算機(jī)，共費(fèi)時(shí)2.5月（組合爆炸）理論上，枚舉法可以解決可計(jì)算領(lǐng)域的許多問(wèn)題實(shí)際上，枚舉法僅適用于解決一些較小規(guī)模的問(wèn)題33x23x2x1例3：尋找最大數(shù)（分治法）再分組：[49，38][65，97][76，13][27]49977627每一組找大數(shù)：歸并成1組[97，76]原始數(shù)據(jù)為

5、：49,38,65,97,76,13、27分成2組：[49，38，65，97][76，13，27][49，97][76，27]歸并成2組：9776每一組找大數(shù)：97找出最大數(shù)：分治法的基本思想例：找最大/最小數(shù)；合并排序；矩陣乘法；二分法搜索等把問(wèn)題分解為若干個(gè)規(guī)模較小的同一問(wèn)題原始問(wèn)題規(guī)模較小的子問(wèn)題問(wèn)題規(guī)模縮小之后很容易得到解答子問(wèn)題的解從子問(wèn)題的解可以很容易地推導(dǎo)出原始問(wèn)題的解原始問(wèn)題的解例4：迷宮問(wèn)題(回溯法、試探法)出口入口迷宮問(wèn)題將問(wèn)題的候選解按某種順序逐一檢驗(yàn)，在檢驗(yàn)過(guò)程中取消上一步或幾步、再尋找下一個(gè)可能候選解的過(guò)程叫做“回溯”DemoBacktracking例5：Hano

6、i塔問(wèn)題（遞歸法）設(shè)A,B,C是3個(gè)塔座，塔座A上有一疊由小到大疊在一起的n個(gè)圓盤，現(xiàn)要求將塔座A上的這一疊圓盤移到塔座C上，并仍按同樣順序疊置。移動(dòng)規(guī)則是：(1)每次只能移動(dòng)1個(gè)圓盤(2)不允許大盤壓在小盤上ABCCAB2個(gè)圓盤的情況abc0abc1abc2abc3一共需要搬動(dòng)3次！3個(gè)圓盤的情況abc0abc搬3次3abc4abc再搬3次7一共需要搬動(dòng)7次！4個(gè)圓盤的情況abc8ABC0abc7搬7次15CAB再搬7次一共需要搬動(dòng)15次！Hanoi塔問(wèn)題分析假定每秒移動(dòng)一次，一年有31536000秒，則需要花費(fèi)大約5849億年的時(shí)間假定計(jì)算機(jī)以1000萬(wàn)次/s的速度進(jìn)行傳送操作，則需要

7、大約58490年的時(shí)間若n=100，在運(yùn)算速度是1012/s（1萬(wàn)億次/秒），該算法需要運(yùn)行4x1010年，幾乎是宇宙年齡設(shè)圓盤數(shù)目為n，移動(dòng)次數(shù)為h(n),則h(n)=2h(n-1)+1=2(2h(n-2)+1)+1=22h(n-2)+2+1=23h(n-3)+22+2+1……=2nh(0)+2n-1+…+22+2+1=2n-1+…+22+2+1=2n-1當(dāng)n=64時(shí)，需要移動(dòng)盤子的次數(shù)為：264-1=18446744