楊老師之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
我風 閱讀(269)
評論(0) 編輯 收藏 引用