博文
任意多边形面积的求解(2005-07-16 18:33:00)
摘要： 今天在论坛看到这样一个问题，程序输入一系列的点，按输入顺序首尾相连构成一个多边形，如何求这个多边形的面积？
其实方法很简单，定积分。我还是简单解释一下，如果是没有读过高等数学的朋友，也让你大致明白。
定积分的本质是求和，计算f(x)在积分区间[a,b]上的一个和Ｓ，首先把积分区间分成n份，这样的分法记为λ，记Δ(λ)=max{Δx|[xi-1,xi]}，也就是所有这些分成的小段中长度最大的一段的长，如果当Δ→０的时候，和式Ｓ＝∑f(θ)Δx (θ∈[xi-1,xi])的极限如果存在的话，就称其为f(x)在[a,b]上的定积分，记为
b
∫f(x)dx
a
其意义从几何上解释，就是f(x)的曲线与x轴、直线x=a,x=b围成的图形的面积。
现在要求的多边形是由线段组成的，只要把所有的线段都求定积分，最后把和加起来，就是多边形的面积。这个推论的证明从略。值得注意的是，用定积分求的面积有正负之分，即：
b a
∫f(x)dx=-∫f(x)dx
a b
从a积到b，与从b积到a只相差一个负号。
线段定积分的计算公式的推导
给出两个点，如何求这两点连成的线段的定积分值呢？
直线的方程可以用y=kx+b表示，所以围成的面积
S=
x2
∫(kx+b)dx
x1
=k/2(x2^2-x1^2)+b(x2-x1)
而斜率k=(y2-y1)/(x2-x1)
截距b=y1-kx1=y1-x1(y2-y1)/(x2-x1)，代入前式得
S=(y2-y1)(x2+x1)/2+y1(x2-x1)-x1(y2-y1)
=(x2-x1)(y1+y2)/2
这让我想到一个初等公式，梯形面积公式，y1,y2看成上下底，(x2-x1)看成是高，上底加下底乘高除二，对直线定积分得到的正是这个梯形的面积。这样走了一个大弯又回到初中了。
......
程序员考试的一点心得(2005-07-13 02:28:00)
摘要：今年我考了程序员，谈不上了不起吧，我也觉得没什么，没过的时候担心自己过不了，过了就觉得无所谓，冷静地想，我觉得“程序员” doesn't mean nothing!我的梦想有两步，第一成为一名程序员，第二成为一名优秀的程序员。所以我还是来谈谈我过程序员考试的一点微薄经验，希望对那些想过而还未过的同志有帮助。
一、想当程序员就要会写程序。
虽然考试没有上机，全是笔试，但对编程能力的考查是程序员考试的最大一个重头戏，具体表现在下午的程序填空题。为什么会觉得程序填空题难？这都是由编程能力决定的，你编过多少程序，了解多少种常用的算法，这些都是靠不断的练习而掌握的，而如果你现在想考程序员，而编程能力又不太强的话，建议不要拿着厚厚的辅导书啃了，丢开一边去，打开你的电脑，编个程序吧。
二、会写程序还要会读懂别人写的程序。
当你有了一定的编程能力之后，很多人都会有这样的感觉，对自己编的程序了如指掌，而对别人编写的程序却看花了眼，啥都看不懂，不知道写些啥玩艺，有的时候还有可能自己看自己很久以前写的程序看不懂了，觉得奇怪。其实没什么好奇怪的，这是一种程序阅读能力，就像英语阅读一样，你不会拿着自己写的文章说看不懂吧，程序阅读也如此，也需要训练。训练的方法就是多读，并且读的时候要想这位程序员是怎么想的，这一点很重要，想想他想问题的思路和方法，这样才会不被牵着鼻子走，达到一眼看穿的效果。
程序填空题就是这两方面能力的综合体现，首先需要阅读，阅读从两方面获得信息，一是程序说明，包括功能说明数据结构说明等，二就是程序本身和注释了。前一部分很重要，有时容易被忽略。另外还有一点很重要，读程序的顺序并不是写程序的顺序，意思就是说，你要全方位的读程序，不要傻乎乎地从第一行读到最后一行，比较大一些的程序都是分块的，有时一个函数名就说明了一切，而不需要仔细看，直接了解其功能，因为程序是分块的，所以阅读也就一块一块读，这样东瞧瞧西瞅瞅就知道要填什么了。当你了解了一个块的功能之后，你就按它的意思编程，当编到留空处时想想还缺什么，缺的东西就是要填的，然后准确地填进去就行了。
三、数据结构是重点。
书中的算法不要说会编，起码要都了解，明白是怎么一回事。然后主要的就是线性表、二叉树，这种填空最怕的是弄错指针，比如删掉一个线性表的元素，到底步骤是怎......
幂极数在近似计算上的应用(2005-07-08 21:29:00)
摘要：今天数学分析考完了，趋着这两天数学感觉还在，就简单谈谈极数在计算机中近似计算的简单应用吧。
极数是一种和的形式，注意只是一种形式，至于它到底是否具有和的意义，还需要数学上的证明，如
∞
∑x^n=1+x+x^2+x^3+...+x^n+...
n=0
也称为无穷极数。
它的意义一般不用管，这是数学研究的人的事，我们只记住它的形式，即一般是具有和的意义的。
极数的一个性质就是收敛或发散，收敛是我们想要的，如
∞
∑(1/2)^n就是我们中学熟悉的等比数列的和，它的和极限是存在的，
n=0
也就是说它收敛于S。
还有x项的级数叫函数项级数，它收敛于一个函数S(x)，反过来我们称极数是S(x)的极数展开，正如泰勒公式一样，将一个函数展开成多项式的和。
形如
∞
∑an(x-x0)^n
n=0
的极数称为幂级数，也就是一个在x=x0点展开的多项式，对于计算机来说多项式意味着只需做加法和乘法，而它却可以表示很多比较复杂的初等函数。
对幂级数来说，收敛半径R指的是它的收敛范围，如果它是在x0点展开，则当x取(x0-R,x0+R)时一定收敛于S(x)，若x取(-∞,x0-R)和(x0+R,+∞)时一定发散，如果取端点x0±R则不一定，需进一步判断。
R如何求，我不讨论，我只介绍用这样的方法算几个函数的展开。
1、求exp(x)的值，即以e为底，x为指数的函数值。
按泰勒级数展开：
exp(x)=1+x+x^2/2+...+x^n/n!+...
∞
=∑x^n/n!
n=0
所以可以用来近似计算：
double exp(double x)
{
int tag=0;//标记x
double s=0.0,a=1.0,n=1.0;
if(x<0){tag=1;x=-x;}//若x<0，进行标记
while(1)
{
s+=a;//累加求和
a=a/n*x;//递......
[转]谈谈我对攻读计算机研究生的看法(2005-06-25 21:22:00)
摘要：My Thoughts on Doing Advanced Computer Science Degree 转自http://www14.tianya.cn/publicforum/Content/itinfo/1/7514.shtml
回复CSDN和KAOYAN诸位网友的几点看法，（为避免吵架，郑重声明，本人不是高手，只是有感而发的一点个人陋见，欢迎指正，事先感谢）：
就我自己的理解，谈谈我对读研和软件学院的看法，不妥之处一笑了之即可。
如果你有实际开发工作经验，感觉自己的水平和实力进入了一个高原期，迫切需要从理论上提高，那么计算机学院是唯一选择。因为计算机学院才能让你在理论上 更上一层楼。软件学院从教学计划上就没有把你往这方面带。当然能不能更上一层楼最终还是完全取决于你自己。需要特别说明的是，工作经验并不一定等于开发经 验，我见过很多工作2-3年的人，但是没有一点开发经验。
你说：“他们都有很强的开发能力,只是不太喜欢读书,也只是希望混个学历对今后在岗位上晋升有好处”，我可以向你保证，你所说的人绝对不是开发能力很强的人。因为，1）高手不可能不喜欢读书；2）高手不可能想去混一个学历；3）高手不可能认为晋升是因为学历的原因。
还需要说明的是，考计算机的人未必个个都是高手，严格来说，大部分都不会编程序。也就是说，庸庸碌碌之辈仍然占绝大多数。研究生毕业的师兄只拿2500 元左右的比比皆是，所以不要寄希望于拿一张研究生文凭出去赚高薪。但是，对于有实际开发工作经验的人，要想自己在3年之中有一个真正的提高的话，计算机学 院提供了广阔的平台。就我所知，每一个月拿2万以上的也有（上海育碧，图形特效算法设计）。所以，同为研究生毕业，能力的差距是极大的。所以，不要去问 “研究生毕业能拿多少？”，要问“像我这种水平的人，研究生毕业能拿多少钱？”这样人家才能够准确地回答你。
所谓“有实际开发工作经验”是指 你目前已经具备下列能力：1）你已经认为C++和汇编语言都是很简单的语言，并能够自如地运用；2）你能够在30分钟之内想到正确的五子棋AI算法设计思 路和方向；3）你完全理解STL为什么这么重要；4）你能够独立地解决所有的编译与链接问题，哪怕你从来没有遇到的问......
简单图形扫描转换算法::Bresenham算法(2005-06-20 16:39:00)
摘要：【什么是扫描转换】
按我的理解就是把图形转换成图像。图形是为了描述客观景物的数学模型，比如表示一条直线可以用直线上两个端点坐标表示，表示一个圆可以用圆心坐标和半径长度表示。图形的描述只在数学阶段，而要把图形真正显示在显示器上，则需要转换成图像，为了说清楚图像必须要了解显示器，说白了显示器能表示的图像都是离散的，也就是不连续的点阵，正如我们常说的分辩率，它指的就是点阵的大小，而运用到ＲＧＢ色彩空间的显示器，对每一个像素点进行Ｒ、Ｇ、Ｂ三个分量的同时扫描，进而产生五彩缤纷的图像，尽管现在的分辩率很高但是它还是离散的，它的数学本质没有变，我们从显示器上观察的世界是不真实的，是数字的，离散的。所以在这样的显示设备上显示图像最大的问题就是失真，尽管分辩率够大但理论上的失真是不可避免的，所以我们只能做到效果上最好的图像显示了，也就是用离散的点最佳逼近真实值，也就是图形扫描转换。
【Bresenham算法】
简单图形的扫描转换常用算法是Bresenham算法。它的思想在于用误差量来衡量点选取的逼近程度。其过程如下：
以平面二维图形的扫描转换为例，设要画的图形方程为F(x,y)=0，要画的区域为[x0,x]（不妨设x方向是最大位移方向，即△x>△y），则Ｆ(x,y)也是一个误差度量函数，我们拿离散的点值代入如果大于0则正向偏离，否则负向偏离，等于0的情况比较少，它表示的是不偏离即恰好与真实点重合。既然x是最大位移方向，那每次对x自增1，相应的y可以选择不增或增1(或-1，具体问题具体分析)，选择的方法就是d=F(x+1,y±0.5)的正负情况进行判断从而选择y的值。实际情况中还要考虑到浮点数的计算问题，因为基本的图形扫描转换算法最好能够硬件实现，所以摆脱浮点数是最好的，常用的方法是对d进行递推，而不是直接由Ｆ(x,y)给出。
【圆的扫描转换算法】
以画圆为例，给出圆心的坐标(0,0)和半径Ｒ，求圆图像的最佳逼近点。
圆是中心对称的特殊图形，所以可以将圆八等分，则只须对八分之一圆孤求解，其它圆孤可以由对称变换得到，我们求的八分之一圆孤为(0,R)-(R√2,R√2)，可知最大位移方向是x方向，x0=0,y0=R，每次对x自增，然后判断y是否减1，直到x>=y为止。误差量由Ｆ(x,y)=x^2+y^2-......
公历日期类(2005-06-15 16:43:00)
摘要：//file:date.h
#include<iostream.h>
class date
{
public:
date(){year=month=day=leapyear=pastdays=week=-1;};
date(int y,int m,int d);
int getweek(){return week;};
friend bool operator<(date& dt1,date& dt2);
friend long leapyearsbetween(date dt1,date dt2);
friend ostream& operator<<(ostream& out,date& dt);
friend long operator-(date dt1,date dt2);
date& operator+=(int days);
protected:
int year,month,day;
int leapyear,pastdays,week;
};
//file:date.cpp
#include<iomanip.h>
#include "date.h"
date::date(int y,int m,int d)
{
static int
r1......
公历历法::星期算法(2005-06-12 18:24:00)
摘要：[原创]
【引】
《创世纪》
创世在宇宙天地尚未形成之前，黑暗笼罩着无边无际的空虚混饨，上帝那孕育着生命的灵运行其中，投入其中，施造化之工，展成就之初，使世界确立，使万物齐备。
上帝用七天创造了天地万物。这创造的奇妙与神秘非形之笔墨所能写尽，非诉诸言语所能话透。
第一日，上帝说：“要有光！”便有了光。上帝将光与暗分开，称光为昼，称暗为夜。于是有了晚上，有了早晨。
第二日，上帝说：“诸水之向要有空气隔开。”上帝便造了空气，称它为天。
……
第七日，天地万物都造齐了，上帝完成了创世之功。在这一天里，他歇息了，并赐福给第七天，圣化那一天为特别的日子，因为他在那一天完成了创造，歇工休息。就这样星期日也成为人类休息的日子。
“造化钟神秀，阴阳割分晓。”上帝就是这样开辟鸿蒙，创造宇宙万物的。
以上来自《圣经》，现在还有一些基督教徒每个礼拜天去教堂朝拜，可见一个星期七天就源于此，这正是我讨论的中心，如何计算哪年哪月哪日是星期几。
【公历历法】
公历历法很简单，年有润年（LeapYear）和平年之分，平年每月天数恒为：
月份 一 二 三 四 五 六 七 八 九 十 十一 十二
天数 31 28 31 30 31 30 31 31 30 31 30 31
共365天。润年366天，二月多一天，29天。
【润年判断】
如果年份数能被4整除但不能被100整除或者能被400整除者，为润年。
【400年刚好一个轮回】
很容易想到每400年内的润年数相等，即刚好一个轮回，400年有多少个润年？被4整除的有100个，被100整除的有4个，被400整除的只有1个，所以一共有100-4+1=97个润年，所以400年共有(365*400+97)天，即146097天，除7余0！
也就是说2001年1月1日的星期数与1年1月1日的星期数相同，翻出日历一看，星期一，我不知道上帝什么时候造的人，或许是1年1月1日。这样一来，任何一个日期我们都可以把它折算到0~......
[TOJ]1021麻将游戏(2006-04-22 13:18:00)
摘要：麻将游戏
Time Limit:1s Memory Limit:1024k
Total Submit:3119 Accepted:531
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
在一种"麻将"游戏中，游戏是在一个有W＊H格子的矩形平板上进行的。
每个格子可以放置一个麻将牌，也可以不放（如图所示）。玩家的目标是将平板上的所有可通过一条路径相连的
两张相同的麻将牌，从平板上移去。最后如果能将所有牌移出平板，则算过关。
这个游戏中的一个关键问题是：两张牌之间是否可以被一条路径所连接，该路径满足以下两个特性：
1. 它由若干条线段组成，每条线段要么是水平方向，要么是垂直方向。
2. 这条路径不能横穿任何一个麻将牌 (但允许路径暂时离开平板)。
这是一个例子：
在（1，3）的牌和在(4, 4)的牌可以被连接。(2, 3)和(3, 4)不能被连接。
你的任务是编一个程序，检测两张牌是否能被一条符合以上规定的路径所连接。
Input
第一行为一整数N表示有N组测试数据。
每组测试数据的第一行有两个整数w，h （1<=w，h<=75），表示平板的宽和高。
接下来h行描述平板信息，每行包含w个字符，如果某格子有一张牌，则这个格子上有个'X'，否则是一个空格。
平板上最左上角格子的坐标为（1，1），最右下角格子的坐标为（w,h）。
接下来的若干行，每行有四个数x1， y1， x2， y2 ，且满足1<=x1,x2<=w，1<=y1,y2<=h，
表示两张牌的坐标（这两张牌的坐标总是不同的）。
如果出现连续四个0，则表示输入结束。
Output
输出文件中，对于每一对牌输出占一行，为连接这一对......
[TOJ]1029埃及分数(2005-06-10 13:41:00)
摘要：埃及分数
Time Limit:2s Memory Limit:1000k
Total Submit:2302 Accepted:340
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。
如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。
对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如：
19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30,
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18.
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。
给出a,b(0〈a〈b〈1000),编程计算最好的表达方式。
Input
第一行:N 表示有N组测试数据，每组测试数据为一行包含a,b(0〈a〈b〈1000)。
Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。
Sample Input
1
19 45
Sample Output
5 6 18
Source
oibh
#include <iostream>
#include <algorithm>
#include <cstdlib>
......
[TOJ]1203程序分析器(2005-06-07 18:50:00)
摘要：程序分析器
Time Limit:2s Memory Limit:2000k
Total Submit:26 Accepted:4
--------------------------------------------------------------------------------
Problem
Tiny Basm语言(简称为TB语言)的巴科斯-瑙尔范式(BNF)为：
<程序> ::= <语句> ¿ { <语句> ¿ }
<语句> ::= <行号> ÿ <语句体>
<语句体> ::= <累加语句> | <输出语句> | <转移语句> | <条件语句> | <结束语句>
<累加语句> ::= <变量> + <整数>
<输出语句> ::= <变量> ?
<转移语句> ::= GO ÿ <行号>
<条件语句> ::= IF ÿ <变量> = <整数> ÿ <转移语句>
<结束语句> ::= END
<变量> ::= <字母>......