圆上点集问题
有平面坐标系$XY$，圆$R$，圆心在原点，半径$r$，从$(r, 0)$开始逆时针，每一度角度，在圆上有点位置$p_i$， $i=0, 1, 2, ..., 359$组成集合$P$现在考虑$P$任意子集$p$，有点数目$n$，从$(r, 0)$位置开始逆时针对点编号$0..n-1$,设定两个变换
1、以X或者Y轴进行镜像变换，如果有点和变换前点重合，则称为找到一个有效变换，去掉新旧两个位置点之一
2、以原点为中心点，进行逆时针旋转变换，变换度数为$31$倍数，如果有点和变换前点重合，则称为找到一个有效变换，去掉新旧两个位置点之一
现在问：
1、是否对任何$p$均有系列变换，使得最终只剩余一个点
2、如果有系列变换存在，是否对任何$n$均存在一个最大变换次数，求出这个次数
3、对任何$p$，如何构造最小变换次数的变换序列 1，2变换均改变点的位置了？
最后可能没有余下的点。
我们还是用复平面上单位圆描述更加方便。
如果开始只有点-1和1,显然通过一次变换1就没有点余下了。而且不管怎么变换，不可能出现只有一个点重合的情况。所以问题1不成立。 :)
那修改下2，3的目标
剩余点的数目等于0 1、是否对任何均有系列变换，使得最终只剩余一个点
31与360互素,答案是肯定的 0也不一定达得到。应该改成0或1，那就式比较显然能够达到了。 1总可以用旋转变换变换到0 也就是说，你的“旧”位置永远是第一个图中点的位置了？
不过还是有歧异，被消除的点的“旧”位置是否包含在里面呢？题目的定义有一点不清楚。
当然条件都给定了，计算最小值应该可以通过动态规划去做 :)
我重新定义下吧
圆上点集问题
有平面坐标系$XY$，圆$R$，圆心在原点，半径$r$，从$(r,0)$开始逆时针，每一度角度，在圆上有点位置$p_i$， $i=0,1,2,...,359$组成集合$P$
现在考虑$P$任意子集$p$，有点数目$n$，从$(r,0)$位置开始逆时针对点编号$0..n-1$,设定两个变换
1、以X或者Y轴进行镜像变换，如果有点和变换前某点重合，则称为找到一个有效变换，在集合中去掉这两个位置点
2、以原点为中心点，进行逆时针旋转变换，变换度数为$31$倍数，如果有点和变换前某点重合，则称为找到一个有效变换，在集合中去掉这两个位置点
现在问：
1、是否对任何$p$均有系列变换，使得最终剩余位置点数小于等于1
2、如果有系列变换满足1，是否对任何n均存在一个最大变换次数，求出这个次数
3、对任何p，如何构造最小变换次数的变换序列，满足1
[ 本帖最后由 无心人 于 2008-5-10 18:48 编辑 ] 还需要明确点的自身消去问题
这个应该只存在于旋转变换里
即如果旋转变换度数不为0，且使得点和自身位置重合称为自变换，消去该点
==========================================================
为了增加难度，禁止这种情况
[ 本帖最后由 无心人 于 2008-5-10 18:49 编辑 ] 1变换使用两次总能够自己消去自己（是不是应该淘汰这种情况，不然就没什么意思了）
页:
[1]
2