算法設(shè)計與分析第版王紅梅胡明習題答案

1、第1頁共41頁算法設(shè)計與分析算法設(shè)計與分析(第2版)王紅梅王紅梅胡明胡明習題習題答案答案習題習題11.圖論誕生于七橋問題。出生于瑞士的偉大數(shù)學家歐拉（圖論誕生于七橋問題。出生于瑞士的偉大數(shù)學家歐拉（LeonhardEuler，1707—1783）提出并解決了該問題。七橋問題是這樣）提出并解決了該問題。七橋問題是這樣描述的：一個人是否能在一次步行中穿越哥尼描述的：一個人是否能在一次步行中穿越哥尼斯堡（現(xiàn)在叫加里寧格勒，在波羅的海南岸）斯堡

2、（現(xiàn)在叫加里寧格勒，在波羅的海南岸）城中全部的七座橋后回到起點，且每座橋只經(jīng)城中全部的七座橋后回到起點，且每座橋只經(jīng)過一次，圖過一次，圖1.7是這條河以及河上的兩個島和是這條河以及河上的兩個島和七座橋的草圖。請將該問題的數(shù)據(jù)模型抽象出七座橋的草圖。請將該問題的數(shù)據(jù)模型抽象出來，并判斷此問題是否有解。來，并判斷此問題是否有解。七橋問題屬于一筆畫問題。輸入：一個起點輸出：相同的點1，一次步行2，經(jīng)過七座橋，且每次只經(jīng)歷過一次3，回到起點該問

3、題無解：能一筆畫的圖形只有兩類：一類是所有的點都是偶點。另一類是只有二個奇點的圖形。2在歐幾里德提出的歐幾里德算法中（即在歐幾里德提出的歐幾里德算法中（即最初的歐幾里德算法最初的歐幾里德算法）用的不是除法而是減）用的不是除法而是減法。請用偽代碼描述這個版本的歐幾里德算法法。請用偽代碼描述這個版本的歐幾里德算法1.r=mn2.循環(huán)直到r=02.1m=n2.2n=r2.3r=mn3輸出m3設(shè)計算法求數(shù)組中相差最小的兩個元素（稱為最接近數(shù)）的

4、差。要求分別給出偽代設(shè)計算法求數(shù)組中相差最小的兩個元素（稱為最接近數(shù)）的差。要求分別給出偽代碼和碼和C描述。描述。采用分治法對數(shù)組先進行快速排序在依次比較相鄰的差圖1.7七橋問題北區(qū)東區(qū)島區(qū)南區(qū)第3頁共41頁coutusingnamespacestdintmain()inta[]=1236490int_value=0將“既不是最大也不是最小的元素”的值賦值給它f(inti=0i!=4i)if(a[i1]a[i]cout_valueend