推 TassTW :推推 10/29 12:19
推 k6416337 :又學到一個好東西 10/29 12:45
推 linrob :又學到一個好東西+1 10/29 17:18
推 jacky7987 :這好厲害阿 10/29 18:12
推 nobrother :推推推 10/29 21:39
→ microball :推～！ 10/30 01:33
推 bohsing :很有趣的分享!!XD 11/03 09:40
來介紹一個東西 Stern-Brocot tree
它是一個樹的結構, 是這樣子構成的:
一開始是兩個端點 0/1 代表 0, 1/0 代表無限大
然後每次在序列的每兩個數中間插入分子分母各是兩邊的分子分母和的有理數
所以第一個是 (0+1)/(1+0) = 1/1 變成 0/1, 1/1, 1/0
再來在 0/1 跟 1/1 中間插入 (0+1)/(1+1) = 1/2
1/1 跟 1/0 中間插入 (1+1)/(1+0) = 2/1
序列成為 0/1, 1/2, 1/1, 2/1, 1/0
依此類推下去
之所以說它是樹的結構是因為我可以把這個成型的結構畫成這樣:
http://0rz.tw/ifghY (借一下維基百科的圖)
而且由於有理數的性質: 當 a/b < c/d 時有 a/b < (a+c)/(b+d) < c/d
樹上每一個有理數的左右分支都會有 左分支 < 自己 < 右分支 的性質
(具有這種性質的樹結構有個名字叫二元搜尋樹
因為可以藉由和路線上的每個數比較來找到所尋找的數值)
那麼 給定兩個有理數
所有在這兩個有理數之間的有理數都會在樹的某一個部份
以這題為例 7/10 跟 11/15 之間的數都會在這一段下面:
(上略)
2/3
／ ＼
(略) 3/4
／ ＼
5/7 (略)
／ ＼
／ ＼
7/10 8/11
／ ＼ ／ ＼
9/13 12/17 13/18 11/15
／ ＼ ／ ＼ ／ ＼ ／ ＼
(下略)
那麼所求分母最小的數就是這兩個數的「最低共同祖先」
也就是上面綠色那一塊的頭
(這個結論可以由這棵樹的性質得到)
也就是說, 在樹中找到這兩個有理數之後往上追共同祖先
追到把兩個人分開的那個數就是答案了 在這題就是 5/7
至於在樹中找有理數也可以利用搜尋樹的性質
例如 看到 2/3 要找的 7/10 大於它 所以往右邊下去
看到 3/4 要找的 7/10 小於它 所以往左邊下去
等等
更多有關這棵樹可以參看維基百科
http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree
這棵樹還跟這個有理數的連分數展開有關
(也就是說, 這個題目也可以用連分數展開來做
道理是一樣的不過這棵樹比較形象化 XD)
--
'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
---'Harry Potter and the order of the phoenix', P513
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.69.49.38