재귀 알고리즘을 기반으로 Python으로 구현된 하노이 탑과 피보나치 수열

이 글에서는 주로 재귀 알고리즘을 기반으로 Python으로 구현한 하노이 탑과 피보나치 수열을 소개합니다. 하노이 탑의 재귀 구현 기법과 피보나치 수열을 예제 형식으로 분석하여 도움이 필요한 친구들이 참고할 수 있습니다.

이 문서의 예제에서는 재귀 알고리즘으로 구현된 하노이 탑과 피보나치 수열을 기반으로 하는 Python을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

여기에서는 두 가지 예를 사용하여 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 코드는 다음과 같습니다.

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

실행 결과는 다음과 같습니다:

>>> fib(0)

0

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


재귀는 컴퓨팅 사고를 가장 잘 표현하는 알고리즘 중 하나입니다. .f(4)를 예로 들어 재귀 실행 프로세스를 살펴보겠습니다.

동일한 프로그램은 단순하지만 루프에 비해 실행 효율성이 낮습니다. 시스템 자원 소모가 루프보다 큽니다. 재귀는 레이어 단위로 호출되고, 완료 후 레이어 단위로 반환되기 때문에 재귀 실행 효율이 높지 않습니다. 그렇다면 왜 재귀를 사용합니까? 몇 가지 문제가 있기 때문에 매우 명확한 루프 솔루션을 찾을 수는 없지만 명확한 재귀 솔루션을 찾는 것은 쉽습니다. 유명한 하노이탑 문제를 예로 들어보자.

2. 하노이 타워

아래 그림은 4개의 플레이트만 있는 하노이 타워 게임의 단순화된 버전입니다.

하노이 타워 게임의 규칙은 다음과 같습니다.

python2 코드는 다음과 같습니다:

def hanoi(a,b,c,n):
  if n==1:#递归结束条件
    print a,'->',c
  else:
    hanoi(a,c,b,n-1)
    print a,'->',c
    hanoi(b,a,c,n-1)

실행 결과:

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

A -> C

>> 하노이('A','B','C',2)

A -> B

A -> >하노이('A','B','C',3)

A -> C
A -> B
A -> -> C
A -> C






관련 권장 사항:


신경망(BP) 알고리즘 Python 구현 및 응용

위 내용은 재귀 알고리즘을 기반으로 Python으로 구현된 하노이 탑과 피보나치 수열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!