資源描述：
《搜索深度優(yōu)先剪枝ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、教學(xué)目標深度優(yōu)先搜索的一般步驟如何剪枝如何編程內(nèi)容要點復(fù)雜問題如何切入化簡思維深度優(yōu)先搜索的一般步驟寫好遞歸程序1任務(wù)：登山人選問題攀登一座高山，假定勻速前進，從山腳登到山頂需走N天，下山也需N天。山上沒有水和食品，給養(yǎng)要靠登山隊員攜帶，而每個隊員所攜帶的給養(yǎng)量要少于他登頂再返回山腳所消耗的給養(yǎng)量。因此，一定要組成一個登山隊，在多人支援的情況下，保證有一個人登頂?，F(xiàn)在登山俱樂部有P個人待選，我們將P個人依次編號為k=1,2,…,P，令E[k]表示編號為k的人每日消耗的給養(yǎng)量，M[k]表示編號為k的人最多
2、可攜帶的給養(yǎng)量。登山計劃要求所組成的登山隊所有成員同時出發(fā)，其中一些人分別在啟程若干天后返回，最終保證出發(fā)N天后至少有一人登頂，出發(fā)2N天后所有人都已返回山腳，無人滯留山上。2編程要求：用鍵盤輸入天數(shù)N（N<10）、俱樂部人數(shù)P（P<10）之后，依次輸入E[k]和M[k]，k=1,2,…,P，分別輸出兩個登山組隊計劃，計劃1，要求參加登山的人數(shù)最少，在滿足這一條件之下消耗的總給養(yǎng)量最少。計劃2，要求消耗的總給養(yǎng)量最少。輸出的內(nèi)容是：有多少隊員參加登山，消耗的總給養(yǎng)量，在出發(fā)時每人分別攜帶多少給養(yǎng)，每人分
3、別在出發(fā)幾天后返回（幾天后開始下山）。題目數(shù)據(jù)保證有解?！据斎敫袷健康?行為2個小于10的整數(shù)N和P,兩個整數(shù)之間有一個空格。第2行為P個整數(shù)，分別是E[1],E[2],…,E[P],相鄰兩整數(shù)之間有一個空格。第3行為P個整數(shù)，分別是M[1],M[2],…,M[P],相鄰兩整數(shù)之間有一個空格。3【輸出格式】第1行到第3行為計劃1的內(nèi)容，第1行有兩個整數(shù)，前者是參加登山人數(shù)Q1，后者是消耗的總給養(yǎng)量。第2行是Q1個整數(shù)，表示Q1個人在出發(fā)時每人攜帶的給養(yǎng)。第3行是Q1個整數(shù)，表示Q1個人中的每個人在出發(fā)幾
4、天后返回。第4行到第6行為計劃2的內(nèi)容，第4行有兩個整數(shù)，前者是參加登山人數(shù)Q2，后者是消耗的總給養(yǎng)量。第5行是Q2個整數(shù)，表示Q2個人在出發(fā)時每人攜帶的給養(yǎng)。第6行是Q2個整數(shù)，表示Q2個人中的每個人在出發(fā)幾天后返回。4【輸入樣例】661222337817182225【輸出樣例】24218246333818173631輸出表明：計劃1中有2個人組隊，分別攜帶18和24的給養(yǎng)量，分別在出發(fā)6天和3天之后返回；計劃2中有3個人組隊，分別攜帶18、17和3的給養(yǎng)量，分別在出發(fā)后6天、3天和1天之后返回。5《
5、登山人選》解題思路當(dāng)我們遇到一道難題時，先要想到：一、可不可以先從一個較簡單的情況分析起，把難度先降低一些，等從中總結(jié)出規(guī)律性的認識后，再回到原題的要求上來；二、能不能先從一個特殊的例子分析起，再推廣到一般情況。為了簡化問題，理出思路，可先將問題化簡為：每人所能攜帶的給養(yǎng)量相同，且每人每天消耗的給養(yǎng)量也相同，選擇一座不高的山，用一組人數(shù)不多的具體數(shù)據(jù)。比如有如下一組數(shù)據(jù)：N=4從山腳到山頂需4天路程P=6登山俱樂部成員人數(shù)E=1每人每天消耗的給養(yǎng)量M=5每人最多攜帶的給養(yǎng)量6為了便于分析，圖1畫出了用上
6、述數(shù)據(jù)組隊登山的思路圖。4下返回高度11山3321222231323311上41424344山001號隊員2號隊員3號隊員4號隊員71#2#3#的支援點h1#2#的支援點1#的支援點432211430012345678t4人登山的高度與時間圖8在圖中，山高是以（路程）天為單位的。山頂?shù)母叨仁?天的路程。在1號隊員上下山的示意圖中，每個方塊代表一天的路程，1號隊員被選中為登頂者，用4天路程上山，再用4天路程下山。如果完全自食其力的話，1號隊員需要自帶8天的給養(yǎng)，而題目限定的每人最多攜帶給養(yǎng)量M=5。因此，
7、沒有同伴支援的話，1號隊員是無法登頂?shù)?。?號登頂后能安全下山考慮，下山只有他一個人，只能自己攜帶給養(yǎng)。因此，在做計劃時讓1號隊員上山時，從山腳（高度0）到高度3使用同伴的給養(yǎng)。過了高度3之后再吃自帶的給養(yǎng)。在圖中小方塊內(nèi)所填的數(shù)字，表示在這一天的路程中由該號隊員供應(yīng)給養(yǎng)。從圖可見1號隊員上山的第一天（從高度0至高度1）由4號隊員提供給養(yǎng)；上山的第2天（從高度1至高度2）由3號隊員提供給養(yǎng)；上山的第3天（從高度2至高度3）由2號隊員提供給養(yǎng)；上山的第4天（從高度3至高度4）吃自己的給養(yǎng)；登頂成功之后，下
8、山的4天也均自食其力。從1號隊員登頂?shù)倪^程需要2號隊員支援的情況看，1號隊員需要在第3天吃2號隊員攜帶的給養(yǎng)，這就意味著2號隊員要跟1號一起爬到高度3之后才能下山。9因此，2號隊員上山走3天，再下山走3天，自己要消耗6天的給養(yǎng)，可是自己只能攜帶5天的給養(yǎng)，當(dāng)然還需要3號支援他。可以這樣計劃：2號隊員上山時，第1天由4號隊員供給；第2天由3號隊員供給；第3天將1份給養(yǎng)支援給1號隊員，自己用掉1份給養(yǎng)。到了高度3之后，用還剩下的3份給養(yǎng)安全下山
