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

不言
リリース: 2018-04-18 14:28:11
オリジナル
2541 人が閲覧しました

この記事では、主に再帰アルゴリズムに基づいて 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 サイトの他の関連記事を参照してください。

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート