進階練習 樹相關問題v0.5.2
- 1.題目資訊
- 2. 寫在前面
- 3. 圖示和思路
- 4. 代碼框架(to be continued)
- 5. 參考資訊
1.題目資訊
在論壇上看到的提問，目前還未解決，按@趙4老師的建議進行階段性梳理，以便提升自己的邏輯思維能力，同時方便大家查閱
2. 寫在前面
-
該題需要對樹結構有一定了解，同時需要良好的邏輯思維能力，才可能發現規律
-
題目初看起來人畜無害，只要按標準步驟處理即可：從少量的結點入手，找到規律后編碼遞回解決，實際上卻很難找到規律
-
需要說明：交換子樹的位置后，若樹結構相同，則視為同一棵樹（如圖所示，我的圖比較丑 大家湊合看）；另外，題目并沒有限定為二叉樹
-
下面把 趙4老師 及 其他大神的分析進行整理，以期方便大家找到規律
-
個人建議還是自己動手畫一下，鍛煉下自己的邏輯思維能力：老師的圖可以作為參考
3. 圖示和思路
-
從結點1到結點6 ： 趙4老師純手工輸出(●’?’●)
N=1, 1種
N=2, 2種
N=3, 4種
N=4, 9種
N=5, 20種
N=6, 48種 -
N=1 N=2 N=3
-
N=4
-
N=5
-
N=6
-
不好意思，上述基本屬于純搬運，我目前還沒有找到規律，后面有時間了會繼續思考，有思路的童鞋歡迎留言
4. 代碼框架(to be continued)
5. 參考資訊
- CSDN論壇相關問題頁面
- 戰爭大神的思路 //我目前沒看懂 ( ╯□╰ )
n個相同節點（n不包括固定的根節點）生成樹的數量，分成兩個步驟：
第一步，求n個節點的排列關系，不考慮節點之間的父子關系，相當于把樹的節點之間的連線去掉的形態，這種拆分叫composition，是有順序的，1-2-3和1-3-2、3-1-2屬于不同拆分，c(n)=2^(n-1)，這個就不證明了，早就有人證過了，
第二步，對第一步生成的每一種節點排列形式，求每一層對上一層的拆分數，比如某種節點排列形式第一層有兩個節點，第二層有三個，則求p(2, 1)、p(3, 2)，第一層不需要計算，因為p(n, 1)=1，p(n, k)表示把n拆分為k個非負整數（允許0）之和的數量，不考慮順序關系，1-2和2-1是同一種拆分，p(n, k)可以遞回實作，比較簡單，把每一層求得的拆分數相乘，即是該種節點排列形式下生成樹的總數，
將每種節點排列形式下生成樹的數量相加，就是n個節點的生成樹的總數，
簡單計算結果（不保證正確）：
n(1) = 1
n(2) = 2
n(3) = 4
n(4) = 9
n(5) = 20
n(6) = 47 (戰爭的補充：計算某一層對上一層的拆分數，不能只考慮上一層的節點總數，還要考慮分塊數，應該是48；分塊還要去重，只需要考慮具有不同節點數的分塊)
…
32位有符號數只能計算到n=26
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/246143.html
標籤：其他
上一篇：IT基礎架構變革，Hitachi Vantara如何解決超融合（HCI）的真正痛點？
下一篇：八個方面理解seo(搜索引擎)