上一篇
下一篇
Voronoi图！！
作者:Epic 日期:2008-11-19
这事还是跟不厚道的老陈有关。
话说上次去Matlab上机，任务就是一个简单的高斯消元。十五分钟搞定（matlab这个东西就是好，居然在二二十行内），然后向小陈交了上次他留给我们的问题——关于一个形如y=sin ax + cos bx（a，b不一定是正数）的方程的周期问题。于是就准备回去洗澡了。可是老陈显然不会允许我们这么做，于是他又布置了一道题，并且声称如果我们做出来了就会对我们刮目相看。题目是这样的：
请构造一个1-n的重排列，使得任意两个相邻数的和为质数。
于是我和LC就开始狂想这道题。先后联想到了网络流，二分图等多种模型，结果还真让我们搞出来了。方法是，先把n放在第一个，然后依次放上满足条件的最大的数。为什么是这样做呢，因为如果我们把1-n这些数抽象成n个点，然后如果两个数之和为素数，就连上一条边。那么就能得到一张图，问题就变成了在这个图上找一个哈密尔顿链。而哈密尔顿链有一个不一定正确的贪心方法，就是每次选择度最小的边。对于每个点i，他的边的个数取决于i-i+n-1之间的素数个数。素数的分布显然是越来越稀的，所以标号越大的点边越少。我们把n为1-100的情况都试了，然后1000，2000都试了，居然都能出解。
现在还留下一个问题，就是，可不可以证明这个贪心方法适用于所有情况呢？谁告诉我？
老陈当然也不知道，不过他只要答案。看到我们洋洋得意的样子，拿出了压箱底的杀手锏。
给定n，要求你安排这n个点在一个正方形中的位置，使得每个点在划分出的Voronoi图的对应多边形的重心上。
现在向全社会征解！他说这个程序他用matlab都编了70行。
话说上次去Matlab上机，任务就是一个简单的高斯消元。十五分钟搞定（matlab这个东西就是好，居然在二二十行内），然后向小陈交了上次他留给我们的问题——关于一个形如y=sin ax + cos bx（a，b不一定是正数）的方程的周期问题。于是就准备回去洗澡了。可是老陈显然不会允许我们这么做，于是他又布置了一道题，并且声称如果我们做出来了就会对我们刮目相看。题目是这样的：
请构造一个1-n的重排列，使得任意两个相邻数的和为质数。
于是我和LC就开始狂想这道题。先后联想到了网络流，二分图等多种模型，结果还真让我们搞出来了。方法是，先把n放在第一个，然后依次放上满足条件的最大的数。为什么是这样做呢，因为如果我们把1-n这些数抽象成n个点，然后如果两个数之和为素数，就连上一条边。那么就能得到一张图，问题就变成了在这个图上找一个哈密尔顿链。而哈密尔顿链有一个不一定正确的贪心方法，就是每次选择度最小的边。对于每个点i，他的边的个数取决于i-i+n-1之间的素数个数。素数的分布显然是越来越稀的，所以标号越大的点边越少。我们把n为1-100的情况都试了，然后1000，2000都试了，居然都能出解。
现在还留下一个问题，就是，可不可以证明这个贪心方法适用于所有情况呢？谁告诉我？
老陈当然也不知道，不过他只要答案。看到我们洋洋得意的样子，拿出了压箱底的杀手锏。
给定n，要求你安排这n个点在一个正方形中的位置，使得每个点在划分出的Voronoi图的对应多边形的重心上。
现在向全社会征解！他说这个程序他用matlab都编了70行。
文章来自: 
引用通告: 
Tags: 评论: 0 | 引用: 0 | 查看次数: 1189
发表评论