博文
[共享]单双精度浮点数的IEEE标准格式(2005-12-17 14:20:00)
摘要：目前大多数高级语言（包括C）都按照IEEE-754标准来规定浮点数的存储格式，IEEE754规定，单精度浮点数用4字节存储，双精度浮点数用8字节存储，分为三个部分：符号位、阶和尾数。阶即指数，尾数即有效小数位数。单精度格式阶占8位，尾数占24位，符号位1位，双精度则为11为阶，53位尾数和1位符号位，如下图所示：
单精度浮点数存储格式
s
指数
尾数
31 30 23 22 0
双精度浮点数存储格式
s
指数
尾数
63 62 52 51 0
细心的人会发现，单双精度各部分所占字节数量比实际存储格式都了一位，的确是这样，事实是，尾数部分包括了一位隐藏位，允许只存储23位就可以表示24位尾数，默认的1位是规格化浮点数的第一位，当规格化一个浮点数时，总是调整它使其值大于等于1而小于2，亦即个位总是为1。例如1100B，对其规格化的结果为1.1乘以2的三次方，但个位1并不存储在23位尾数部分内，这个1是默认位。
阶以移码的形式存储。对于单精度浮点数，偏移量为127（7FH），而双精度的偏移量为1023（3FFH）。存储浮点数的阶码之前，偏移量要先加到阶码上。前面例子中，阶为2的三次方，在单精度浮点数中，移码后的结果为127+3即130（82H），双精度为1026（402H）。
浮点数有两个例外。数0.0存储为全零。无限大数的阶码存储为全1，尾数部分全零。符号位指示正无穷或者负无穷。
下面举几个例子：
单精度浮点数
十进制
规格化
符号
移阶码
尾数 &n......
最短带权路径问题的解法::Dijkstra & Floyd(2005-10-22 16:06:00)
摘要：最短带权路径问题的解法::Dijkstra & Floyd
在一个网络中，如果两个结点之间有直接的因果关系，则这两个结点直接连通，在连接
两个结点的弧上标上它的代价或权，值得注意的是这样的代价不一定是对称的，即A到B
的代价不一定等于B到A的代价，实际问题中以行船为例，有顺水和逆水的区别。在图Ｇ
中，给出两个结点求这样一条最短的路径，使经过这条路径上的代价之和最小，这就是最短
路径问题。
如果所有弧上的权都相等，则问题退化为求两个结点间的一条路径使经过的中间结点最
少。比如在一个城市的交通网络中，乘客关心的可能只是旅途中中转的次数，只希望转更少
次数的车。对于这样的问题，运用ＢＦＳ对图进行层次遍历，可以在O(n)的时间复杂度上
完成搜索，考虑到ＢＦＳ的层次遍历性质，不难理解，在此不讨论。
考虑到带权的有向图（无向图可看成特殊的有向图），如何求最短路径呢？
１、 Dijkstra算法
Dijkstra是最早提出这个算法的大牛：）。这是图论中非常有名的一个算法。
图采用邻接矩阵的形式描述，M[i][j]表示结点i到结点j间的代价，如果没有直接因果
关系，则为无穷大，计算机中可以用一个很大的数据代替。后面的Floyd算法同样这样描述。
差点忘了，dijkstra算法只能求出从结点i到其它各结点的最短路径。算法引入这样两
个集合S和Ｔ，Ｓ是那些已经确定了到Ｉ结点的最短路径的结点，在计算过程中为什么可
以确定某些结点已经到达了最短的要求了呢？后面再讲。Ｔ为全集Ｕ和Ｓ的差集，即那些还
未确定最短路径的结点。而且Ｓ的初值是{i}，Ｔ的初值是Ｕ-{i}。另外再引入一个标记数组
Ｄ[N]，其中在某一步D[k]表示当前从i到k的较短路径，D[k]的初值为M[i][k]，整个算法
过程如下：
１、 在Ｔ中选择一个Ｄ[k]最小的结点k，将k并入Ｓ，并从Ｔ中去掉，如果Ｔ为｛｝则
转到３；
２、 用k结点和Ｔ中其余结点进行一遍比较，如果D[i]>D[k]+M[k][i]，则用D[k]+M[k][i]
取代原来的Ｄ[i]，重复１；
３、 算法结束，此时Ｄ[k]中保存的就是从Ｉ到k结点的最......
带通配符*,?的模式匹配(2005-10-03 22:48:00)
摘要： 传统的模式匹配都是：串T匹配串S，如果存在S的子串S'==T。
现在要求的是模糊匹配，串T中含有特殊符'*'和'?'，'*'匹配任意字符串或空串,'?'匹配任意一个字符，如'*Rick'匹配任意以'Rick'结尾的串和'Rick'串，'?ick'匹配任意以'ick'结尾且长度为4的串。
输入：
1、带特殊符的T串
2、一系列测试串S[i]
输出：
如果S[i]匹配T输出.T.，否则输出.F.
１、'?'很好处理，只要在原有的定位函数中加一点点就行：
int index(char *s,char *t,int pos)
{
int i=pos,j=0,lens=strlen(s),lent=strlen(t);
while(i......
最小二乘法线性回归(2005-09-23 21:28:00)
摘要：在现实中经常遇到这样的问题，一个函数并不是以某个数学表达式的形式给出，而是以一些自变量与因变量的对应表给出，老师讲课的时候举的个例子是犯罪人的身高和留下的脚印长，可以测出一些人的数据然后得到一张表，它反应的是一个函数，回归的意思就是将它还原成数学表达式，这个式子也称为经验表达式，之所以叫经验就是说它不完全是实际中的那样准确，是有一定偏差的，只是偏差很小罢了。
最小二乘法
设经验方程是y=F(x)，方程中含有一些待定系数an，给出真实值{(xi,yi)|i=1,2,...n},将这些x,y值代入方程然后作差，可以描述误差：yi-F(xi)，为了考虑整体的误差，可以取平方和，之所以要平方是考虑到误差可正可负直接相加可以相互抵消，所以记误差为：
e=∑(yi-F(xi))^2
它是一个多元函数，有an共n个未知量，现在要求的是最小值。所以必然满足对各变量的偏导等于0，于是得到n个方程：
de/da1=0
de/da2=0
...
de/dan=0
n个方程确定n个未知量为常量是理论上可以解出来的。用这种误差分析的方法进行回归方程的方法就是最小二乘法。
线性回归
如果经验方程是线性的，形如y=ax+b，就是线性回归。按上面的分析，误差函数为：
e=∑(yi-axi-b)^2
各偏导为：
de/da=2∑(yi-axi-b)xi=0
de/db=-2∑(yi-axi-b)=0
于是得到关于a,b的线性方程组：
(∑xi^2)a+(∑xi)b=∑yixi
(∑xi)a+nb=∑yi
设A=∑xi^2,B=∑xi,C=∑yixi,D=∑yi，则方程化为：
Aa+Bb=C
Ba+nb=D
解出a,b得：
a=(Cn-BD)/(An-BB)
b=(AD-CB)/(An-BB)
C++程序：
#include
#include
void main()
{
double x,y,A=0.0,B=0.0,C=0.0,D=0.0,delta;
int n;
cin>>n;
for(int i=0;i<n;++i)
......
马踏棋盘的贪心算法(2005-08-25 12:20:00)
摘要：我的作业，凑合一篇吧……
C语言课程设计实验报告
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在８×８方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
１、 输入初始位置坐标x,y；
２、 步骤 c:
如果c>64输出一个解，返回上一步骤c--
(x,y) ← c
计算(x,y)的八个方位的子结点，选出那此可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然（２）是一个递归调用的过程，大致如下：
void dfs(int x,int y,int count)
{
int i,tx,ty;
if(count>N*N)
{
output_solution();//输入一个解
return;
}
for(I=0;i<8;++i)
{
tx=hn[i].x;//hn[]保存八个方位子结点
ty=hn[i].y;
s[tx][ty]=count;
dfs(tx,ty,count+1);//递归调用
......
产生任意范围内的等概率随机数(2005-08-17 21:34:00)
摘要：C提供的标准随机函数是rand()，返回0~RAND_MAX，共RAND_MAX+1个随机数，如果我需要更大的随机数范围应如何做？
试设计：
long random(long n);返回0~n-1间的等概率随机数
分情况讨论
如果n<RAND_MAX+1，大可以用rand()%n的方法做，但这样做也并不能满足等概率性，设r=RAND_MAX%n，得到0~r的概率要稍大一些，尤其在n较接近RAND_MAX时，当n较小时影响可以忽略。
if(n<=RAND_MAX)
{
r=RAND_MAX-(RAND_MAX+1)%n;//尾数
t=rand();
while(t>r)t=rand();
return t%n;
}
如果n>=RAND_MAX+1，我的想法是分段抽样，分成[n/(RNAD_MAX+1)]段，先等概率得到段再得到每段内的某个元素，这样分段也类似地有一个尾数问题，不是每次都刚好分到整数段，一定或多或少有一个余数段，这部分的值如何选取？
选到余数段的数据拿出来选取，先进行一次选到余数段概率的事件发生，然后进行单独选取：
else
{
r=n%(RAND_MAX+1);//余数
if(happened((double)r/n))......
满足任意精度的概率事件发生器(2005-08-16 21:40:00)
摘要：#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#define MinProb 3.05185094759972e-5
bool happened(double probability)//probability 0~1
{
if(probability<0)return false;
if(probability<MinProb)
return rand()==0&&happened(probability/MinProb);
if(rand()<=probability*RAND_MAX)
return true;
return false;
}
MinProb是理论上的最小发生概率，为什么会这样，因为计算机是离散的，它永远只能得到有限范围内的随机离散数。
bool happened(double probability);
是按概率probability发生的随机事件发生器，如当probability=0.5时，将等概率得到真或者假，当为其它值时，将按probability的概率得到真，以1-probability的概率得到假。
如果probability比较大，MinProb是足够精确的，如0.5和0.5000001是有足够精确相等的，它相当于一个大概率加一个小概率，小概率被‘吃’掉了。
而小概率事件单独发生能不能突破MinProb的极限呢？
我昨天睡觉的时候想出来了这样的算法，从理论上是可以无限精确的，即任意小的小概率事件都可以得到。
其......
分酒问题-搜索解法(2005-08-15 02:54:00)
摘要：//分酒
/*有四个人喝酒，有两个八两装满酒的瓶，
只有一个三两的杯子。他们要平分这些酒，
但是不能借用其它的工具，你觉得应该怎么做？
*/
#include<iostream.h>
int position[6354][8];//状态集
long ptop=0;
//后来实验的结果是，在求解的过程中可能出现6354种状态
int object[7]={8,8,0,0,0,0,0};//0,1瓶,2杯,3~6人，写在一起只是为了便于搜索
int solution[60][3];//保存解过程：a,b,n a->b(n)
int cmin=100;//最少步数
int scount=0;
int pour(int a,int b)
//从a编号对象往b编号对象转移时，反回可行转移的酒量,返回0表示非法
{
int empty;
if(object[a]==0)return 0;
if(a==b)return 0;
//if(a>2)return 0;//不能从人往容器转移
if(b<3)//容器往容器
{
empty=b<2?8-object[b]:3-object[b];
if(object[a]<empty)return object[a];
return empty;
}
&nb......
任意多边形面积的求解(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)看成是高，上底加下底乘高除二，对直线定积分得到的正是这个梯形的面积。这样走了一个大弯又回到初中了。
......
简单图形扫描转换算法::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-......