Unlock Particle

追逐与拦截

Jul 17th 2010

By: Catouse

No comments
小时候玩过叫“打蜜蜂”的游戏。当然只是我们一厢情愿的称呼，游戏的名字叫“Galaga”。游戏的目的就是操作一架只能左右移动的战机，消灭成群的“小蜜蜂”，并且还有躲避不停非向战机的子弹和“蜜蜂”。我最喜欢里面的“嗡嗡”声。不过能及时躲过“跟踪弹”的追击才是我引以为豪的事情。可以想象如果游戏中的敌人不能跟踪我的位置，游戏将变得多么乏味。

追逐

追逐有很多种方式，这里仅讨论自然环境中的视线追逐，即追击者在看到猎物所在方位进行跟踪。这种方式很符合真实情况。

假设场景中有一个追击者A和猎物B，某时刻，追击者以速度向量u运动，猎物以速度向量v运动，B为追击者速度向量的末端点。

从追击者A的角度来看，猎物C在向量AB的左侧，向量AB与向量AC夹角为θ，追击者A只需要将自己的速度向量u逆时针旋转角度θ，即可将自身面对猎物C并向其靠近。如果C在向量AB的右侧，则需要将u顺时针旋转一定角度。由此，面临的问题就是判断猎物是在追击者速度向量左侧还是右侧。

上面的问题可以简化为判断平面上向量某一点在已知向量左侧还是右侧。当然这个问题已经有一个很好的解法。定义平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量为：

$S(P_{1},P_{2},P_{3})=\begin{vmatrix} x_{1} & x_{2} & x_{3}\\ y_{1} & y_{2} & y_{3} \\ 1 & 1 &1 \end{vmatrix}=(x_{1}-x_{3})*(y_{2}-y_{3})-(y_{1}-y_{3})(x_{2}-x_{3})$

当P1,P2,P3逆时针时S为正的，当P1,P2,P3顺时针时S为负。

对于上图三点A，B，C，可以判断C与向量AB的位置关系：
- 如果S（A，B，C）为正数，则C在矢量AB的左侧；
- 如果S（A，B，C）为负数，则C在矢量AB的右侧；
- 如果S（A，B，C）为0，则C在直线AB上。
```
class PursueSimulator:Simulator
{
    private PointF preyPos = new PointF(BGC.WindowSize.Width, BGC.WindowSize.Height/5);//猎物位置
    private PointF predatorPos = new PointF(0, 10);//追击者位置
    private PointF purposePos = PointF.Empty;//目的点
    private Vector3 u = new Vector3(0.7, 0.7,0);//追击者速度向量
    private Vector3 v = new Vector3(-1, 0.6,0);//猎物速度向量
    private Vector3 vectorAC = new Vector3();//猎物C与追击者A方位向量
    private Vector3 aRcSpeed = new Vector3();//追击者A对于猎物C的相对速度向量
    private double rollAngle = 0;//偏转角度
    private double rollDirection = 0;//偏转方向,>0:逆时针偏

    private Pen pen1 = new Pen(Color.FromArgb(20, Color.Gray));//画笔1
    private Pen pen2 = new Pen(Color.FromArgb(20, Color.Yellow));//画笔2

    //每次刷新画面逻辑时调用
    public override void Render()
    {
        #region 猎物和追击者按照预计速度运动
        predatorPos.X += (float)u.X;
        predatorPos.Y += (float)u.Y;
        preyPos.X += (float)v.X;
        preyPos.Y += (float)v.Y;
        #endregion

        #region 保证猎物和追击者遇到边界方向反弹
	//...
        #endregion

        vectorAC.X = preyPos.X - predatorPos.X;
        vectorAC.Y = preyPos.Y - predatorPos.Y;
        vectorAC.Z = 0;

        purposePos = preyPos;//追击者目的点为猎物

	//
	// 标记A
	//

	//获取追击者速度方向与猎物方位方向,便计算更真实的转角
        rollAngle = Vector3.Angle(u, vectorAC);
        rollDirection = (predatorPos.X - purposePos.X) * (predatorPos.Y + u.Y - purposePos.Y) - (predatorPos.Y - purposePos.Y) * (predatorPos.X + u.X - purposePos.X);

        if (rollDirection > 0)
            u.Roll(Math.Max(rollAngle/3.0, Math.PI/360.0));
        else if (rollDirection < 0)
            u.Roll(-Math.Max(rollAngle/3.0, Math.PI/360.0));
    }

    //每次重绘画面时调用
    public override void ReDraw(Graphics g)
    {
        g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
        g.DrawEllipse(pen1, predatorPos.X - 4, predatorPos.Y - 2, 8, 8);
        g.DrawEllipse(pen2, preyPos.X - 4, preyPos.Y - 2, 8, 8);
    }
}
```
上图中，白色轨迹为追击者。可见追击者已经能很好的追逐猎物，而且过渡自然。

拦截

拦截是追逐的一种，不过有很大的不同。拦截是通过预测猎物的运动方向和速度大小，直接以预定位置为目标，达到目标后与猎物相遇。通常拦截是更明智的做法，即使追逐者的速度比猎物小，通过有效的拦截也能达到目标。

不过从编程来说实现拦截也是很简单。在追逐算法中，追击者只需要以猎物为目标，并调整自己的方向即可。而拦截中，追击者预测猎物位置，并以预测点位置为目标，调整自己的方向就可以到达预测地点。由此说来，仅需要解决的一个问题是计算猎物和追击者能够相遇的预测点。

计算预测点可以通过下面的方法：
1. 计算追击者与猎物的相对速度，即猎物与追击者的速度向量差Vt=v-u；
2. 计算两者间的距离向量S = AC；
3. 由以上条件可以计算追击者与猎物相遇的时间T=|S|/|Vt|;
4. 相遇点距离追击者的向量St=OA+T*v;（O为坐标原点）
在追逐的算法中，只需要在追逐角度计算之前将追逐的目标置为预测点。

将以下代码插入到上面的代码“标记A处”：
```
	#region 拦截
	aRcSpeed = v - u;
	time = vectorAC.Magnitude / aRcSpeed.Magnitude;
	//计算预测点,并将追击者目的点置为预测点
	purposePos = new PointF((float)(preyPos.X + v.X * time), (float)(preyPos.Y + v.Y * time));
	#endregion
```
模拟程序下载

下载地址： Dropbox | DBank | UUShare

最后附送模拟程序壁纸一张，点击图片查看大图（1280×800）
AI

AI, 下载, 人工智能, 拦截, 算法, 编程, 追逐
亦歌mini

May 9th 2010

By: Catouse

13 comments
亦歌mini是亦歌的又一个桌面扩展应用.一个透明可定制颜色的桌面浮动面板,可以显示歌词和进行播放操作,支持全局快捷键,自动检测到其他打开的亦歌客户端并配合其来使用.

亦歌mini包含了亦歌本身的所有功能,还具有以下特色功能:
1. 简洁美观的交互界面,浮动桌面面板,可以显示歌词,支持鼠标控制播放.
2. 随意更改面板颜色,可定制的背景透明度,拖动改变面板大小,个性搭配你的桌面环境.
3. 全局快捷键响应,无需打断当前工作,随时切换和收藏歌曲.
4. 内置亦歌桌面版,不用打开浏览器也可以享受亦歌,启动时可以跳过桌面版显示,仅显示亦歌mini.
5. 多种使用模式,启动时自动检测已经打开的亦歌(用其他方式打开的亦歌,比如浏览器,亦歌桌面版,跨平台Air等),轻松搭配任意客户端使用亦歌.
6. 绿色单文件程序,无需安装,还可以装进你的U盘使用.
下载: SkyDrive | Dropbox | UUShare | box.net 现在可以去http://mini.1g1g.org下载最新版

注意:仅支持32位Windows操作系统,包括Windows7, Vista, Xp

Xp用户如果没有安装.net framework需要自行安装,可以从这里下载安装包(.net framework 2.0)

需要的其他组件:adobe flash player activeX

亦歌mini的创意得感谢airplay这么好的作品,还有@fatboy等热心朋友的大力帮助.
欢迎大家给我意见反馈,Gtalk: catouse[@]gmail.com.
Software

Beta, Download, 下载, 亦歌mini, 软件
制作亦歌mini

May 8th 2010

By: Catouse

1 comment

亦歌是我喜欢的在线音乐播放器.美观的界面,简洁的操作,打开浏览器就能收听歌曲.最大的特色是无需维护播放列表,亦歌会根据用户听歌习惯源源不断的推送更符合口味的歌曲到播放列表.这很好的满足了像我这种懒人也能亲近音乐.我使用亦歌时要做的就一件事情:喜欢听的歌曲收藏,不喜欢听的直接pass,遇到讨厌的歌手加入黑名单.其他的交给亦歌吧.

亦歌通常需要打开浏览器使用.幸好亦歌开放了API,这得以让满足各种需要的扩展应用产生.比如亦歌桌面版就可以把亦歌搬到桌面上,不必打开浏览器就可以使用.不过对于我这种懒人,还不满足,我需要在桌面上显示歌词,并进行一些播放的操作,而且还有足够简洁.为了更懒,我决定自己重新做一个桌面扩展应用.这开始于那天我在亦歌扩展开发网页上乱逛.我把这个应用称为亦歌mini.

第一天,我编程测试了亦歌api在.net上的可行性,并且特意编写了一个控制1gCommander的对象.

第二天,我开始在Photoshop上设计我的mini界面了.开始时我也是按照常规的思路,左边是操作按钮,右边是歌词显示,不过我马上想到了Airplay的超酷交互模式.实际上操作按钮仅在鼠标接近时才起作用,为何不能仅在有可能用到时再显示呢.这样可以留出全新的空间为歌词显示所用.后来我遇到的问题是怎样合理配色,绘制阴影,边框,渐变背景,设定面板大小等.就反复测试不同的界面,并且编程实现,不过大多自己都不满意.这天几乎是通宵未睡.

为了更加完美,第三天差不多花了半天时间在界面上,剩下的时间就是完善程序配置,加入全局快捷键功能.还好这都很快.接下来我又对一些小错误进行了改正,总算是完成了第一个版本.

就这样整整花了三天时间,结果还算满意,自己用起来也很爽.我可以在桌面上看到歌词了.我的最初要求就是这些.我不用再去理会亦歌原来的播放器界面,我只需要喜欢的歌曲就收藏,不喜欢的Pass.这一切都可以通过亦歌mini的快捷键完成,或者直接在面板上通过鼠标完成.真是很方便!

后来我把这个发给我的朋友,没想到大家都喜欢.这鼓励我继续完善亦歌mini,并分享给大家.

大家可以到这里看到亦歌mini的最新信息.

Software

亦歌, 亦歌mini, 开发, 软件
到底有多少条路?

May 3rd 2010

By: Catouse

1 comment
今天(已经是昨天了)又翻了翻《啊哈,灵机一动》(马丁·加德纳著),有个排列组合的谜题是复杂的路.要求就是寻找在一个错综复杂的路径图里面从一个节点到另一个节点的所有可行路径数目.已规定每次我只能选择向右或者向上移动一个位置.

比如上图是一个棋盘形式的路径图,比较容易找规律,如果我愿意花一个钟头的时间的话,我可以把所有路径列举出来,如果顺利的话,我想可以给我更少的时间.我小时候总是为自己能很快而准确的列举找到答案而洋洋得意.我还记得小时候寻找一个笼子里面兔子和鸡的合适数目,我忙碌的在草稿纸上列举所有兔子的腿数和鸡的腿数.

虽然我知道很少有人愿意按照上面的方法去得到答案,但是如果去做了,我肯定能从中找到规律.不过下面从一个格子开始分析,这样也许是一个很不错的尝试.当我被迫要打开柜子所有抽屉找到所有装了纽扣的抽屉时,从第一个抽屉开始,是个明智的决定,这样不至于后来一团糟,想象一下,当你最后都不知道打开哪些抽屉而又不得不再次打开验证时是多么的令人沮丧.

显而易见,在一个格子里面,从左下角到右上角有两种路径.如上图A→C→B和A→D→B.

为了更好的表现每个节点上到达该节点的路径数目,可以及时的把数目标注上,如上图所示.这样看起来好极了,我开始迫不及待的按照这种方法在棋盘的每个格子的节点上开始标记.

我做的很快.我还不知道是否是正确的,但我很兴奋,没有什么能够阻止我继续写下这些数,不停计算100以内加法对我是一件很过瘾的事情.真不可思议,一分钟内我列举出了所有的数目,我认为肯定是正确的,我必须要证明.归纳法无疑是一个很不错的证明.
1. 已知第一个格子里面,除右上角的节点,其他三个节点的数目已知全部为1,可知从第一个格子的左下角到右上角有两条不同路径.记值为2。有谁还怀疑1+1=2呢?
2. 对于非十字型节点,也可以当做十字形节点处理,把节点左边和下边的十字分支数目定为0
3. 参照下图,假如我已经知道某个节点左边节点和下面节点值的话,只要把这两个值做加法就是该节点值
再次回到这些棋盘上面的数字,总是相邻两个方向的数字做加法得到下一个节点值.把棋盘旋转45°.真难以置信,这不就是杨辉三角吗?这使我想到当把一个没有头脑的虫子放在棋盘左下角让其按照谜题规律移动,那么这些数字足以代表虫子到达某节点的可能性.在加德纳的《啊哈,灵机一动》书上,谜题本身是苏珊为了避免上学碰到讨厌的斯蒂克而需要每天走不同的路径.呵呵,如果加德纳进一步把这个故事扩展的话.我想苏珊可以完全有根据的选择那些斯蒂克选择可能性小的路径.当然我们得残忍的先认同斯蒂克像虫子一样.杨辉三角最重要的性质是第n行的所有数列式n次二项式展开式的系数列.这也很好的说明了到达节点的概率性.

现在我可以欢呼了.甚至像下图这种不规则格子地图也能用这种方法得到正确答案.

也许已经取得了很大的胜利了,不过我已经厌倦了在每个节点做加法.当有一个复杂的棋盘地图或者蜂窝地图时我就不能逼迫自己做着机械的加法.我需要计算机来帮助我得到一个简洁的答案.

我之所以在上面对这个谜题进行分析,是因为我在看书联想到上周上课时练习的几道动态规划问题.寻找路径问题,可以归结为一个简单的递推.而动态规划能够保正每个节点仅被计算一次,减少重复计算.实际上,我在上面的操作中,就是一个手工的动态规划演绎过程.

下面使用动态规划的方法来重新分析棋盘路径问题,并尝试给出算法.

不妨做如下定义:给棋盘上的每个节点定义坐标,最左下方的为f(0,0),最有上方的为f(M,N).

该问题子问题就可以描述为:从(0,0)走到(x,y),每次只能往右或者往上走一步(对应坐标值增1),一共有多少种走法,该点走法的数目记为f(x,y),原问题就是求解f(M,N)

要得到f(x,y)有两个方法,一个是从(x-1，y)往右走一步到(x,y),另一个就是从(x,y-1)走到(x,y).第一个方法有f(x-1,y)种走法,第二种有f(x,y-1)种走法.所以可以得到f(x,y)=f(x-1,y)+f(x,y-1),这个可以通过归纳法证明.由此得到递推公式为:
1. 当x=0或y=0时,f(x,y) = 1;
2. 当x>0且y>0时,f(x,y)=f(x-1,y)+f(x,y-1)
```
/// 求解到坐标(m,n)的不同路径数目
public int HowManyWays(int m,int n)
{
    //创建一个二维表来保存每个节点的路径数目值
    int[,] answerMap = new int[m, n];
    //初始化表中所有值为1
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            answerMap[i, j] = 1;

    //使用递推来得到每个节点的解
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            answerMap[i, j] = answerMap[i - 1, j] + answerMap[i, j - 1];

    //返回结果
    return answerMap[m - 1, n - 1];
}
```
这个算法也就是计算了杨辉三角.如果要计算非规则的棋盘地图节点路径的话,就不能使用简单的二维表,可以考虑使用树形结构或者图来存储地图节点关系数据.不同的移动规则也影响算法过程.
Algorithm, C-Sharp, Math, Programming

C#, 动态规划, 归纳法, 杨辉三角, 谜题, 路径, 递推

寻找非线性方程实根(4)-Aitken迭代加速

Apr 15th 2010

By: Catouse

这次来尝试使用Aitken法寻找方程实根,Aitken是迭代加速方法中的一种.

假设非线性方程为x=f(x)
一次迭代为u=f(x_n)
同时得到v=f(x_u)
x_n+1 = v-(v-u)²/(v-2u+x_n)
当u和v的差值在容差之内,则认为v为方程的一个实根

Aitken的收敛速度会比常规的迭代方法略快.
参考代码如下:

/// <summary>
/// Aitken求解非线性方程的一个实根
/// </summary>
/// <param name="func">要求解的方程函数</param>
/// <param name="maxItCount">最大迭代次数</param>
/// <param name="eps">容差</param>
/// <param name="x">根的初始值,预估计一个更接近于根的实际值的初始值</param>
public static double Aitken(SimpleEquation func, double eps, double x,int maxItCount)
{
    double u, v, x0 = x;
    int i =0;
    for (i = 0; i < maxItCount;i++ )
    {
        u = func(x0);
        v = func(u);
        if (System.Math.Abs(u - v) < eps)
        {
            x0 = v;
            break;
        }
        else
            x0 = v - (v - u) * (v - u) / (v - 2.0 * u + x0);
    }
    if (i == maxItCount)
        throw new Exception("迭代不收敛!");
    return x0;
}

用方程 $x=-2x{}^3^{}+2x{}^2^{}+3$ 验证在1.5附近的实根

验证代码如下:

static void Main(string[] args)
{
    Console.WriteLine(Aitken(Func,0.00000001,1.5,50));
}

public static double Func(double x)
{
    return -(2*x*x*x-2*x*x-3);
}

运行结果为
1.40445153631998

Algorithm, C-Sharp, Math

Aitken, 实根, 数学, 方程, 迭代法, 非线性方程

寻找非线性方程实根(3)-试位法

Apr 15th 2010

By: Catouse

No comments

试位法也称为割线法,是二分法的一种改进,每次比二分法多计算一次乘法.

设满足:f(a)<f(b),则在区间[a,b]内有实根

用直线(割线)连接点(a,f(a)),(b,f(b)),得到弦.弦方程为
$y(x)=[\frac{f(b)-f(a)}{b-a}]x+[f(a)-\frac{f(b)-f(a)}{b-a}a]$
令y(x)=0，解出x作为比较值,即
$x_{n}=[\frac{af(b)-bf(a)}{f(b)-f(a)}]$

假设k = f(a)f(x_n)
如果k<0，则b=x_n
如果k>0，则a=x_n
如果k=0(实际操作为k小于指定的容差eps),则x_n就是要求的实根

试位法局限于需要一个给定的区间,而且不能保证一定收敛

下面的代码供参考:

/// <summary>
/// 试位法求解非线性方程的一个实根
/// </summary>
/// <param name="func">要求解的方程函数</param>
/// <param name="eps">容差</param>
/// <param name="a">给定的区间左端点</param>
/// <param name="b">给定的区间右端点</param>
public static double RegulaFalsi(SimpleEquation func, double eps, double a, double b)
{
    double f_a, f_b, f_x,x;
    f_a = func(a);
    f_b = func(b);
    if (f_a * f_b > 0)
    {
        throw new Exception("不能用试位法在给定的区间找到实根");
    }
    do
    {
        x = (a * f_b - b * f_a) / (f_b - f_a);
        f_x = func(x);
        if (f_x * f_a < 0
        {
             b = x;
             f_b = f_x;
         }
         else
         {
             a = x;
             f_a = f_x;
         }
     } while (System.Math.Abs(f_x) >= eps);
     return x;
}

用方程 $2x{}^3^{}-2x{}^2^{}+x-3$ 验证在区间[-10,10]上的实根

验证代码如下:

static void Main(string[] args)
{
    Console.WriteLine(NonlinearEquations.RegulaFalsi(Func,0.00000001,0,5));
}

public static double Func(double x)
{
    return 2*x*x*x-2*x*x+x-3;
}

运行结果为1.40445153506626

与mathematica结果相符

Algorithm, C-Sharp, Math

实根, 数学, 方程, 试位法, 非线性方程

寻找非线性方程实根(2)-牛顿迭代法

Apr 14th 2010

By: Catouse

No comments

当已知在区间[a,b]上方程f(x)=0只有一个唯一的实根,则可以通过牛顿迭代方法得到方程的实根
$x_{n+1} = x_{n}-\frac{f(x_{n})}{{f'(x_n)}}$

这样不断迭代计算的值序列会收敛于方程f(x)=0的根.

当满足以下条件时,迭代结束

$|f(x_{n+1})|<\varepsilon \:\:\wedge\:\: |x_{n+1}-x_{n}|<\varepsilon$

程序设计时,为了提高效率,使用循环代替迭代,但为了不致于造成死循环,可以预先给定一个迭代的最大次数,超出则认为方程迭代不收敛

下面的代码供参考

/// <summary>
/// 用牛顿法求解非线性方程的一个实根
/// </summary>
/// <param name="func">方程函数</param>
/// <param name="derivative">方程求导函数</param>
/// <param name="eps">要求的计算精度</param>
/// <param name="maxItCount">最大迭代次数</param>
/// <param name="x">根的初始值,预估计一个更接近于根的实际值的初始值</param>
/// <returns>返回找到的实根</returns>
public static double Newton(SimpleEquation func, SimpleEquation derivative, double eps, int maxItCount,int x)
{
    int k = 0;
    double x0, x1,y,dy;
    x0 = x;
    x1 = x+eps+1.0;
    y = func(x0);
    dy = derivative(x0);
    while ((System.Math.Abs(x1 - x0) >= eps ||System.Math.Abs(y)>=eps)
        && k < maxItCount)
    {
        if (System.Math.Abs(dy) + 1.0 == 1.0)
            //导数为0,找到一个实根
            return x0;
        x1 = x0 - y / dy;
        y = func(x1);
        dy = derivative(x1);
        x0 = x1;
        k++;
    }
    if (k == maxItCount)
        Console.WriteLine("迭代没有收敛");
    return x1;
}

用以下一元3次方程验证
$y = x^3-10*x^2+100$

求解x=5附近的一个实根
测试代码如下:

static void Main(string[] args)
{
    Console.WriteLine(Newton(Func,Der,0.000001,60,5));
}
//计算f(x)的值,输入x,返回f(x)
public static double Func(double x)
{
    return x*x*x-10*x*x+100;
}
//计算f'(x)的值,输入x,返回f'(x)
public static double Der(double x)
{
    return 3*x * x - 20 * x;
}

实际返回结果为4.12605572254691

Algorithm, C-Sharp, Coding, Math

实根, 数学, 方程, 牛顿迭代法, 迭代法, 非线性方程

寻找非线性方程实根(1)-对分法

Apr 13th 2010

By: Catouse

No comments

用计算机来获得线性方程实根是一个很普遍的问题,现在还记得第一次编程解决的典型问题就是求解一元二次方程实根.那个当然可以使用经典公式得到,不过寻找普遍的非线性方程实根也是一件有趣的事情,简单好玩而且不局限方法的事情总是引人入胜.

对分法是求解非线性方程实根最普遍的方法,通过给定一个目的实根可能存在的区间,在区间内划分小区间进行搜索.对于在搜索过程中的每一个小区间[X,X_k+1]进行如下判断:

定义:h为小区间的长度,则有X_k+1=X_k+h
如果=0,则X_k为一个实根,然后从X_k+h/2开始往后搜索
如果=0，则X_k+1为一个实根,且从X_k+1+h/2往后搜索
>0，则说明在当前区域没有实根,或者h太大,放弃本区域,从X_k+1开始往后搜索
如果f(X_k)*f(X_k+1)<0，则说明在当前区域内有实根,就可以利用对分法,不断将当前区间范围缩小,直至找到该区域上的根,然后从X_k+1网后搜索

很显然,该方法操作简单,但对于小区间长度h的选择要慎重,如果过长,则可能丢失实根,如果过小,则需要花费更多的计算量.
下面是一个C#实现的算法参考

/// <summary>/// 对分法求解非线性方程的根
/// </summary>
/// <param name="eqt">要求解的方程</param>
/// <param name="eps">精度</param>
/// <param name="a">区间左端点</param>
/// <param name="b">区间右端点</param>
/// <param name="h">搜索步长</param>
/// <param name="m">预计最多根的数目</param>
/// <returns>返回所有找到的根的值列表</returns>
public static List<double> Bisect(SimpleEquation func, double eps, double h, double a, double b, int m)
{
    List<double> result = new List();
    result.Clear();
    bool js;
    double z = a;
    double y = func(z);
    double z1, y1,z0,y0;
    while (z < b + h / 2.0 && result.Count< eps)//判断左端点是否为根
    {
        if (System.Math.Abs(y) < eps)//判断左端点是否为根
        {
             result.Add(z);
             z = z + h / 2.0;
             y = func(z);
        }
        else
        {
            //计算右端点
            z1 = z + h;
            y1 = func(z1);
            //判断右端点是否为根
            if (System.Math.Abs(y1) < eps)
            {
                 result.Add(z1);
                 z = z1 + h / 2.0;
                 y = func(z);
            }
            //如果左右端点值同负或同正,则将右端点变换为新区间的左端点
            else if (y * y1 > 0.0)
            {
                y = y1;
                z = z1;
            }
            //如果左右端点值异号,则说明该区间存在合适的根
            else
            {
                js = false;//是否找到根
                while (!js)
                {
                    //如果该区间长度在精度范围内,则返回区间中值为根
                    if (System.Math.Abs(z1 - z) < eps)
                    {
                        result.Add((z + z1) / 2.0);
                        z = z1 + h / 2.0;
                        y = func(z);
                        js = true;
                    }
                    else
                    {
                        //尝试取区间中值为根
                        z0 = (z1 + z) / 2.0; y0 = func(z0);
                        //如果中值在取值范围内
                        if (System.Math.Abs(y0) < eps)
                        {
                            result.Add(z0);
                            js = true;
                            z = z0 + h / 2.0;
                            y = func(z);
                        }
                        //缩小取值区间
                        else if (y * y0 < 0.0)
                        {
                            z1 = z0;
                            y1 = y0;
                        }
                        //缩小取值区间
                        else
                        {
                            z = z0;
                            y = y0;
                        }
                    }
                }
            }
        }//end else
    }//end while
    return result;
}

我们来测试下面的方程,区间取为[-4,4]

使用如下的测试代码:

static void Main(string[] args)
{
    List<double> res = Bisect(Func,0.000001,0.1,-4,4,4);
    foreach (double r in res)
        Console.WriteLine(r);
}

public static double Func(double x)
{
    return 100 * x * x * Math.Sin(x) - 50 / x + 10 * x * x * x - 9 * Math.Pow(x, 4);
}

可以得到结果为:

-0.827932357788083
-3.81469724037968E-07
0.862653732299807
2.71254234313965

Algorithm, C-Sharp, Math

实根, 对分法, 数学, 方程, 非线性方程

我为什么使用C#

Apr 8th 2010

By: Catouse

No comments
为了不至于产生误解,开始我要说的是我不大喜欢C#,我更倾向于C++.很多人在说,站在更高的角度,没有意义去谈论任何语言的好坏.我倒认为是各有所爱吧,或者更多的是生活所逼.事实上是我在更多的使用C#.我只想说明在博客中为什么更多的在使用C#.

其实不管你是否一致在思考算法或者AI,总有些时候你得把你的一些新奇想法很快的做成桌面软件,实际上,我完成这个想法的就是使用C#,根据我对C#的了解,我认为有以下理由让我选择C#来为AI和图像算法做Windows可视化演示或应用
1. 简单的语法: 有一定语言基础的都能很快的入门
2. 代码清晰整洁: 完全面向对象,语法综合了很多语言的优点,而且加入了几个很好的特点(比如属性,委托等),可以把他当做另一种伪代码,易于表达算法,转换成为其他语言也很方便,对于函数的输出参数和引用参数要求注明out 和ref,表达更清晰.
3. 数据类型丰富: 包括常见的enum,bool,decimal等,当然还支持泛型.
4. 允许使用指针:肯定有时候需要用到指针,C#允许你有限制的使用
5. 自动内存管理:这个无疑能减少内存管理操作对你的程序逻辑造成的干扰
6. 丰富的基础库支持:MS已经提供了很强的基础类库,特别是GDI+可以方便处理各种图形图像.
7. 支持DirectX:很方便快速的创建3D视窗,仅仅牺牲一点点性能,如果不做游戏单纯研究算法和AI的话是值得的.
8. 对Windows支持很好:内置对组建对象模型（COM）和WindowsAPI的支持.基于组件模型,可以混合C++等其他语言完成程序
9. 其他的还有完整的异常处理机制,对web的支持等,不过我这里只考虑给Windows可视化演示或应用带来的好处.
如果程序要求高性能,我想还可以选用C++,毕竟C#依赖的.net并没有内联函数机制和析构函数.
C-Sharp

C#, 编程
使用C#Lambda进行泛型参数的数值运算

Mar 21st 2010

By: Catouse

No comments
做天写了一个矩阵运算类,我尝试了用泛型来实现,很明显泛型能在我给我的矩阵应用带来更多的选择.矩阵运算在游戏及其AI运用很广泛.不过后来我一想,还是没有必要运用泛型实现.不过昨天的经历让我有兴趣和大家讨论一下C#泛型参数的值运算问题:泛型参数带来的好处的同时也不能忽视其局限性.

泛型参数应用的一个很老的例子就是交换两个数的值了,比如下面的方法实现了两个任意值类型参数的值交换:
```
public void Swap(ref T a, ref T b)
{
    T temp = a;
    a = b;
    b = temp;
}
```
当然此方法不能应用于引用类型参数,为了防止泛型编程过程中,不恰当的调入应用参数增加隐性bug,C#对泛型增加了参数约束.在C#中参数约束是通过where关键字实现的,关于更多的泛型参数约束请参考MSDN
上面的方法中参数a,b肯定只能是值类型,所以修正程序第一行如下:
```
public void Swap(ref T a, ref T b) where T:struct
```
现在我们讨论的不是泛型的概念,不妨考虑一下以下问题:
1. 能否通过泛型实现一个方法来返回所有参数中最大的那个呢?
2. 能否通过泛型实现一个方法来得到一个泛型参数的倒数呢?
3. 能否计算方法中泛型参数的绝对值,或者取负呢?
4. …
就拿第一个问题吧,很可能我们会写出下面的代码:
```
public T GetTheGreater(T a, T b) where T:struct
{
    if(a>b)
        return a;
    else
        return b;
}
```
世界上的事情总是有倒霉的一半,程序的第三行不会通过编译检查,已经很明了了,泛型参数是不能进行逻辑判断运算,至少不能进行大于的比较运算.实际上包括所有的逻辑运算和算术运算.由此可见上面的问题在C#里面几乎是不可解决了.
不过我们不要忘了倒霉的一半不是全部,C#3.0引入了表达式树,使得不同类型的值进行运算成为可能.表达式基类Expression提供了丰富的表达式运算方法来帮我们达到目的.我有点迫不及待的给出几行代码,下面是运用表达式树比较两个泛型参数的大小:
```
///
/// 判断a是否小于b
/// 注意参数顺序,判断的是前一个参数是否小于后一个参数
///
public static bool LessThan(T num1, T num2) where T:struct
{
    //参数表达式树节点1
    ParameterExpression para1 = Expression.Parameter(typeof(T), "left");
    //参数表达式树节点2
    ParameterExpression para2 = Expression.Parameter(typeof(T), "right");
    //两个参数节点构成关系为比较大小的二叉树节点
    BinaryExpression expsLessThan = Expression.LessThan(para1, para2);
    //定义lambda表达式
    Expression> exps = Expression.Lambda
        >(expsLessThan, new ParameterExpression[] { para1, para2 });
    //转化为匿名函数指针
    Func myFunction = exps.Compile();
    //返回执行结果
    return myFunction(num1, num2);
}
```
关于表达式树的更多概念请参见System.Linq.Expressions 命名空间这里不再重复MSDN的内容
当然上面的是逻辑判断的例子,如果是算术运算呢?我们只要改变对Expression代理的封装就是.
```
///
/// 将两个泛型参数做加法运算
///
public static T Add(T num1, T num2) where T:struct
{
    //参数表达式树节点1
    ParameterExpression para1 = Expression.Parameter(typeof(T), "left");
    //参数表达式树节点2
    ParameterExpression para2 = Expression.Parameter(typeof(T), "right");
    //两个参数节点构成关系为求和的二叉树节点
    BinaryExpression expsAdd = Expression.LessThan(para1, para2);
    //定义lambda表达式
    Expression> exps = Expression.Lambda
        >(expsLessThan, new ParameterExpression[] { para1, para2 });
    //转化为匿名函数指针
    Func myFunction = exps.Compile();
    //返回执行结果
    return myFunction(num1, num2);
}
```
上面的都是二元运算,如果是一元运算呢?有点点不同就是注意对lambda表达式的中的代理参数封装,还有就是二叉树节点为UnaryExpression(包含一元运算的表达式),而不是BinaryExpression(包含二元运算的表达式)
下面是一个求负的方法
```
///
/// 求给定泛型参数的负数
///
public static T Negate(T num) where T:struct
{
    //创建一个参数表达式树节点
    ParameterExpression para1 = Expression.Parameter(typeof(T), "left");
    //构成一个求负的一元表达式
    UnaryExpression expsNegate = Expression.Negate(p1);
    //定义lambda表达式
    Expression> exps = Expression.Lambda
        >(expsLessThan, new ParameterExpression[] { para1});
    //转化为匿名函数指针
    Func myFunction = exps.Compile();
    //返回执行结果
    return myFunction(num);
}
```
有了上面三个例子,基本上所有的逻辑运算和算术运算都不是问题了,不过我们如果在定义的泛型类中一个个定义这些方法肯定很别扭,不仅破坏泛型类本身的聚合性,而且重复写也麻烦,所以我们可以将这些运算方法封装为另外一个泛型类,比如取个名字就叫 CalculateGeneric,实际上我就是这么叫的.
```
///
/// 泛型数值类型计算类
///
public static class CalculateGeneric where T:struct
{
    /// 返回此数值泛型的0值
    public static T Zero;

    /// 实现两个泛型变量的相加算术运算
    public static T Add(T num1, T num2);

    /// 判断两个泛型变量值是否相等
    public static bool Equal(T num1, T num2);

    /// 取倒数
    public static T Reciprocal(T num);

    ///更多丰富的计算类型....
}
```
你可能会注意到上面的类中有一个访问器是返回0值,另外你还可能注意到取倒数的方法.所以我还要补充一个问题就是怎样解决泛型参数常量1和0的表示,比如我要通过泛型方法得到不同类型数值的倒数,我就要得到数值1.Expression类也没有提供取倒数的表达式运算方法.
我还没有很好的办法来解决这个问题,不过我临时是这样来解决的:
- 通过泛型代码中的默认关键字default 来变相获取0值,这有泛型参数如果为值类型,则默认值为0
- 将一个不为0值的泛型参数和自身做除法运算则得到数值1
我不能保证上面的解决方法适合所有情况,欢迎大家提出错误或者分享你的解决方案.
另外说明,不能乱用这种方法来对泛型操作,毕竟这样修改了泛型的本意.(2010-4-4 15:57:01更新)
C-Sharp

C#, Lambda, 泛型, 表达式树
- 1
- 2
- >

Unlock Particle

追逐与拦截

追逐

拦截

模拟程序下载

亦歌mini

制作亦歌mini

到底有多少条路?

寻找非线性方程实根(4)-Aitken迭代加速

寻找非线性方程实根(3)-试位法

寻找非线性方程实根(2)-牛顿迭代法

寻找非线性方程实根(1)-对分法

我为什么使用C#

使用C#Lambda进行泛型参数的数值运算

标签

分类

最新日志

功能