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

1、習(xí)題習(xí)題11.圖論誕生于七橋問(wèn)題。出生于瑞士的偉大數(shù)學(xué)家歐拉（圖論誕生于七橋問(wèn)題。出生于瑞士的偉大數(shù)學(xué)家歐拉（LeonhardEuler，1707—1783）提出并解決了該問(wèn)題。七橋問(wèn)題是這樣）提出并解決了該問(wèn)題。七橋問(wèn)題是這樣描述的：一個(gè)人是否能在一次步行中穿越哥尼描述的：一個(gè)人是否能在一次步行中穿越哥尼斯堡（現(xiàn)在叫加里寧格勒，在波羅的海南岸）斯堡（現(xiàn)在叫加里寧格勒，在波羅的海南岸）城中全部的七座橋后回到起點(diǎn)，且每座橋只經(jīng)城中全部的七

2、座橋后回到起點(diǎn)，且每座橋只經(jīng)過(guò)一次，圖過(guò)一次，圖1.7是這條河以及河上的兩個(gè)島和是這條河以及河上的兩個(gè)島和七座橋的草圖。請(qǐng)將該問(wèn)題的數(shù)據(jù)模型抽象出七座橋的草圖。請(qǐng)將該問(wèn)題的數(shù)據(jù)模型抽象出來(lái)，并判斷此問(wèn)題是否有解。來(lái)，并判斷此問(wèn)題是否有解。七橋問(wèn)題屬于一筆畫問(wèn)題。輸入：一個(gè)起點(diǎn)輸出：相同的點(diǎn)1，一次步行2，經(jīng)過(guò)七座橋，且每次只經(jīng)歷過(guò)一次3，回到起點(diǎn)該問(wèn)題無(wú)解：能一筆畫的圖形只有兩類：一類是所有的點(diǎn)都是偶點(diǎn)。另一類是只有二個(gè)奇點(diǎn)的圖形。2在

3、歐幾里德提出的歐幾里德算法中（即在歐幾里德提出的歐幾里德算法中（即最初的歐幾里德算法最初的歐幾里德算法）用的不是除法而是減）用的不是除法而是減法。請(qǐng)用偽代碼描述這個(gè)版本的歐幾里德算法法。請(qǐng)用偽代碼描述這個(gè)版本的歐幾里德算法1.r=mn2.循環(huán)直到r=02.1m=n2.2n=r2.3r=mn3輸出m3設(shè)計(jì)算法求數(shù)組中相差最小的兩個(gè)元素（稱為最接近數(shù)）的差。要求分別給出偽代設(shè)計(jì)算法求數(shù)組中相差最小的兩個(gè)元素（稱為最接近數(shù)）的差。要求分別給出

4、偽代碼和碼和C描述。描述。采用分治法對(duì)數(shù)組先進(jìn)行快速排序在依次比較相鄰的差#includeusingnamespacestdintpartions(intb[]intlowinthigh)圖1.7七橋問(wèn)題北區(qū)東區(qū)島區(qū)南區(qū)if((a[i1]a[i])usingnamespacestdintmain()inta[]=1236490int_value=0將“既不是最大也不是最小的元素”的值賦值給它f(inti=0i!=4i)if(a[i1]a