최근의 학습은 항상 돌아가는 이 물건을 돌릴 수 없다. 나는 이 물건을 배우기로 결정했다. 처음 접했을 때 이해에 문제가 좀 생겼다. 이해가 된 것 같아서 그렇다. 그러나 책을 덮고 블로그를 끄면 자기가 쓰기만 하면 어리둥절한 표정을 짓는다.많이 쓰면 좀 나아질 거야. 20문제 연습하고 비비할게.

문서 목록

1.귀속 문제는 정수 곱하기로부터 이 문제를 도입한다.

2. 한노타

3.피보나치 수열

4.최대 공약수

구하기

5. 계단 뛰어넘기

6.변태 계단 뛰어넘기

1. 문제를 귀속시키고 정수 곱하기로부터 이 문제를 도입한다.

함수 f(n) = n!= 설정1 ∗ 2 ∗ 3 ∗ ⋅ ⋅ ⋅ ∗ ( n − 1 ) ∗ n f(n)=n!=1 * 2 * 3 * ···* (n-1) * n f(n)=n!=1∗2∗3ͦ3∗n(n-1)?n그러면 이 함수는 f(n)=n?f(n)=f(n)=n(n)=n*f(n)=n*f(n-1)f(n)=n?f(n)=n(n)=n?f(n-1)로 볼 수 있다. 이때 귀속의 공식을 찾았으니 가장 중요한 단계는 일을 끝내야 할 귀속 조건을 찾는 것이다!반드시 귀환에게 출구를 찾아야 한다. 그렇지 않으면 무한히 교체될 것이다.이것은 일반적으로 비교적 쉽다. 바로 이 문제의 시작 부분이나 끝 부분이다. 예를 들어 이 계승 문제의 출구가 n=1n=1n=1일 때 f(n)=1f(n)=1f(n)=1f(n)=1이다.단계별 반복 코드는 다음과 같습니다.

def func(n):
	if n == 1:
		return 1
	else:
		return n * func(n - 1)

교체의 계승은:

#  
def func(n):
	result = n
	for i in range(1, n):
		result *= i
	return result

2. 한노타

def hanoi(n, x, y, z):     ##  n x y， z
	if n == 1:
		print(x,'-->',z)   ##  
	else:
		hanoi(n-1,x,z,y)   ##  n-1 x z， y， x n z
		print(x,'-->',z)
		hanoi(n-1,y,x,z)

n= int(input(" ："))
hanoi(n,'x','y','z')

3. 피보나치 수열

def fab(n):    # 1 1 2 3 5 8 13 21 34 55···
	if n == 1 or n == 2:
		return 1
	else:
		return fab(n-1)+fab(n-2)

4. 최대 공약수(전전 상제법) 구하기

def gcd(a,b):
	a,b = (a,b) if a>=b else (b,a)
	if a%b ==0:
		return b
	else:
		return gcd(b,a%b)

5. 계단 뛰어오르기

개구리 한 마리는 한 번에 1계단을 올라갈 수도 있고 2계단을 올라갈 수도 있다.이 개구리가 n급 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해라.먼저 규칙을 찾다.법칙에서 교체 공식이나 귀속 법칙을 추출할 수 있다.f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(n)=f(n-1)+f(n-2)의 법칙을 총결해 낼 수 있다

## py2.7
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number==1:
            return 1
        else:
            a = 1
            b = 1
            for i in range(number):
                a,b = b, a+b
            return a

## py3.7
def jumpfloor(n):
	if n <= 3:
		return n
	else:
		return jumpfloor(n-1)+jumpfloor(n-2)

print(jumpfloor(int(input())))

6. 변태 계단 뛰어넘기

개구리 한 마리가 한 번에 1계단을 올라갈 수도 있고, 2계단을 올라갈 수도 있다.이 개구리가 n급 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해 보세요.질문: 링크:https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
본 문제에 관하여 전제는 n계단에 n계단의 점프법이 한 번 있다는 것이다.분석은 다음과 같다. f(1)=1 f(2)= f(2-1)+f(2-2)//f(2-2)는 2단계가 한 번에 2단계를 뛰는 횟수를 나타낸다.f(3)= f(3-1)+f(3-2)+f(3-3)f(n)= f(n-1)+f(n-2)+f(n-3)+...2) n=1시, 1가지 점프법만 있고, f(1)=13)n=2시에는 두 가지 점프 방식이 있는데, 한 번에 1단계 또는 2단계로 돌아간다. 이것은 문제(1)로 돌아간다. f(2-1)+f(2-2)4)4) 4) n=3시에는 세 가지 점프 방식이 있다. 1단계, 2단계, 3단계. 그러면 첫 번째 점프 1단계 뒤에 남은 것은 f(3-1)이다.첫 번째 2 단계 탈출, f (3-2) 남음;첫 번째 3단계, 그럼 f(3-3)가 남았으니 결론은 f(3)=f(3-1)+f(3-2)+f(3-3)5)n=n이 남았을 때 n으로 뛰는 방식이 있다. 1단계, 2단계...n단계, 결론은 f(n)=f(n-1)+f(n-2)+...+f(n-1)+f(n-n)+f(n-n)=>f(0)+f(0)+f(1)+f(1)+f(3)+f(3)+f)+f(3)+...)+f(1)+)는 간단하지만 결론은 간단하다.우리는 계속 간소화할 수 있다. f(n-1)= f(0)+f(1)+f(2)+f(3)+...+f(n-1)-1) = f(0)+f(1)+f(2)+f(2)+f(3)+...+f(n-2)f(n)=f(0)+f(1)+f(2)+f(3)+...+f(n-1)+f(n-1)+f(n-1)=f(n-1)+f(n-1)=f(n-1)+f(n-1)=f(n-1)*f(n-1)=f(n-1)
이것은 등비수열로 통항식도 구할 수 있다: 2^(n-1)

#  ， ， 
def func(n):
	return 2**(n-1)

#  
def jumpfloor(n):
	if n ==1:
		return 1
	else:
		return 2*jumpfloor(n-1)