Re: [中學] 關於不等式的一題

看板Math作者LPH66 (f0VMRgEBA)時間12年前 (2013/10/29 12:15)推噓6(6推 0噓 1→)

留言7則, 7人參與討論串3/3 (看更多)

來介紹一個東西 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

推

TassTW

10/29 12:19, , 1^F

10/29 12:19, 1^F

推

k6416337

10/29 12:45, , 2^F

10/29 12:45, 2^F

推

linrob

10/29 17:18, , 3^F

10/29 17:18, 3^F