楊老師之Blog
群里老魔極力推薦之blog.粗粗瀏覽之,發(fā)現(xiàn)里面dd的確不錯(cuò);
摘錄之.
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.關(guān)于求中間值的算法(要求比較次數(shù))
初眼看到這個(gè)問題是想到的算法為排序后取出中間位置的即可,但是這樣的復(fù)雜度為O2,比較次數(shù)為n*(n+1)/2,而后考慮用加權(quán)的平衡二叉樹,這樣比較次數(shù)就大大的減少了.
看了算法后面的回復(fù):
回復(fù):9個(gè)數(shù)分別三個(gè)三個(gè)取出中值而后再對(duì)三個(gè)結(jié)果取中值,這明顯不對(duì),例如:125346789,第一次就無(wú)情的把中值給拋棄了.
提供的算法雖然代碼寫不正確,但其倒也是一種不錯(cuò)的想法,只是這種算法的局限性在于如果提供的數(shù)據(jù)大小不定而且分散的話這種算法就會(huì)變成比排序還要浪費(fèi)時(shí)間了.
總結(jié)下求中值的算法:
1.通用方法:
構(gòu)建一個(gè)加權(quán)的平衡二叉樹.每個(gè)葉子的權(quán)值為子樹葉的數(shù)目.這樣只要取出每個(gè)數(shù)值后插入到該二叉數(shù)中.最后取出平衡二叉樹的根即為中值.
可定義的二叉樹結(jié)構(gòu):
struct?ST_V2TREE
{
???
INT
?Data;??????????
//
節(jié)點(diǎn)數(shù)據(jù)
???
INT
?Power;?????????
//
權(quán)值
???ST_V2TREE?
*
pL,
*
pR;?
//
左右子樹
}
2.映射算法
該算法適合與數(shù)值某一固定較小范圍(如:1000100-1000355)里求中值.
先創(chuàng)建一個(gè)固定的數(shù)組,并把其要找中值的數(shù)據(jù)映射到對(duì)應(yīng)的數(shù)據(jù)中,而后便利數(shù)組,找到第(int)(n/2)個(gè)存在的數(shù)據(jù)即為中值.
posted on 2007-09-21 10:14
我風(fēng) 閱讀(261)
評(píng)論(0) 編輯 收藏 引用