알고리즘과 데이터 구조 학습 노트 시리즈-귀속(1)
2318 단어 귀속
본문 시작.
사실 이전에도 귀속 방법으로 해결하는 문제를 많이 보았습니다. 많은 상황에서 우리는 이 문제를 귀속 방법으로 해결해야 한다는 것을 알았지만 완전한 절차를 쓰지 못했습니다. 그래서 저는 귀속 문제를 기초성과 복잡성 두 가지로 나눴습니다.복잡성 문제는 제가 나중에 연구를 다 한 후에 여러분께 제 개인적인 경험을 공유하고 오늘은 주로 기초적인 문제를 이야기합니다.
우선, 기초적인 귀속 문제가 무엇인가.내가 보기에 두뇌로 한 걸음 한 걸음 귀속 표현식을 생각해 낼 수 있는 것 같다. 아마도 이 말은 좀 쓸데없는 것처럼 보일 것이다. 몇 가지 대표적인 예를 들면 여러분들이 내가 한 말을 이해할 수 있을 거라고 생각한다.
문제1: 정수 N을 정하고 피보나치 수열의 N항을 되돌려줍니다.
해결: 피보나 절수열은 1, 2, 3, 5, 8·····과 같은 수열로 제3항이 앞의 두 항의 합과 같다는 특징이 있기 때문에 우리는 아래의 추이식 f(N)=f(N-1)+f(N-2)를 쉽게 쓸 수 있다. 이것은 이해하기 쉽다.그러나 또 하나의 문제는 귀환이 반드시 끝나야 한다는 것이다. 여기서 식이 맨 앞의 두 항목으로 귀환될 때 귀환해야 하기 때문에 N=1과 2시에 귀환해야 한다. 물론 처음에 입력한 N<1이면 바로 0이다.다음 프로그램을 작성할 수 있습니다.
public int f(int N)
{
if(N < 1)
{
return 0;
}
else if(N == 1 || N == 2)
{
return N;
}
return f(N-1)+f(N-2);
}문제2: 농장에서 성숙한 암소가 매년 한 마리의 암소만 낳고 영원히 죽지 않는다고 가정하면 첫해에 농장에서 성숙한 암소가 한 마리 있었고 이듬해부터 암소가 암소를 낳기 시작했다.암소 한 마리당 3년 후에 익으면 암소를 낳을 수 있다.N의 정수를 정하여 N년 후 암소의 수를 구하다.
해결: 지난 문제와 유사한 피보나치 수열, 우리는 N년의 관점에서 이 문제를 고려할 수 있다. 올해의 암소 수는 어떻게 생겼는가?적어도 작년의 암소가 올해는 틀림없이 있을 것이라는 것을 우리는 먼저 틀림없이 알 수 있을 것이다.이렇게 하면 f(N)는 적어도 f(N-1)와 같다.그리고 제목에서 암소는 송아지를 낳을 수 있고 한 마리당 3년이 성숙해야 송아지를 낳을 수 있기 때문에 3년 전 암소의 수를 늘릴 수 있다.그래서 f(N)에 f(N-3)를 더 넣어야 한다.간단하게 이렇게 설명하면 왜 f(N-3)가 증가했는지 명확하게 설명할 수 없기 때문에 우리도 자세히 나누어 볼 수 있다.올해의 소는 반드시 작년의 소를 포함해야 하고, 올해 성숙한 소만 소를 낳을 수 있기 때문에 작년의 소 중에는 올해 성숙하지 못한 소가 존재할 것이다. 그렇다면 문제는 올해 얼마나 많은 소가 성숙했는가에 있다.그러면 3년 전에 태어난 송아지와 당시에 이미 성숙한 암소만 올해 성숙했다. 이것은 바로 그 해의 소의 수량, 즉 f(N-3)이다.그래서 f(N)=f(N-1)+f(N-3).구체적인 절차는 열거하지 않고 이전 문제와 매우 유사하다.N=1, 2, 3시에 돌아갑니다.
문제3: 정수 N을 정하면 계단 수를 대표하고 한 번에 2개 또는 한 계단을 건널 수 있으며 몇 가지 걷는 방법이 되돌아갈 수 있습니까?
해결: 여전히 같은 사고방식이다. 만약에 내가 지금 N 단계 계단에 있다고 가정하면 우리는 이 N 단계 계단이 어떻게 도착했는지 고려해야 한다.가능성 1은 한 계단을 올라가면 걷는 방법은 모두 f(N-1)이고, 가능성 2는 두 계단을 올라가면 걷는 방법은 f(N-2)이기 때문에 f(N)=f(N-1)+F(N-2)를 열거할 수 있다.
종합적으로 말하면 간단한 귀속 문제에 대해 우리는 자신이 N시까지 처신할 때의 상황을 고려하고 이 f(N)가 어떻게 왔는지 고려하면 우리가 문제를 푸는 데 어느 정도 도움이 될 수 있다.물론 귀환의 효율은 매우 낮다. 위의 세 가지 문제는 모두 효율적인 동적 기획의 해법을 가지고 있다. 나중에 제가 배워서 여러분께 공유할 것이다.
마지막으로 만약에 이 블로그를 본 학생이 있다면 제 문제점을 지적해 주기를 바랍니다. 이것은 제 학습 소감일 뿐이고 발전해야 할 부분도 있습니다.저에게 귀속에 관한 우수한 블로그를 추천해 주셔서 제가 계속 공부하고 함께 발전할 수 있도록 해 주십시오.
좋은 웹페이지 즐겨찾기
