分治法算法分析与设计实验二
主要内容
•
•
•
•
•实验目的主要实验仪器设备和环境实验内容实验要求注意点
实验目的
•理解分治法的基本思想
•针对特定问题，可以设计出分治算法进行求解
主要实验仪器设备和环境
•每位学生一台计算机
•计算机的操作系统为
–windows 2000或Windows XP
•工具软件
–C++ IDE，JAVA IDE
实验内容二最近点对问题•问题描述
–对于平面上给定的N个点，给出所有点对的最短距离
–即，输入是平面上的N个点，输出是N点中具有最短距离的两点
•现要求随机生成N个点的平面坐标，应用穷举法编程计算出所有点对的最短距离
•现要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离
实验要求
•编程语言可以用C,C++或者JAVA，关键步骤必须有注释
•实验报告必须包含以下内容：算法设计的基本思路、程序清单以及针对测试数据的运行结果•实验报告电子版请发至[email protected]，Email标题：“学号姓名算法实验二最近点对”，附件请不要压缩，实验报告名：“学号姓名算法实验二最近点对”
注意点
•随机数的生成问题
•求解最近点对问题时的分治策略
•分解后子问题的解如何合并
编码提示
•随机数生成
–srand(time(0));//设置随机数种子
•要#include
–rand();//生成[0,MAX)之间的随机整数
•要#include
–for(inti=0;i
{
ran_num=rand() % 10;
cout
}//生成不大于10的随机整数
编码提示
•最近点对问题的分治策略
–S:平面上的二维点集合
–预处理：分别根据点的x轴和y轴坐标进行排序，得到X和Y,很显然此时X和Y中的点就是S中的点
编码提示
•Conquer
–两个递归调用，分别求出
和drSL和SR中的最短距离为dl
编码提示
•Combine–对于Y’L中的每一点，检查Y’R中的点与它的距离，
更新所获得的最近距离
分治法算法分析与设计实验二
主要内容
•
•
•
•
•实验目的主要实验仪器设备和环境实验内容实验要求注意点
实验目的
•理解分治法的基本思想
•针对特定问题，可以设计出分治算法进行求解
主要实验仪器设备和环境
•每位学生一台计算机
•计算机的操作系统为
–windows 2000或Windows XP
•工具软件
–C++ IDE，JAVA IDE
实验内容二最近点对问题•问题描述
–对于平面上给定的N个点，给出所有点对的最短距离
–即，输入是平面上的N个点，输出是N点中具有最短距离的两点
•现要求随机生成N个点的平面坐标，应用穷举法编程计算出所有点对的最短距离
•现要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离
实验要求
•编程语言可以用C,C++或者JAVA，关键步骤必须有注释
•实验报告必须包含以下内容：算法设计的基本思路、程序清单以及针对测试数据的运行结果•实验报告电子版请发至[email protected]，Email标题：“学号姓名算法实验二最近点对”，附件请不要压缩，实验报告名：“学号姓名算法实验二最近点对”
注意点
•随机数的生成问题
•求解最近点对问题时的分治策略
•分解后子问题的解如何合并
编码提示
•随机数生成
–srand(time(0));//设置随机数种子
•要#include
–rand();//生成[0,MAX)之间的随机整数
•要#include
–for(inti=0;i
{
ran_num=rand() % 10;
cout
}//生成不大于10的随机整数
编码提示
•最近点对问题的分治策略
–S:平面上的二维点集合
–预处理：分别根据点的x轴和y轴坐标进行排序，得到X和Y,很显然此时X和Y中的点就是S中的点
编码提示
•Conquer
–两个递归调用，分别求出
和drSL和SR中的最短距离为dl
编码提示
•Combine–对于Y’L中的每一点，检查Y’R中的点与它的距离，
更新所获得的最近距离