4

誰かが助けてくれることを願っています。私はプログラマーではありませんが、フィボナッチ数列の探索に興味があり、それは再帰ツリーです...

関連する TreeNode クラスとともに Binary Tree クラスを作成しました。次の方法で作成された再帰呼び出しのバイナリ ツリーを生成したいと考えています。

f(n) = f(n-1) + f(n-2) n の特定の値

標準の Insert メソッドを置き換えて、Binary Tree クラスの InsertFibonacci メソッドとして追加したいと思います。

def insertNode(self, root, inputData):
    if root == None:
        return self.addNode(inputData)
    else:
        if inputData <= root.nodeData:
            root.left = self.insertNode(root.left, inputData)
        else:
            root.right = self.insertNode(root.right, inputData)
        return root

Fib 関数にある種のデコレータを追加しますか?

# Fib function
def f(n):

    def helper(n):
        left = f(n-1)
        right = f(n-2)
        return left,right

    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        left, right = helper(n)
        return left + right
4

2 に答える 2

3

これが私が考えることができる最も簡単な解決策です：

class FibTree(object):
    def __init__(self, n):
        self.n = n
        if n < 2:
            self.value = n
        else:
            self.left = FibTree(n - 1)
            self.right = FibTree(n - 2)
            self.value = self.left.value + self.right.value
于 2012-02-11T00:22:14.150 に答える
1

1 つの方法を次に示します。

def insertFibonacci(self, n):
    current = self.addNode(n)
    if n > 1:
        current.left = self.insertFibonacci(n-1)
        current.right = self.insertFibonacci(n-2)
        # if you want the fibonacci numbers instead of the calls:
        # current.value = current.left.value + current.right.value
    return current

正と仮定しnます。フィボナッチ コール ツリーのルートを返す必要があります。

これはまったく同じ種類のバイナリ ツリーではないことに注意してください。二分探索木が行う順序不変条件を満たしません。便宜上、既存の構造を使用したいだけだと思います。

于 2012-02-11T00:20:31.800 に答える