中科大黄刘生算法第一次作业中科大黄刘生算法第一次作业.doc
文本预览下载声明
算法实验报告
Ex.1 若将y ← uniform(0, 1) 改为 y ← x, 则上述的算法估计的值是什么？
实验结果如下：
可见结果趋近于2*sqrt(2)
Ex.2 在机器上用估计π值，给出不同的n值及精度。
计算方法就采用课上讲到的HitorMiss算法，伪代码如下：
f←sqrt(1 – x*x)
HitorMiss (f, n) {
k ← 0;
for i ← 1 to n do {
x ← uniform(0, 1);
y ← uniform(0, 1);
if y ≤ f(x) then k++;
}//endfor
return 4*k/n;
}
实验结果如下：
从总的趋势来看，n的值越大，给出的pai的精度越高。但对应到两次实验结果未必n大的精度一定高，这是概率算法的特点。
EX.3 采用算法类似HitorMiss算法，不过加入了一些特殊处理，以便能够正确计算穿越x轴、周期函数等的积分。
算法伪代码如下：
f ← x^2 / - sqrt(x) / sin(x)
MyCalc(f , minx, maxx, miny, maxy, n)
{
k ← 0;
for i ← 1 to n do {
x ← uniform(minx, maxx);
y ← uniform(miny, maxy);
if f(x) = 0//函数在x轴上方，积分是f与x轴之间的部分，积分值为正
then if y = f(x) y =0
k++;
else//函数在x轴下方，积分是f与x轴之间的部分，积分值为负
if y = f(x) y = 0
k--;
}//endfor
if miny 0//函数在x轴上方
then return k / n * (maxx - minx) * (maxy - miny) + miny * (maxx - minx));
else if maxy 0//函数在x轴下方
then return k / n * (maxx - minx) * (maxy - miny) + maxy * (maxx - minx);
else//函数穿越x轴
then return k / n * (maxx - minx) * (maxy - miny);
}
运行结果如下：
可见程序运行结果还是很准确的，能正常处理在x轴单侧、穿越x轴的连续函数积分。
Ex.5 估计自然数子集的大小
采用了课件中介绍的概率算法。为了加快速度，程序采用红黑树处理集合相关运算，比如判断产生的随机数是否已经出现过等，效率为O(log n)。
算法伪代码如下(部分非主要算法未给出)：
struct Num{//红黑树节点，num为已产生的随机数
num; parent; LeftChild; RightChild; color; };
LeftRotate(Num **root, Num *x); //红黑树root以x为支点左旋
RightRotate(Num **root, Num *x); //红黑树root以x为支点右旋
insertfixup(Num **root, Num *z); //修正插入元素z后的红黑树，使其符合红黑树性质
insert(Num **root, Num *z);//将节点z插入以root为根的红黑树，同时检查待插入的节点是否在树中出现过。返回true表示元素出现过，停止生成叶子；返回false表示未出现过这个元素，正常生成叶子
NumberOfSet(n)
{
Number ← 0;// 对集合数目估计10次，10次的总和
for i ← 1 to 10 do{
times ← 0;
NumPicked ← uniform(1, n);
NodeOfRedBlackTree ← NumPicked;//将产生的随机数赋给红黑树节点
while [ insert( NodeOfRedBlackTree ) ] = false //该元素没有出现过
then do{
NumPicked ← uniform(1, n);
NodeOfRedBlackTree ← NumPicked;
times++;
}//endwhile
Number ← Number + 2 * times^2 / pai;
}//endfor
return Number / 10;
}
算法运行结果如下：
从以上的运行结果可以看出，算法能够处理100到10^9量级的计数，计数效果随n的增大逐渐变好。当n较小时，每次运行给出的结果误差
显示全部