杨老师之Blog
群里老魔极力推荐之blog.粗粗浏览之,发现里面dd的确不错;
摘录之.
1.牛B的求pi程序:
void main()
{
long
a
=
10000
,b
=
0
,c
=
2800
,d
=
0
,e
=
0
,f[
2801
],g
=
0
;
for
( ; b
-
c; )
f[ b
++
]
=
a
/
5
;
for
( ;d
=
0
, g
=
c
*
2
; c
-=
14
, printf(
"
%.4d
"
,e
+
d
/
a ), e
=
d%a )
for
( b
=
c; d
+=
f[b]
*
a, f[b]
=
d%
--
g, d
/=
g
--
,
--
b; d
*=
b );
}
2.关于求中间值的算法(要求比较次数)
初眼看到这个问题是想到的算法为排序后取出中间位置的即可,但是这样的复杂度为O2,比较次数为n*(n+1)/2,而后考虑用加权的平衡二叉树,这样比较次数就大大的减少了.
看了算法后面的回复:
回复:9个数分别三个三个取出中值而后再对三个结果取中值,这明显不对,例如:125346789,第一次就无情的把中值给抛弃了.
提供的算法虽然代码写不正确,但其倒也是一种不错的想法,只是这种算法的局限性在于如果提供的数据大小不定而且分散的话这种算法就会变成比排序还要浪费时间了.
总结下求中值的算法:
1.通用方法:
构建一个加权的平衡二叉树.每个叶子的权值为子树叶的数目.这样只要取出每个数值后插入到该二叉数中.最后取出平衡二叉树的根即为中值.
可定义的二叉树结构:
struct ST_V2TREE
{
INT
Data;
//
节点数据
INT
Power;
//
权值
ST_V2TREE
*
pL,
*
pR;
//
左右子树
}
2.映射算法
该算法适合与数值某一固定较小范围(如:1000100-1000355)里求中值.
先创建一个固定的数组,并把其要找中值的数据映射到对应的数据中,而后便利数组,找到第(int)(n/2)个存在的数据即为中值.
posted on 2007-09-21 10:14
我风 阅读(236)
评论(0) 编辑 收藏 引用