n階費氏數

Define the Fibonanci binary tree of order n as follows:

█ If n=0 or 1, the tree consists of a single node.

█ If n>1, the tree consists of a root, with the Fibonanci tree of order n-1 as the left subtree and the Fibonanci tree of order n-2 as the right subtree.

1. What's the number of leaves in the Fibonanci tree of order n? Why?

2. What's the depth of Fibonanci tree of order n?

2 個解答

• 鴨子
Lv 6
1 0 年前
最佳解答

1.

the number of leaves in the Fibonanci tree of order n

= Fibonanci 數列的 第 n+1 項

採標準Fibonanci 數列的定義

F(0)=0

F(1)=1

F(n)=F(n-1)+F(n-2), n>1

那答案為Fibonanci 數列的第 n+1 項

==========================

理由:

Leaf 就是沒有左樹,右樹的 node

a binary tree (如果不是leaf) 的 leaf數

=左樹的 leaf數 + 右樹的 leaf數

(因為根不是leaf

a binary tree (是leaf)的 leaf數

=1

定義: L(n) = the number of leaves in the Fibonanci tree of order n

L(0)=1 (因為 If n=0 or 1, the tree consists of a single node.)

L(1)=1

L(n)=L(n-1)+L(n-2)

因為If n>1, the tree consists of a root, with the Fibonanci tree of order n-1 as the left subtree and the Fibonanci tree of order n-2 as the right subtree.

=>

L(n) 是 Fibonanci 數列的第n項

=========================================================

What's the depth of Fibonanci tree of order n?

n=0, 為 0

n>0, 為 n-1

因為:

The depth of a node n is the length of the path from the root to the node.

The root node is at depth zero.

D(0)=0

D(1)=0

D(2)=1

D(3)=2

D(4)=3

D(5)=4

.....

D(n)=0, n= 0

D(n)= n-1, n>0

• 6 年前

硬碟要找硬碟醫院，能救回來才重要，我司就是找他們做出來的

必須要推，當初心急亂找錯店告訴我沒辦法，後來找又找到硬碟醫院，我告訴他真心要來救援，可以等，在他們努力下有找回來

太棒了，原來微軟張經理都找過他們

http://www.datamaster.com.tw/