再帰アルゴリズムに基づいて Python で実装されたハノイの塔とフィボナッチ数列

この記事では、主に再帰アルゴリズムに基づいて Python で実装されたハノイの塔とフィボナッチ数列を紹介します。ハノイの塔とフィボナッチ数列の再帰実装テクニックをサンプルの形式で分析します。

この記事では、ハノイの塔と再帰アルゴリズムによって実装されたフィボナッチ数列に基づく Python の例について説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

ここでは 2 つの例を使用して、Python での再帰の使用法を学びます。

1. フィボナッチ数列で添え字 n を持つ数値を見つけます (添え字は 0 から数えます)

フィボナッチ数列の形式は次のとおりです: 0,1,1,2,3,5,8 ,13...

① while ループを使用すると、Python2 コードは次のようになります。

def fib(n):
  a,b=0,1
  count=0
  while count<n:
    a,b=b,a+b
    count=count+1
  print a

実行結果は次のようになります。

>>>
0
>> fib(1)
1
>>> fib(3)
2
> 4)
3
> >> fib(5)
5

② 再帰を使用する (再帰には境界条件が必要です)

の Python2 コードは次のとおりです。実行結果は次のとおりです:

>> ;> fib(0)

0
>>> fib(2)

1

> >> fib(3)
2

>>> fib(4)

3

>>> fib(5)

再帰は計算的思考を最もよく表現するアルゴリズムの 1 つです例として f(4) を見てみましょう:



同じプログラムは再帰を使用しますが、プログラムは単純ですが、再帰の実行効率はループよりも低くなります。システムリソースの消費量はループよりも大きくなります。再帰は階層ごとに呼び出され、完了後に階層ごとに返されるため、再帰の実行効率は高くありません。では、なぜ再帰を使用するのでしょうか?いくつかの問題があるため、明確なループ解決策を見つけることはできませんが、明確な再帰的解決策を見つけるのは簡単です。有名なハノイ塔問題を例に考えてみましょう。



2. ハノイの塔

下の写真は、プレートが4枚だけのハノイの塔ゲームの簡易版です:

ハノイの塔ゲームのルールは次のとおりです:

Python2のコードは次のとおりです:

def fib(n):
  if n==0 or n==1:#递归的边界条件
    return n
  else:
    return fib(n-1)+fib(n-2)

実行結果:

>>> hanoi('A','B','C',1)A ->C

>>>ハノイ('A','B','C',2)

A->C

>> > ハノイ('A','B','C',3)

A -> C
B ->C

A ->C

関連する推奨事項:


ニューラルネットワーク (BP) アルゴリズムの Python 実装とアプリケーション

以上が再帰アルゴリズムに基づいて Python で実装されたハノイの塔とフィボナッチ数列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。