계단 오르기 문제 귀속 해법
2059 단어 에세이
간단히 계단을 오르다
한 사람이 계단을 오르면 한 번에 최대 3급까지만 올라갈 수 있는데, 15급 계단을 오르는 방법은 모두 몇 가지가 있습니까?일반적으로 이런 문제에 부딪히면 우리는 귀착을 고려하여 마지막부터 고려할 수 있다.한 번에 최대 3계단만 올라갈 수 있기 때문에 15계단을 오르려면 다음과 같은 세 가지 상황이 있다.14계단에서 1계단 올라가기 2.13계단에서 2계단을 올라가세요.12계단에서 3계단을 올라가면 n계단을 오르는 방법의 수가 f(n)이면 f(15) = f(14) + f(13) + f(12), 또 f(1) = 1, f(2) = 2, f(3) = 4이기 때문에 귀속 쓰기가 한눈에 들어온다.
int jumpFloor(int n)
{
if(1 == n)return 1;
if(2 == n)return 2;
if(3 == n)return 4;
else return jumpFloor(n-1)+jumpFloor(n-2)+jumpFloor(n-3);
}복잡한 계단 오르기
만약 지금 문제가 한 사람이 n급의 계단을 오르는 것으로 변한다면, 그는 한 번에 1급, 2급,..., n급을 오를 수 있다. 그가 n급을 오르는 방법은 f(n)가 얼마입니까?이전의 결론에 따르면 우리는 쉽게 얻을 수 있다. f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n) 여기에서 f(n-1)는 1계단을 올라가서 n으로 가는 방법수를 나타내고, f(n-n)는 n계단을 직접 올라가서 n으로 가는 방법수(사실은 1)를 나타낸다.이때 f(n-1)f(n-1)=f(n-1)+...+f((n-1)-(n-1)+f((n-1)-(n-1)=f(n-2)+f(n-3)+...+f(n-1)+f(n-n) 대입 f(n)=f(n-1)+f(n-1)=2*f(n-1) 추출 관계식이 나오면 코드가 잘 쓰인다.
int jumpFloor2(int n)
{
if(1 == n)return 1;
else return 2 * jumpFloor2(n-1);
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
시간 형식 변환, "2018-07-12T07:45:0.000Z"와 유사 = > 2018-07-11 15:45:29정의: 호출 tip: 제가 vue에서 사용한 것도 시간 뒤에 추가할 수 있습니다.split(‘T’)[0]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
