圆上点集问题

无心人

有平面坐标系$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$，如何构造最小变换次数的变换序列

mathe

1，2变换均改变点的位置了？ 最后可能没有余下的点。 我们还是用复平面上单位圆描述更加方便。 如果开始只有点-1和1,显然通过一次变换1就没有点余下了。而且不管怎么变换，不可能出现只有一个点重合的情况。所以问题1不成立。

无心人

那修改下2，3的目标 剩余点的数目等于0

northwolves

1、是否对任何均有系列变换，使得最终只剩余一个点 31与360互素,答案是肯定的

mathe

0也不一定达得到。应该改成0或1，那就式比较显然能够达到了。

无心人

1总可以用旋转变换变换到0

mathe

也就是说，你的“旧”位置永远是第一个图中点的位置了？ 不过还是有歧异，被消除的点的“旧”位置是否包含在里面呢？题目的定义有一点不清楚。 当然条件都给定了，计算最小值应该可以通过动态规划去做

无心人

我重新定义下吧 圆上点集问题 有平面坐标系$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 编辑 ]

mathe

1变换使用两次总能够自己消去自己（是不是应该淘汰这种情况，不然就没什么意思了）