演算法與資料結構課程設計報告

演算法與資料結構

課程設計實驗報告書

課程設計名稱：最小套圈設計

學生姓名：張延雲

學號：201058501314

學院：計算機學院

班級：計101-3班

日期：2023年7月13日

一、問題分析和任務定義

1、問題分析

本設計的要求是設計乙個最小套圈。

規則是：遊戲者將手中的圓環套圈投向場中的玩具，**中的玩具就作為獎品獎給遊戲者。

給定乙個套圈遊戲場中的布局，固定每個玩具的位置，請你設計乙個圓環套圈的半徑尺寸，使得它每次最多只能套中乙個玩具，但同時為了讓遊戲看起來更具有吸引力，這個套圈的半徑又需要盡可能大。

為使問題進一步簡單化，假設每個玩具都是平面上乙個沒有面積的點，套圈是簡單的圓，乙個玩具**住，是指這個點到圓心的距離嚴格小於圓的半徑。如果有兩個玩具被放在同乙個位置，那麼輸出的圓半徑就是0.

2、任務定義

（1）定義乙個點的結構體wanju來存放點的橫縱座標，表示乙個玩具的空間位置，同時採用wanju這種結構體陣列來存放不同的玩具；

（2）求最小套圈設計問題歸結為先輸入每個玩具的空間位置，然後求他們任意兩點之間的最小距離，然後取最小距離的一半即為套圈半徑，判斷是否有兩個或兩個以上的玩具放在同一點，若有，那麼套圈的半徑就為0；

（3）求最小距離的方法採用「分而治之」，將所有的點按它的x座標排序，從中間將場地一分為二，然後遞迴的解決兩邊場地的子問題，分別得到兩個字問題的最小半徑d左和d右，，將其記為d，然後看它和剛剛求的那個最小距離哪個更小，最小的那個的一半即為最小套圈半徑；

（4）定義兩個陣列分別來存放玩具和最小距離，實現對多組測試資料的輸入和測試結果的存放和輸出。

二、資料結構的選擇和概要設計

1、玩具的儲存結構

將玩具抽象成空間乙個沒有面積的點，其數學模型如下圖所示：

a11 a12 ┅ a1n

a21 a22 ┅ a2n

am×n1≤x≤m，1≤y≤n)

aij ┇

am1 am2 ┅ amn

因此可以用空間座標x和y來表示，在本程式中我採用了陣列這種儲存結構，包含橫縱座標的結構體型別wanju;

資料型別描述如下：

typedef struct wanju;

2、建立放置玩具思想的演算法

（1）宣告wanju型別的結構體，根據提示資訊輸入玩具的個數，根據輸入的玩具個數將每個點的橫縱座標輸入，然後依次存放在陣列之中；

（2）如果輸入的玩具個數大於程式剛開始自定義的maxwanjus或小於0輸出錯誤的提示資訊；

（3）當輸入的玩具個數為0時結束輸入測試組；

3、將所有的點按x座標排序；

為了提高求最短距離的效率，將所有的點先按x座標排序，本程式中排序採用的是系統的庫函式qsort，採用該演算法能夠提高演算法的效率；演算法思想：在compx()函式為將兩個點的橫座標減橫座標，如果大於0，返回1則發生交換，如果等於0或小於0則不發生交換，在qsort函式中第乙個引數為陣列名，第二個為陣列中元素的個數，第三個為每個陣列元素

所佔的位元組大小，最後乙個為呼叫的表示式比較的交換函式compx；

int compx(const void *a, const void *b實現按x排序

return ((wanju*)a)->x-(( wanju*)b)->x;

}int compy(const void* a, const void* b實現按y排序

return ((wanju *)a)->y-(( wanju *)b)->y;

} qsort(wanjus, numwanjus, sizeof(point), compx將陣列按x排序；

qsort(wanjus, numwanjus /2, sizeof(point), compy將陣列按y排序；

qsort(wanjus + numwanjus /2, numwanjus - numwanjus /2, sizeof(point), compy);

4、計算套圈的半徑的演算法思想

首先建立乙個放置玩具的平面（每個玩具都是平面上乙個沒有面積的點），其次判斷是否有放在同一位置的玩具，再次計算套圈的半徑。

（1）建立放置玩具平面的演算法思想

該演算法的實現是定義乙個含有橫縱座標x和y的結構體，其次定義乙個含有ｘ和ｙ的結構體陣列wanju，具體操作於下：

（ⅰ）當程式提示，輸入玩具數目時，就讀入玩具的個數t （正整數），若輸入小於０或大於自定義最大的那個maxwanjus，輸出輸入錯誤的提示資訊。

（ⅱ）輸入正確則依次輸入各個點的橫縱座標。接下來又出現「輸入玩具個數」的提示資訊，當還想輸入一組測試陣列，按上述繼續輸入，當輸入為０，則結束輸入了。

（2）定義子函式float juli(wanju a, wanju b)求空間任意兩點間的距離，呼叫系統的庫函式sqrt求兩點間的距離；

演算法描述如下：

float juli(wanju a, wanju b)

return (float)sqrt((

（3）為了提高求最短距離的效率，將所有的點先按x座標排序，本程式中排序採用的是系統的庫函式qsort，採用該演算法能夠提高演算法的效率；演算法思想：在compx()函式為將兩個點的橫座標減橫座標，如果大於0，返回1則發生交換，如果等於0或小於0則不發生交換，在qsort函式中第乙個引數為陣列名，第二個為陣列中元素的個數，第三個為每個陣列元素所佔的位元組大小，最後乙個為呼叫的表式比較的交換函式compx；

（4）定義乙個子函式float shotjuli(wanju* wanjus, int n)求空間中點之間哪兩點距離最短，求出它們間的距離；其中n表示玩具的個數；wanjus表示陣列名；如果n等於1，返回0；n等於2，呼叫juli函式求它們之間的距離；n等於3，呼叫juli函式求出第乙個點與第二個點之間的距離；呼叫juli函式求出第二個點與第三個點之間的距離；呼叫juli函式求出第乙個點與第三個點之間的距離；利用雙目運算<？：求出三點間距離最短的兩點間的距離；當n大於3，利用遞迴將場地分成左右兩半，然後對左右兩部分分別呼叫shotjuli函式；比較剛剛求出的左右兩邊的最短距離，將其中較小的那個賦值給變數d，同時將d賦值給shotjuli..綜合中間地帶，通過掃瞄左右子集中與其距離在d之內的所有點，已完成合併求最短距離。

然後取中間地帶的距離temp與shotjuli中較小的距離，並將它最為引數返回；

（5）如何輸出多組測試資料的套圈的最小半徑

定義乙個陣列result來存放最小半徑，並且賦初始值為-1（因為套圈半徑不可能為負數），將求的最小套圈半徑存在result中，當result[i]！=-1時，輸出所有的測試結果；

5、結構圖

三、詳細設計和編碼

１、建立放置玩具平面的演算法思想

typedef struct//定義玩具座標點的結構體

wanju;

while(1)

for(i=0;i

2、求空間任意兩點間的距離

float juli(wanju a,wanju b)//求兩個玩具之間的距離，在shotjuli函式中呼叫

3、將場地排序的演算法

int compx(const void *a,const void *b)//實現按x排序

int compy(const void *a,const void *b)//實現按y排序

qsort(wanjus,numwanjus,sizeof(wanju),compx);//呼叫compx函式qsort(wanjus,numwanjus/2,sizeof(wanju),compy);

演算法與資料結構課程設計報告

資料結構與演算法課程設計

資料結構課程設計報告

資料結構課程設計報告

相關推薦