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

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

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

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

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