分治法解决邮局选址问题C
所属分类：数据结构
开发工具：C/C++
文件大小：290KB
下载次数：0
上传日期：2020-11-10 16:36:58
上 传 者：
tt096
说明： 基于分治算法的邮局选址问题，简单易懂，巩固学习
(The post office location problem based on divide and conquer algorithm is simple and easy to understand and consolidate learning)
文件列表:
分治法解决邮局选址问题 C++ (0, 2019-03-13)
分治法解决邮局选址问题 C++\Result.txt (603, 2018-10-12)
分治法解决邮局选址问题 C++\input_assign01_01.dat (115, 2018-10-05)
分治法解决邮局选址问题 C++\input_assign01_02.dat (9, 2018-10-05)
分治法解决邮局选址问题 C++\input_assign01_03.dat (19, 2018-10-05)
分治法解决邮局选址问题 C++\input_assign01_04.dat (33, 2018-10-05)
分治法解决邮局选址问题 C++\input_assign01_05.dat (40, 2018-10-05)
分治法解决邮局选址问题 C++\input_assign01_06.dat (51, 2018-10-05)
分治法解决邮局选址问题 C++\main.cpp (5230, 2018-10-06)
分治法解决邮局选址问题 C++\postoffice.exe (117760, 2018-10-06)
分治法解决邮局选址问题 C++\postoffice.ilk (693944, 2018-10-06)
分治法解决邮局选址问题 C++\postoffice.pdb (888832, 2018-10-06)
运行环境：win10 ***位+vs2017
.dat和.cpp和.exe都在一个文件夹中
运行过程说明：双击当前目录的下的可执行文件postoffice.exe，运行结束后可以在程序运行窗口或者Result.txt看到各个测试输入
文件的结果。
算法设计：先得到居民城市坐标和权值(x_value,y_value,weight)，再分别将城市横纵坐标序列各存储到结构体数组中，
然后利用分治法对其进行排序查找带权中位数：
（1）一开始,对整个数组找到一个枢轴位置，并且使小于枢轴值的元素在枢轴值左侧区间，
不小于枢轴值的元素在枢轴值右边。并计算左右两端的权值之和是否小于1/2（带权中位数定义），
如果满足则返回这个枢轴值；
（2）如果不满足则比较枢轴左右两区间权值之和的具体数值与其对应的最大值大小，
如果左边的权值之和大于其最大值，则说明带权中位数在枢轴左侧区间，反之，则在枢轴右侧区间；
（3）那么，就可以缩小范围只对左侧或者右侧区间递归地进行枢轴值查找，最终得到带权中位数；
（4）然后求得x和y坐标数组中的带权中位数mid_x和mix_y，即为所求的邮局位置；
数据结构设计：利用结构体存储某一维上的坐标和权值：
struct City//定义城市结构体
{
int coordinate;//某一维方向的城市坐标
double weight;//城市的权值
};
利用动态结构体数组去存储居民城市的横纵坐标以及对应的权值，这些数据来自输入数据文件。
其中输入数据文件输入数据格式为：第一行：居民城市个数n，第二行到第n行：居民城市x坐标 居民城市y坐标 居民城市对应权值
算法伪代码：
int main(){
for(int k=0;k
近期下载者：
相关文件：
收藏者：