博文
解线性方程组的一些方法(2007-05-23 15:04:00)
摘要：第一大类是直接法，理论基础是高等代数里的矩阵和行列式，也是众所周知的消元法。
x+y=a
x-y=b
小学就开始会解了，所以消元法在每个人心里都很明白，计算机算法也相对简单和容易理解，有完全主元消去法，列主元消去法，高斯若当消去法（消去对角线下方元素的同时消去上方元素）等。
高斯列主元素消去法实现：
//高期列主元素消去法，ab为{A,b}增广矩阵
void gauss1(CMatrix &ab)
{
int h,w;
ab.size(h,w);
if(h+1!=w)//要求n阶方阵
return;
int n=h;
int i,j;
for(i=0;i<n;++i)
{
//从a[i,i]到a[n,i]找出最大元素所在行
int max=i;//max指向最大列主元素所在行
for(j=i+1;j<h;++j)
{
if(fabs(ab.elem(j,i))>fabs(ab.elem(max,i)))
max=j;
}
ab.swap(i,max);//交换行
if(ab.elem(i,i)==0.0)//det=0，计算停止
return;
//消元
for(j=i+1;j<h;++j)
{
ab.pt(i,j,-(ab.elem(j,i)/ab.elem(i,i)));
}
//将a[i,i]化成1.0
ab.mul(i,1.0/ab.elem(i,i));
}
&n......
GL的简单封装类与游戏编程基础(2007-05-17 23:25:00)
摘要：用MFC习惯了，所以想把GL的一些东西封装成类，放在MFC里一起搭应用程序。
GL当初是被设计成与硬件及平台无关的专业3D绘图API，也就是说用GL的时候，你可以把你正在用计算机这件事忘了，你是在进行艺术创作！
虽然MS不太情愿支持GL，但从WIN NT开始也正式把GL加入了WIN32 API中，在一组dll中实现，所以使用起来也还方便。
WINDOWS下GL实现的基本原理（其它平台的不知道），因为有GDI/GDI+，所以GL在这里显得有些像异类，在GDI下画图是使用的图形设备上下文（描述表）DC，而在GL里是渲染描述表RC，所有的gl*绘画函数都是在一个当前RC上进行的，绘制完之后用WIN API SwapBuffers(HDC)交换缓存到DC，进行图形的显示。
class CGLFrame;可以看成是对RC的封装，所以可以认为它就是GL本身。
它的构造函数不做任何事情，将产生一个对象，未做初始化。初始化要在CreateRC()中完成。
BOOL CGLFrame::CreateRC(CDC *pdc, CRect &rect, BOOL bMWA);
pdc : 一个CDC在堆上的对象，可以是CClientDC等，在析构函数中有delete pdc的操作。
rect : 是初始的显示宽度
bMWA : 标识是否在多窗口应用下绘画，默认为FALSE。
从这之后，将由CGLFrame对象托管RC资源，及进行绘图操作（绘图还是用gl*函数，只是放在特定的地方）
举个例子，在基本对话框应用程序下使用CGLFrame
1，包含必要的头文件和库文件（或者直接把glframe.h和glframe.cpp添加到工程）
2，从CGLFrame下继承自己的CMyFrame
3，在CSampleDlg中创建CMyFrame的对象，m_glfrm
4，在CSampleDlg::OnInitDialog()里进行RC的创建：
CClientDC *pdc=new CClientDC(this);
CRect rect;
GetClientRect(&rect);
m_glfrm.CreateRC(pdc,&rect,FALSE);
5，在需要进行渲染的地方调用：m_glfrm.Render();（或者Rend......
VC实现线程同步（或异步）(2007-04-24 22:07:00)
摘要：操作系统里讲的的进程同步，用的是信号灯，PV操作，P操作看成是申请资源，V操作是看成是交还资源，资源可以有很多解释，比如时间，空间，数据等，而信号量可以看成是资源数目。
在WIN32里多进程用得少，因为进程建立很费劲，分配虚拟内在是其中一个原因，取而代之的是线程，线程可以看成是小进程，是一个进程中活的东西，进程是死的，占有了内存和得到了一些系统资源后就死了，只有启动主线程的时候才活起来，主线程的地位相当重要，主线程一结束进程也就被OS踢出去了。进程间也可以通信，当然要复杂一些，因为地址空间完全不同，用得多的有管道等。
1，互斥对象
一个互斥对象，维护一组数据：当前线程，使用计数，受信状态。PV操作相当于：WaitForSingleObject()和ReleaseMutex()，ReleaseMutex()不一定会将Mutex Release掉，如果计数为1，才会将线程ID改为0，并改受信状态为signed。建立的语句是CreateMutex，释放资源是CloseHandle，进程退出的时候也会自动释放。
2，事件对象
事件对象分两种，一种是人工重置的(ManualReset)，影响到WaitForSingleObject()的时候是否由系统设为unsigned，这里有个值得思考的情况：
a,When "Non-ManualReset" use
WaitForSingleObject(event1);
b,When "ManualReset" use
WaitForSingleObject(event1);
ResetEvent(event1);
他们是不是等价的呢？看起来，如果人工重置的，在WaitForSingleObject()后紧接着就ResetEvent()，那不就是系统自动的了吗？
这是不等价的，原因是，在调用完WaitForSingleObject()后，在进入ResetEvent()之前，是有可能被系统的线程调度程序给设成‘就绪’状态，其它的线程执行，这时候又是signed，所以就出问题了。
3，临界区段
临界区程序就是有线程在处理相同的数据，如果线程都在跑各自不同的数据，那异步是完全没有问题的，如果跑相同的程序，就可能有问题，相当于线程撞在了一起，所以叫临界......
FFT乘法和高精运算库(2)(2007-04-14 16:43:00)
摘要：
目前实现了，加，减，乘，乘方，阶乘和计算菲数，速度没有大幅度提高，唉，也没那么多时间做了，先放一放。（除法做得不好，太慢了，慢到不能用）
最后一次提升的快一些，因为我想到两个实数序列可以合并在一起，做为一个复数的实部和虚部，这样一起做FFT会快一些。推导很简单，公式是：
x(t),y(t)为N点实序列，设X(t)=DFT[x(t)] , Y(t)=DFT[y(t)]，记w(t)=x(t)+iy(t)，W(t)=DFT[w(t)]，于是由DFT的线性性质，有W(t)=X(t)+iY(t)，但是不一定就是W(t)的实部和虚部，为了由W(t)得到X(t)和Y(t)，是计算X(t)=(W(t)+W*((N-t))N)/2和Y(t)=(W(t)-W*((N-t))N)/2i。
这样一来，做一次乘法就只需要2次fft。
我的机子比较慢，测了几组数据，结果是：
Factorial Function Test (1.0)
_______________________
n! cost time (s)
1k! 0.028163
10k! 0.856568
20k! 2.215239
40k! 6.278020
80k! 16.574058
Test Date\2007\04\11
Factorial Function Test (1.01) [增加快速地址变换]
_______________________
n! Cost Time (s) Approximations
1000 0.025191 4.023872600770937735437 E 2567
10000 0.735035 ......
FFT乘法和高精运算库(1)(2007-04-11 20:28:00)
摘要：不准备多写，这些东西网上可以搜出一箩筐来。
高精运算库的构想，是可以快速的应付巨数的运算，包括加，减，乘，除等。比如现在的int是16字节，long32字节，LONGLONG64字节，再大一些就要扩字了，于是就不能用原来汇编给我们用的指令了，需要重新定义运算。
加减很容易，小学加减法，跟手工算一样的，复杂度是O(n)，n表示数据的长度。
乘法如果直接像手工算一样做，复杂度是O(n*n)的，FFT乘法是将数看成多项式：
P1(x)=a0+a1x+a2x^2+...+anx^n，如果取ak在0到9之间，且x取10，那它就表示一个十进制数，如果再用另外一个多项式P2(x)与它相乘，那结果和它所表示的数相乘是一样的数值。
多项式乘法其实质是做两个系数序列的卷积，而FFT正是对这样的卷积做从时域到频域的变化，FFT的本质也是DFT，离散富里叶变换，因为有卷积定理：
如果h(t)=x(t)*(y(t)，且H(s)=DFT[h(t)]，X(s)=DFT[x(t)]，Y(s)=DFT[y(t)]，那么有，H(s)=X(s)Y(s)
在频域的序列只需要做乘积，就是对应项乘对应项，是O(n)复杂度，因为FFT是一个DFT的快速算法，复杂度在O(nlogn)，所以可以得到同样复杂度的FFT乘法，形式表示成：
h(t)=IFFT[ FFT[x(t)]FFT[y(t)] ]
IFFT是快速富里叶反变换，可以转换成FFT，所以一个乘法的时间是3个FFT加一个线性乘积运算，因此也是O(nlogn)。
开始动手做FFT乘法程序之前，先实现一个FFT算法模块，然后要考虑的事有：1，复数如何表示？用float还是double型存实型数？2，进行运算的时候选多大的基？
因为DFT的运算关系到复数，复数好办，用两个实数表示就行了，实数的选取，精度够不够，如何表示精度，误差怎样控制？
如果基是B，参与运算的数最长有N，则一种最极端的情况是，全部取到B-1（测试的时候如果基10，就全9，基100就全99进行测试），做线性卷积回来最大的可能结果是N(B-1)^2，这里要考虑浮点数的精度和需要达到的巨数的长度，很矛盾的选择，一方面想基越大越好，这样大数存起来比较节省，但是基一选大了，精度就会下降，可以实验一下。我实验的结果是float型绝对不够，可能算不是很大的数都错几位，double可以......
简单方法算pi和e，计算到小数点后面一万位(2007-03-29 15:20:00)
摘要：简单方法算pi和e，计算到小数点后面一万位
1， 计算pi(圆周率)
算pi的公式非常之多，下面是几个有趣的：
pi/4=1+(1*1/(2+(3*3/(2+(5*5/(2+…)))))) [布朗克连分式]
2/pi=(sqrt(2)/2)*(sqrt(2+sqrt(2))/2)*(sqrt(2+sqrt(2+sqrt(2)))/2)*… [韦达恒等式]
pi/4=(2/1)*(2/3)*(4/3)*(4/5)*(6/5)*(6/7)*(8/7)*(8/9)*… [华里达表达式]
pi*pi/6=1/1*1+1/2*2+1/3*3+… [欧拉等式]
虽然这些连分式、无穷级数、无穷乘积都收敛到pi或和pi相关的数值，但是收敛速度却各不相同，收敛和收敛速度是两个完全不同的概念。
现在PC机上很有名的SuperPi，采用了Gauss-Legendre算法，这个公式每迭代一次将得到双倍的十进制精度，比如要计算100万位，迭代20次就够了。虽然收敛速度是超线性的，但是随着展开的数据位数越来越高，迭代一次的代价会越来越大，这关系到高精度算法，实现起来相当复杂。高精度，这是个值得思考的问题。
在这里采用一个简单的公式计算，Machin公式：pi=16arctg(1/5)-4arctg(1/239) （可以把这个表达式输入到google上，然后google会告诉你结果是3.1415926）
下面从arctg(x)的展开出发，简单讨论一下这个公式。
可以从等比数列的极限开始：设|x|<1，1+x+x^2+x^3+…=1/(1-x)，等式左边是无限项，如果只取有限的n项，结果会是什么呢？这关系到一个余项的的问题，对右边的式子进行泰勒展开，有泰勒余项，于是：1/(1-x)=1+x+x^2+…+x^n+ x^(n+1)/(1-eps)^(n+1) （1），eps在0到x之间，最后的那个余项是进行误差分析的基础，也是决定收敛速度的式子。（1）只展开到有限项，于是对它两边进行代换得到，
1/(1+x^2)=1-x^2+x^4-…+(-1)^n*x^(2n)+ x^(2n+2)/(1+eps*eps)^(n+1)......
我写的智能指针auto_ptr(2007-03-20 17:37:00)
摘要：为什么要用这个auto_ptr，一般的C语言指针不够用吗？如果C++里没有new，那一般的指针就够用了，现在的代码都像这样：
int *p=new int[100];
//使用p
delete[] p;
使用p的时候，如果突然出了问题，比如丢出异常，就会中止程序，而不能运行delete，造成内存泄漏，所以在使用的时候，经常要做很多判断，比如
if(p)
{
...
delete[] p;
}
if(XXX)
{
delete[] p;
throw(xx);
}
所以，拿到内存容易，但责任就大啊，所以整个代码被整个乱七八糟，而且程序员还要保持清醒的头脑，一不小心就。。。
STL的auto_ptr就是为了解决这个问题，做的一个封装，在指针的运算过程中，比如*,->，发生错误，丢异常，并在析构的时候delete。
把VC6里的auto_ptr复制下：
template<class _Ty>
class auto_ptr {
public:
typedef _Ty element_type;
explicit auto_ptr(_Ty *_P = 0) _THROW0()
: _Owns(_P != 0), _Ptr(_P) {}
auto_ptr(const auto_ptr<_Ty>& _Y) _THROW0()
: _Owns(_Y._Owns), _Ptr(_Y.release()) {}
auto_ptr<_Ty>& operator=(const auto_ptr<_Ty>& _Y) _THROW0()
{if (this != &_Y)
{if (_Ptr != _Y.get())
{if (_Owns)
&nbs......
单纯形法性规划问题求解器(2007-03-19 22:09:00)
摘要：
我花了一天时间写的，为了做作业，不用用笔在纸上算了。
简单写了一个分析字符串的东西，没有专门的考虑词法分析什么的，只从中间提取变量名和参数表，有一个符号表功能，矩阵运算是原来数值分析实习时写的CMatrix。
LPSolver 单纯形法线性规划问题求解器 v0.1 rickone
[实现功能]
1,直接单纯形法
2,大M法,M近似
3,两阶段法
[输入格式]
MAX或MIN(目标函数=目标函数表达式)
{
约束方程1;
约束方程2;
...
}
1,目标函数变量为第一个扫描到的变量标识
2,线性表达式的每一项:<系数><变量名>
3,约束形式:<= = >=
=不能写成==
4,符号'='为方程左右的边界标识符
5,符号';'为方程结束标识符,最后一个也不能省
6,隐含的约束条件有,所有的变量>=0
[例子]
MAX(z=x1+x2+x3)
{
x1-x2<=100;
2x1-1.5x2>=10;
x1+3x3=50;
}
QQ:85104865
email to: rickone@sina.com
date:2007/03/19
VC6源码（部分，仅含主窗口的代码，分析字符串和LP算法，Matrix的只给个接口说明吧）：
//: Matrix.h
#if !defined(AFX_MATRIX_H__83023DF6_28C2_4C65_A12D_9DAAF6624E84__INCLUDED_)
#define AFX_MATRIX_H__83023DF6_28C2_4C65_A12D_9DAAF6624E84__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
// Matrix.h : header file
//
////////////////////////////////////////////////////////////////......
VC小结(1)(2007-03-16 23:18:00)
摘要：MSDN里面有一些专题值得读一下，至少知道MFC的目的和一些方法或者手段。随便乱写一些，如果以后发现还有价值的话就整理。
1）MFC是对平台SDK的一个大封装。
学了C++，还不知道C++能干嘛，不知道就算能干这些，又有什么用，甚至不知道为什么要设计类，为什么要封装。
WINDOWS里的资源是用句柄表示的，句柄这个词不知道是哪个中国IT菜手翻译的，handle干嘛要这么翻译？它的意义很明显嘛，处理，为什么要处理？有人说，它是微软要隐含内部实现，因为它是商业软件嘛，我觉得不是，这不是根本原因，它原本的目的还是为了代码的向后兼容和可复用性。比如最重要一种资源，文件，它是和具体设备相关的，但文件操作只对一个文件的HANDLE进行处理，就是把它的定义和处理分开，C语言里的FILE也是一样的道理。各种各样的资源统一处理，在系统里统一表示，这样系统就会有条不紊地工作。也算是一个小的封装吧，具体实现和外部代码的分开，封装。于是有了SDK编程。
MFC封装在外面，更大的封装，它是为了让程序员把搭建一个复杂的WIN32程序，从设计那些复杂的实现中解放出来，把开发重点放在软件的数据结构和算法上。由于SDK封装得低，所以可以认为那些handle本身就是资源本身，可以这样认为。再在这之上进行面向类的封装，就是MFC。
有人说懂得了继承，才真正懂得了面向对象，或者C++。C++的目标或许也是这样吧，虽然语言本身没告诉我们它的目的是什么，做为了个成熟的类库，比如MFC，我们不仅仅是简单的利用它的一些功能调用，比如用CCommonDialog，而关键是选择合适的类继承下来，设计自己的子类，来实现整个软件的功能。
在面对各种各样的MFC中的类，要记住一点，类生成的对象，本身并不代表资源本身，比如CEdit并不是EditBox，它们之间可以有联系，但这个联系可以人为的剪断，对象只是一个从操作到资源的一个纽带。这也是为什么它有构造函数，却要用::Create()创建的原因。
2）弄清消息分发的过程。
消息的机制是为了让WINDOWS变迟顿，让它‘慢’下来，只有你‘叫’它做事它才做，由主动工作变为被动工作。有时候发送消息本身也可以看成消息处理本身。MFC对消息的处理封装得可就复杂了，不是非要弄得非常清楚才行，要知道消息被MFC丢来丢去的先后顺序，比如一个按钮的COMMAND响应可以给CW......
字牌游戏开发计划(2007-02-25 01:31:00)
摘要：没有代码。
我想起原来看的一集《卫斯理》的故事里面的一个家伙，他是卫斯理的朋友，卫斯理认识的朋友都是厉害角色，他的厉害之处是他的推理能力，他是天生的侦探，可惜没有做成侦探，于是他就天天在家里意识犯罪，什么是意识犯罪？在几年里他每天都想一个犯罪方案出来，并进行非常详细的计划，比如抢劫，他写出流程和计划，然后放在那里，当然他从未犯过罪，只是过把瘾而已，并乐此不疲，卫斯理都为他的计划之周密而惊叹。
这几天走亲戚拜年，茶饭之余从老到小就只知道打牌，麻将啊，扑克啊，昏天暗地，我看他们打的时候就想要是做个牌类游戏该如何着手设计，哦，意识犯罪而已。
我们这地方比较流行字牌，因为玩起来特刺激，啥是刺激？打一块钱一个码，一天下来估计可以输上好几百块~不比麻将，堆着麻烦，打起来也随意性大，输赢都有，一点都不刺激~
字牌和麻将很相似，但是规则上会复杂很多，牌是纸做的，实际中4人一起玩，但拿牌的只有3个，3个人摸牌，比4个人摸牌容易摸一些，而且上下吃也容易些，比如，你和你上家的牌大部分都能吃，所以近似2/3的牌可以吃。
怎样着手设计呢？或者说计划一下。
首先是数据结构啦，从最底层开始。编码，牌如何用数字表示，原则，越简单越好，统一编码，比如1到10表示万，11到20表示条，统一一致编码。这时你会觉得是不是要做成复合形式的，就像MAC地址是平面的，而IP是分段的，在你还不知道这样编有什么好处的时候，别乱编，比如你觉得用二维数组表示更简单，但这样的操作是不是真的简单还不知道，有没有更麻烦的时候呢？或许有，因为以后的功能是应该可以扩充的。
有了牌的定义，然后就有桌面上的牌和手上的牌两类，桌上的牌在实际规则中或许比较复杂，但程序中很简单，只要是随机分发就行了，定义成一个可随机取的队列，类似代码如下：
typedef int SPoker; // 牌的定义
class CPokerQueue
{
SPoker poker[80];
CPokerQueue(); // 在这里顺序填入应有的所有牌
public:
SPoker hand(); // 摸牌
......