博文
宽搜(2006-05-04 22:52:00)
摘要：关于tju1258双向宽搜的做法讨论
经过不懈努力,终于吧tju1258ac了
当然,初看好象是一个简单题,bfs+hash了事,不过并不是那么简单....
一个单纯的正向宽搜程序:
const dbin:array[1..8]of longint=(1,2,6,24,120,720,5040,40320);
maxn=362880;
maxmm=3;
var restate:array[1..maxn]of boolean;
queue:array[1..maxn,1..2]of longint;
mat:array[0..maxmm,1..9]of integer;
tmpline:array[1..9]of integer;
recode,tmpstate,co,qf,qr,s:longint;
procedure init;
begin
fillchar(restate,sizeof(restate),false);
qf:=0;qr:=0;
end;
procedure turncode(num:integer;var code:longint);
var s,s1:integer;
sum:longint;
begin
sum:=1;
for s:=1 to 9 do mat[0,s]:=mat[num,s]+1;
for s:=1 to 8 do
begin
inc(sum,(mat[0,s]-1)*dbin[9-s]);
&nb......
用Gauss列主元消元法解线性方程组(2006-04-09 23:15:00)
摘要：#include<math.h>
#include<stdio.h>
#define NUMBER 20
#define Esc 0x1b
#define Enter 0x0d
float A[NUMBER][NUMBER+1] ,ark;
int flag,n;
exchange(int r,int k);
float max(int k);
message();
main()
{
float x[NUMBER]; /*此数组用于存放方程解*/
int r,k,i,j;
char celect;
clrscr();
printf("\n\n用Gauss列主元消元法解线性方程组");
printf("\n\n1.解方程组请按Enter.");
printf("\n\n2.退出程式请按Esc.");
celect=getch();
if(celect==Esc)
exit(0);
printf("\n\n 输入方程组的维数：n=");
scanf("%d",&n);
printf(" \n\n现在输入系数矩阵A和向量b:");
for(i=1;i<=n;i++)
{
printf("\n\n请输入a%d1--a%d%d系数和向量b%d:",i,i,n,i);
/*实现将每一行中的系数和向量一次......
任意多边形面积的求解(2006-04-01 14:49: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)看成是高，上底加下底乘高除二，对直线定积分得到的正是这个梯形的面积。这样走了一个大弯又回到初中了。
Ｃ++程序代码
#include<iostream.h>
float linesqr(float x1,float y1,float x2,float......
大数相乘的一种高效算法(2006-04-01 14:31:00)
摘要：/**************************************
算法复杂度为：O(longhta*longthb）
longtha为乘数的位数
longhtb为被乘数的位数
***************************************/
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define LEN 1000
void mult(char [],char [],char []);
main()
{
char op1[LEN],op2[LEN],op3[LEN*2-1];
scanf("%s%s",op1,op2);
mult(op1,op2,op3);
printf("%s\n",op3);
getch();
return 0;
}
void reverse(char a[])
{
int longth=strlen(a);
int i;
for(i=0;i<longth/2;i++){
&......
概率密度函数分布的随机变量生成算法(2006-04-01 14:28:00)
摘要：概率密度的定义
概率简单地说就是在空间某处附近一确定的范围内发生某事件的可能性，而概率密度则是概率与空间范围之比的极限。在讨论更复杂一些的空间之前，可以从一维的线性空间出发定义它们。
在一维空间中，用数轴表示所有的点，定义Ф(x)为：随机变量i，当i<x时的概率，因此得Ф(-∞)=0，Ф(+∞)=1（因为全概率为1），这个条件是直接由定义得出，称为归一化条件。
由此当x取数轴上的点时，随机变量i取到[x,x+△x](△x>0)中时的概率应该为Ф(x+△x)-Ф(x)，则定义i取到这个区间的平均概率密度p^=(Ф(x+△x)-Ф(x))/ △x，此时如果极限:
lim(Ф(x+△x)-Ф(x))/ △x=p(x) 存在
△ x->0
则称极限值为这一点的概率密度，由数学知识这正是导数的定义，于是有p(x)=dФ/dx，于是有△Ф=∫p(x)dx，积分区域为△，虽然这是从一维情况推出，这是概率的一般形式定义。于是归一化条件就相应为∫p(v)dv=1，积分区域为全空间。
由此概率密度函数就唯一决定了随机变量的分布，反过来我们也说随机变量服从某种概率密度函数的分布。
如何由p函数模拟随机变量的生成
首先我们要有一个这样的随机函数，Ｃ的原型如下：
double random();/*返回一个大于等于0，小于1之间的等概率随机双精度小数*/
-->规格化的随机变量<--
这个算法的实现将在以后给出算法，事实上笔者最开始学习编程时就是学的这种随机函数，它是BASIC里的标准函数，这里只是为了讨论的需要，因为由它可以非常方便的得到任意范围内的随机数，包括浮点数或整数。
然后我们再拿来这样一个任意的概率密度函数p(x)，且满足归一化条件∫p(x)dx=1，积分区域为[0,1)。最后再给出这个函数在[0,1)上的上限（最大值）h。然后用下面的方法生成服从该分布的随机变量。
首先得到一个等概率的随机的二维的点(x,y)，它落在矩形区域[0,1;0,h]内，同时我们还要求这样一个条件y<p(x)，如果得到的点不满足这个条件则重新取点，也就是说把那些不满足此条件的点‘去掉’。最后我说这里的x满足p(x)的分布。证明如下：
......