【100分】构造多边形解决办法

【100分】构造多边形
有这样一种多边形，从坐标原点开始，向北前进一个单位，
然后再转左或者转右，再前进两个单位，然后再转左或者转右，再前进三个单位，
一直下去，最后再前进n个单位，刚好回到原点形成一个n边形。
现在，告诉你n，你能构造出这样的多边形吗？

给定的N<=1000,用DP都会超时。

考虑把东西，南北方向的边长写成2个数列：
南北：1，3，5，7...
东西：2，4，6，8...
看上去题目似乎能转变为给2个序列加上+，-号，使2个序列和都为0，但没有经过严格推导，不能断定。


能否有其他的思路找出该多边形的规律？



[解决办法]
"看上去题目似乎能转变为给2个序列加上+，-号，使2个序列和都为0" 

这就足够构造了吧
[解决办法]
似乎是个随机过程问题
[解决办法]
简单试了一下，这个数太大了，这样来算DP效率太低，还是从整数划分来找吧！
[解决办法]
楼主好有想法。托楼主的开导，此方法已经是非常好了。

南北是以3为差的。
南北：1，4，7，10...
东西：2，4，6，8...

然后分n为奇数(2k+1） 
n为偶数（2k）

再推出两方程。

脑袋转不过来了，改天再想。

探讨

有这样一种多边形，从坐标原点开始，向北前进一个单位，
然后再转左或者转右，再前进两个单位，然后再转左或者转右，再前进三个单位，
一直下去，最后再前进n个单位，刚好回到原点形成一个n边形。
现在，告诉你n，你能构造出这样的多边形吗？

给定的N<=1000,用DP都会超时。

考虑把东西，南北方向的边长写成2个数列：
南北：1，3，5，7...
东西：2，4，6，8...
看上去……

[解决办法]
LZ的意思是要构造出一种吧，而不是求出所有的解，否则那是一个天文数字，估算了一下，n=1000时解超过了2^250。当n为4k或者4k+3型数时才有可能有解。并且对n=4k(k>=2)，n=4k+3(k>=7）一定有解，较小的n楼主可以自己验证下。
[解决办法]
用数学归纳法，先实验10个点之内的找出规律，再证明n和n+1的情况都符合。
[解决办法]
如果只是构造一种的话，那就简单多了，首先奇数的个数必须是偶数个才可以，可以用DP求一个1000以内的所有解，然后用贪心，让待选数的和降到1000以内就可以了。

偶数列可以先除以来2构造，只要用DP求500以内的解就可以了。
[解决办法]
不好意思，n=4k，n=4k+3型数时没那么简单，还要对k的奇偶性继续分下去讨论一次。只有当n为8k,8k+7型数时才有解。
[解决办法]
以我的理解，它说是N边形，也就是说没有线是交叉的！

由此可以推想到:

所有纵座标y和 = 0;
所有横座标x和 = 0;

不知道这样说，正确没有????
[解决办法]

探讨

以我的理解，它说是N边形，也就是说没有线是交叉的！

由此可以推想到:

所有纵座标y和 = 0;
所有横座标x和 = 0;

不知道这样说，正确没有????

[解决办法]
#include <stdio.h>
int a[10000];
int b[10000];
void main()
{
int n;int i,j;
for (n=8;n<=70;n+=8)
{
for (i=1;i<=n/2;i++)
{
if (i<=n/8||i>(n/2-n/8))

a[i]=2;

else a[i]=4;
}
for (j=1;j<=n/2;j++)
{
if (j<=n/8||j>(n/2-n/8))

b[j]=1;

else b[j]=3;
}
printf("\n构造%d条边的多边形：\n",n);
for (i=1;i<=n;i++)
{ 
if(i%2!=0)
{ 
if (a[(i+1)/2]==1)
printf("第%d步向上走\n",i);
if (a[(i+1)/2]==2)
printf("第%d步向右走\n",i);
if (a[(i+1)/2]==3)
printf("第%d步向下走\n",i);
if (a[(i+1)/2]==4)
printf("第%d步向左走\n",i);
}
else
{ if (b[i/2]==1)
printf("第%d步向上走\n",i);
if (b[i/2]==2)
printf("第%d步向右走\n",i);
if (b[i/2]==3)
printf("第%d步向下走\n",i);
if (b[i/2]==4)
printf("第%d步向左走\n",i);
}
}

}
}
必须是8的倍数

就是首位的数字同向
比如1 3 5 7
1与7同向
3与5和两端的反向
也就是寄序列和偶序列中间的数字与两端的反向
否则会出现回旋交叉
[解决办法]
对于8m,按顺序平均分成4组，开始和结尾两组正号，中间两组符负号，可以构成不自相交的结果。
对于8m-1,在前面添加一个偶数0后同上面划分即可。

而对于n是其它情况，显然无解

查看更多 下一篇