Algorithm 版 (精华区)
发信人: zjliu (fly), 信区: Algorithm
标 题: 求任意简单多边形的面积
发信站: 哈工大紫丁香 (Sun Jul 7 14:52:02 2002) , 转信
发信人: TurboZV (又是一年大四), 信区: Algorithm
标 题: [Zz]怎样求任意简单多边形的面积
发信站: 一网深情 (2002年06月30日02:48:44 星期天), 站内信件
发信人: starfish (LaTeX~~), 信区: Algorithm
标 题: Re: 怎样求任意简单多边形的面积
发信站: 南京大学小百合站 (Tue May 21 12:36:43 2002)
直接用公式计算
// 要求按照逆时针方向输入多边形顶点
// 可以是凸多边形或凹多边形
float area_of_polygon(int vcount,float x[],float y[])
{
int i;
float s;
if (vcount<3) return 0;
s=y[0]*(x[vcount-1]-x[1]);
for (i=1;i<vcount;i++)
s+=y[i]*(x[(i-1)]-x[(i+1)%vcount]);
return s/2;
}
标 题: [Zz]怎样求任意简单多边形的面积
发信站: 一网深情 (2002年06月30日02:48:44 星期天), 站内信件
发信人: starfish (LaTeX~~), 信区: Algorithm
标 题: Re: 怎样求任意简单多边形的面积
发信站: 南京大学小百合站 (Tue May 21 12:36:43 2002)
直接用公式计算
// 要求按照逆时针方向输入多边形顶点
// 可以是凸多边形或凹多边形
float area_of_polygon(int vcount,float x[],float y[])
{
int i;
float s;
if (vcount<3) return 0;
s=y[0]*(x[vcount-1]-x[1]);
for (i=1;i<vcount;i++)
s+=y[i]*(x[(i-1)]-x[(i+1)%vcount]);
return s/2;
}
(1-2x)H(x) = x+x^2+x^3+...=x/(1-x)
标 题: [Zz]求解汉诺塔的非递归算法
发信站: 一网深情 (2002年06月30日02:49:12 星期天), 站内信件
发信人: zyxie (charlie), 信区: Algorithm
标 题: 求解汉诺塔的非递归算法.
发信站: 南京大学小百合站 (Sat May 18 19:28:30 2002)
Hanoi塔问题移动次数的递推公式：
令h(n)表示n个圆盘所需要的转移次数，根据递归的算法，先把前面的n-1格盘子转移到B上
，然后把第n个盘子转移到C上，最后再一次将B上的n-1个盘子转移到C上，
于是有：
h(n)=2h(n-1)+1,
h(1)=1, (1)
下面利用母函数来解上面的递归式：
设母函数
H(x)=h(1)x+h(2)x^2+...+h(n)x^n+..., (2)
将H(x)和-2xH(x)相加得到：
(1-2x)H(x) = h(1)x+[h(2)-2h(1)]x^2+[h(3)-2h(2)]x^3+...
根据递归式(1)可以得到h(2)-2h(1) = 1, h(3)-2h(2)=1,...
于是：
(1-2x)H(x) = x+x^2+x^3+...=x/(1-x)
整理得到：
H(x)= x/[(1-x)(1-2x)] (3)
我们可以将H(x)化为：
H(x) = 1/(1-2x) - 1/(1-x)
= (1+2x+(2x)^2+(2x)^3+...) - (1+x+x^2+...)
= ∑(2^k-1)x^k, k=1,2,...∞ (4)
比较(2)(4)得到：
h(k) = 2^k-1
也就是说，对于n个盘子，必须移动2^n-1次才可以。
下面是一个求汉诺塔问题的非递归程序
/* Non-recursive solution to Towers of Hanoi */
void main();
#include <stdio.h>
#define width (rings+1)
整理得到：
H(x)= x/[(1-x)(1-2x)] (3)
我们可以将H(x)化为：
H(x) = 1/(1-2x) - 1/(1-x)
= (1+2x+(2x)^2+(2x)^3+...) - (1+x+x^2+...)
= ∑(2^k-1)x^k, k=1,2,...∞ (4)
比较(2)(4)得到：
h(k) = 2^k-1
也就是说，对于n个盘子，必须移动2^n-1次才可以。
下面是一个求汉诺塔问题的非递归程序
/* Non-recursive solution to Towers of Hanoi */
void main();
#include <stdio.h>
#define width (rings+1)
void main()
{
int rings, last, next, x, z[500], s[3];
printf("how many rings? "); scanf("%d",&rings);
for(x=1; x<=rings; x++) /* put rings on first peg */
z[x]=width-x;
for(x=0; x<=2*width; x+=width) /* set base for each peg */
z[x]=1000;
/* if even number of rings, put first ring on second peg; if odd, on third */
if(rings%2==0)
{
last=1; s[2]=0; s[1]=1;
z[width+1]=z[rings];
}
else
{
last=2; s[1]=0; s[2]=1;
void main()
{
int rings, last, next, x, z[500], s[3];
printf("how many rings? "); scanf("%d",&rings);
for(x=1; x<=rings; x++) /* put rings on first peg */
z[x]=width-x;
for(x=0; x<=2*width; x+=width) /* set base for each peg */
z[x]=1000;
/* if even number of rings, put first ring on second peg; if odd, on third */
if(rings%2==0)
{
last=1; s[2]=0; s[1]=1;
z[width+1]=z[rings];
}
else
{
last=2; s[1]=0; s[2]=1;
void main()
{
int rings, last, next, x, z[500], s[3];
printf("how many rings? "); scanf("%d",&rings);
for(x=1; x<=rings; x++) /* put rings on first peg */
z[x]=width-x;
for(x=0; x<=2*width; x+=width) /* set base for each peg */
z[x]=1000;
/* if even number of rings, put first ring on second peg; if odd, on third */
if(rings%2==0)
{
last=1; s[2]=0; s[1]=1;
z[width+1]=z[rings];
}
else
{
last=2; s[1]=0; s[2]=1;
3号一块也得不到，2号得1块金子，1号也是一块也得不到。
5号海盗的策略稍有不同。他需要收买另两名海盗，因此至少得用2块金子来贿赂，才
能使自己的方案得到采纳。他的分配方案应该是：98块金子归自己，1块金子给3号，1块金
子给1号。
这一分析过程可以照着上述思路继续进行下去。每个分配方案都是唯一确定的，它可
以使提出该方案的海盗获得尽可能多的金子，同时又保证该方案肯定能通过。照这一模式
进行下去，10号海盗提出的方案将是96块金子归他所有，其他编号为偶数的海盗各得1块金
子，而编号为奇数的海盗则什么也得不到。这就解决了10名海盗的分配难题。
Omohundro的贡献是他把这一问题扩大到有500名海盗的情形，即500名海盗瓜分100块
金子。显然，类似的规律依然成立——至少是在一定范围内成立。事实上，前面所述的规
律直到第200号海盗都成立。 200号海盗的方案将是：从1到199号的所有奇数号的海盗都将
一无所获，而从2到198号的所有偶数号海盗将各得1块金子，剩下的1块金子归200号海盗自
己所有。
乍看起来，这一论证方法到200号之后将不再适用了，因为201号拿不出更多的金子来
收买其他海盗。但是即使分不到金子，201号至少还希望自己不会被扔进海里，因此他可以
这样分配：给1到199号的所有奇数号海盗每人1块金子，自己一块也不要。
202号海盗同样别无选择，只能一块金子都不要了——他必须把这100块金子全部用来
收买100名海盗，而且这100名海盗还必须是那些按照201号方案将一无所获的人。由于这样
的海盗有101名，因此202号的方案将不再是唯一的——贿赂方案有101种。
203号海盗必须获得102张赞成票，但他显然没有足够的金子去收买101名同伙。因此，
无论提出什么样的分配方案，他都注定会被扔到海里去喂鱼。不过，尽管203号命中注定死
路一条，但并不是说他在游戏进程中不起任何作用。相反，204号现在知道，203号为了能
3号一块也得不到，2号得1块金子，1号也是一块也得不到。
5号海盗的策略稍有不同。他需要收买另两名海盗，因此至少得用2块金子来贿赂，才
能使自己的方案得到采纳。他的分配方案应该是：98块金子归自己，1块金子给3号，1块金
子给1号。
这一分析过程可以照着上述思路继续进行下去。每个分配方案都是唯一确定的，它可
以使提出该方案的海盗获得尽可能多的金子，同时又保证该方案肯定能通过。照这一模式
进行下去，10号海盗提出的方案将是96块金子归他所有，其他编号为偶数的海盗各得1块金
子，而编号为奇数的海盗则什么也得不到。这就解决了10名海盗的分配难题。
Omohundro的贡献是他把这一问题扩大到有500名海盗的情形，即500名海盗瓜分100块
金子。显然，类似的规律依然成立——至少是在一定范围内成立。事实上，前面所述的规
律直到第200号海盗都成立。 200号海盗的方案将是：从1到199号的所有奇数号的海盗都将
一无所获，而从2到198号的所有偶数号海盗将各得1块金子，剩下的1块金子归200号海盗自
己所有。
乍看起来，这一论证方法到200号之后将不再适用了，因为201号拿不出更多的金子来
收买其他海盗。但是即使分不到金子，201号至少还希望自己不会被扔进海里，因此他可以
这样分配：给1到199号的所有奇数号海盗每人1块金子，自己一块也不要。
202号海盗同样别无选择，只能一块金子都不要了——他必须把这100块金子全部用来
收买100名海盗，而且这100名海盗还必须是那些按照201号方案将一无所获的人。由于这样
的海盗有101名，因此202号的方案将不再是唯一的——贿赂方案有101种。
203号海盗必须获得102张赞成票，但他显然没有足够的金子去收买101名同伙。因此，
无论提出什么样的分配方案，他都注定会被扔到海里去喂鱼。不过，尽管203号命中注定死
路一条，但并不是说他在游戏进程中不起任何作用。相反，204号现在知道，203号为了能
保住性命，就必须避免由他自己来提出分配方案这么一种局面，所以无论204号海盗提出什
么样的方案，203号都一定会投赞成票。这样204号海盗总算侥幸拣到一条命：他可以得到
他自己的1票、203号的1票、以及另外100名收买的海盗的赞成票，刚好达到保命所需的50
%。获得金子的海盗，必属于根据202号方案肯定将一无所获的那101名海盗之列。
205号海盗的命运又如何呢？他可没有这样走运了。他不能指望203号和204号支持他的
方案，因为如果他们投票反对205号方案，就可以幸灾乐祸地看到205号被扔到海里去喂鱼
，而他们自己的性命却仍然能够保全。这样，无论205号海盗提出什么方案都必死无疑。2
06号海盗也是如此——他肯定可以得到205号的支持，但这不足以救他一命。类似地，207
号海盗需要104张赞成票——除了他收买的100张赞成票以及他自己的1张赞成票之外，他还
需3张赞成票才能免于一死。他可以获得205号和206号的支持，但还差一张票却是无论如何
也弄不到了，因此207号海盗的命运也是下海喂鱼。
208号又时来运转了。他需要104张赞成票，而205、206、207号都会支持他，加上他自
己一票及收买的100票，他得以过关保命。获得他贿赂的必属于那些根据204号方案肯定将
一无所获的人（候选人包括2到200号中所有偶数号的海盗、以及201、203、204号）。
现在可以看出一条新的、此后将一直有效的规律：那些方案能过关的海盗（他们的分
配方案全都是把金子用来收买100名同伙而自己一点都得不到）相隔的距离越来越远，而在
他们之间的海盗则无论提什么样的方案都会被扔进海里——因此为了保命，他们必会投票
支持比他们厉害的海盗提出的任何分配方案。得以避免葬身鱼腹的海盗包括201、202、20
4、208、216、232、264、328、456号，即其号码等于200加2的某一方幂的海盗。
现在我们来看看哪些海盗是获得贿赂的幸运儿。分配贿赂的方法是不唯一的，其中一
种方法是让201号海盗把贿赂分给1到199号的所有奇数编号的海盗，让202号分给2到200号
保住性命，就必须避免由他自己来提出分配方案这么一种局面，所以无论204号海盗提出什
么样的方案，203号都一定会投赞成票。这样204号海盗总算侥幸拣到一条命：他可以得到
他自己的1票、203号的1票、以及另外100名收买的海盗的赞成票，刚好达到保命所需的50
%。获得金子的海盗，必属于根据202号方案肯定将一无所获的那101名海盗之列。
205号海盗的命运又如何呢？他可没有这样走运了。他不能指望203号和204号支持他的
方案，因为如果他们投票反对205号方案，就可以幸灾乐祸地看到205号被扔到海里去喂鱼
，而他们自己的性命却仍然能够保全。这样，无论205号海盗提出什么方案都必死无疑。2
06号海盗也是如此——他肯定可以得到205号的支持，但这不足以救他一命。类似地，207
号海盗需要104张赞成票——除了他收买的100张赞成票以及他自己的1张赞成票之外，他还
需3张赞成票才能免于一死。他可以获得205号和206号的支持，但还差一张票却是无论如何
也弄不到了，因此207号海盗的命运也是下海喂鱼。
208号又时来运转了。他需要104张赞成票，而205、206、207号都会支持他，加上他自
己一票及收买的100票，他得以过关保命。获得他贿赂的必属于那些根据204号方案肯定将
一无所获的人（候选人包括2到200号中所有偶数号的海盗、以及201、203、204号）。
现在可以看出一条新的、此后将一直有效的规律：那些方案能过关的海盗（他们的分
配方案全都是把金子用来收买100名同伙而自己一点都得不到）相隔的距离越来越远，而在
他们之间的海盗则无论提什么样的方案都会被扔进海里——因此为了保命，他们必会投票
支持比他们厉害的海盗提出的任何分配方案。得以避免葬身鱼腹的海盗包括201、202、20
4、208、216、232、264、328、456号，即其号码等于200加2的某一方幂的海盗。
现在我们来看看哪些海盗是获得贿赂的幸运儿。分配贿赂的方法是不唯一的，其中一
种方法是让201号海盗把贿赂分给1到199号的所有奇数编号的海盗，让202号分给2到200号
标 题: Re: [Zz]海盗分币问题
发信站: 一网深情 (Sun Jun 30 17:20:44 2002) , 站内信件
如果用计算机该如何做呢？
想一想？！
--
王等不才，剑履具备，
万里崎岖，为国效命。
西入巴蜀，励精图治，
电子自强，当立东方。
※ 来源:．一网深情 http://bbs.uestc.edu.cn [FROM: 202.115.25.*_*]
--
※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：3.405毫秒