設計進度安排
1、分析居民區光纖網路的資料屬性，并依據光纖鋪設的功能要求，確定演算法設計方案；
2、完成網路光纖鋪設的資料結構設計作業，包括圖檔案的結構與存盤結構、最小生成樹的存盤結構、圖形的顯示結構等；
3、完成功能設計作業，包括隨機生成代價檔案、讀圖檔案、計算最小生成樹、顯示最小生成樹等；
4、使用C或C++程式設計語言撰寫實作演算法程式；
5、完成大作業報告，
設計內容
認真參閱課程相關參考資料、資料，了解鋪設網路光纖的原理要求，設計一個實作居民小區之間網路光纖鋪設的最佳方案選擇的演算法，具體內容如下：
需要在某個城市n個居民小區之間鋪設網路光纖，假設任意兩個居民小區之間均需要鋪設光纖，則在這n個居民小區之間只需要鋪設n-1條光纖即可形成一個網路，但由于地理環境不同，所需要的代價也不盡相同，本課程設計要求事先隨機生成任意居民小區之間鋪設網路光纖的代價，并將代價存入檔案，然后設計一個最佳方案進行光纖鋪設，使得既能連通所有小區之間的網路，又能使網路光纖鋪設的代價最小，最終以圖形形式輸出所設計的最佳方案，
需求分析
1.光纖網路設計
在某個城市n個居民小區之間鋪設網路光纖，設計一個最佳方案進行光纖鋪設，使得既能連通所有小區之間的網路，又能使網路光纖鋪設的代價最小，
2.功能要求
輸入居民區的個數，光纖的條數，光纖的單價，以及各個居民區之間的距離，運用克魯斯卡爾演算法，輸出系統最優的鋪設方案，
代碼具體
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
cout<<"居民小區光纖路線鋪設最優方案設計 "<<endl;
int neighborhoodNum, opticalNum; // 居民區個數, 光纖線路條數
int neighborhood1, neighborhood2; //兩個居民區
double price; //光纖線路單位長度價格
double distance, shortest_distance=0; //最短總路線長度
int neighborhoodArrary[100][100]; //鄰接矩陣
int i, j;
cout<<"請輸入居民區個數: ";
cin>>neighborhoodNum;
cout<<"請輸入光纖線路條數: ";
cin>>opticalNum;
cout<<"請輸入光纖線路單位長度價格 : ";
cin>>price;
cout<<endl;
for(i=0; i<neighborhoodNum; i++)
for(j=0; j<neighborhoodNum; j++)
{
neighborhoodArrary[i][j]=9999;
}
cout<<"請輸入各光纖線路的兩居民區及距離："<<endl;
j=1; //j 表示第 n 條線路
for(i=0; i<opticalNum; i++)
{
cout<<"請輸入第 "<<j<<" 條光纖線路的兩居民區及距離: "; //存盤兩居民區及距離
cin>>neighborhood1>>neighborhood2>>distance;
neighborhoodArrary[neighborhood1][neighborhood2]=distance;
neighborhoodArrary[neighborhood2][neighborhood1]=distance;
j++;
}
int short_way[100];
int near_neighborhood[100];
int min_way;
int temp_neighborhood;
for(i=1; i<neighborhoodNum; i++)
{
short_way[i]=neighborhoodArrary[0][i];
near_neighborhood[i]=0;
}
short_way[i]=0;
near_neighborhood[i]=0;
cout<<"居民小區光纖路線鋪設最優方案設計如下: \n";
for(i=1; i<neighborhoodNum; i++)
{
min_way=9999; j=1; temp_neighborhood=1;
while(j<neighborhoodNum)
{
if(short_way[j]!=0 && short_way[j]<min_way)
{
min_way=short_way[j];
temp_neighborhood=j;
}
j++;
}
cout<<" 居民區 "<<near_neighborhood[temp_neighborhood]<<"----("<<min_way<<"米) ----居民區"<<temp_neighborhood<<endl;
short_way[temp_neighborhood]=0;
shortest_distance+=min_way;
for(j=0; j<neighborhoodNum; j++)
if(neighborhoodArrary[temp_neighborhood][j]<short_way[j])
{
short_way[j]=neighborhoodArrary[temp_neighborhood][j];
near_neighborhood[j]=temp_neighborhood;
}
}
cout<<"最短總長度為: "<<shortest_distance<<"米"<<endl;
cout<<"最低總造價為: "<<shortest_distance*price<<"元"<<endl<<endl;
char choice;
cout<<"清空資料, 重新輸入? T or F : "; cin>>choice;
if(choice=='T' )
{
system("cls") ; //清空螢屏, 重新開始
}
if(choice=='F' )
{
cout<<"成功退出!";
exit(0) ; //退出程式 }
}
}
代碼運行結果：
總結：
運用最小生成樹，點表示居民區，路徑表示光纖線路，運用克魯斯卡爾演算法，使既能連通所有小區之間的網路，又能使網路光纖鋪設的代價最小，考慮iostream庫輸入輸出流便捷，采用C++代碼，思考設計程序中遇到演算法選擇的困難，最后考慮時間復雜度和空間復雜度選擇克魯斯卡爾演算法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499071.html
標籤：其他
下一篇：Hash 哈希表和演算法思路詳解