알고리즘 총결의 추이와 귀속
4614 단어 acm 문제 풀이
점차적 계산법
귀속 알고리즘은 대체적으로 두 가지 측면의 내용을 포함한다. 1) 귀속 기점.2) 귀속 관계
기점을 점차 미루다
귀환 기점은 일반적으로 제목이나 실제 상황에 의해 확정되고 귀환 관계에 의해 내놓지 않는다.만약 귀환 기점을 확정할 수 없다면 귀환 알고리즘은 실현될 수 없다.이를 통해 알 수 있듯이 귀속 기점은 귀속 알고리즘의 중요한 부분이다.
점진적 관계
귀속 관계는 귀속 알고리즘의 핵심이다.일반적으로 반복 관계에는 다음과 같은 항목이 있습니다.
다음은 밤을 통해 상술한 유형의 추이 관계를 상세하게 소개한다.
1. 1 단계는 f(i)를 계산할 때 앞의 항목 중 하나만 사용한다. 예를 들어 등차수열.공차는 3의 등차 수열이고 그 추이 관계는 다음과 같다.
f(i)=f(i-1)+3
eg. 평면에 있는 10개의 직선은 평면을 가장 많이 몇 부분으로 나눌 수 있습니까?분석: 직선의 수를 점차적인 변수로 하고 i개의 직선이 평면을 f(i)부분으로 가장 많이 나눈다고 가정하면 f(i-1)는 i-1개의 직선이 평면을 가장 많이 나눈 부분을 나타낸다.i-1직선의 평면에 직선 i를 증가하면 쉽게 얻을 수 있는 i는 평면에 이미 존재하는 i-1직선과 가장 많은 교점이 있다. 즉, 직선 i는 가장 많은 i단으로 나뉘고 이 i단은 순서대로 평면을 둘로 나눈다. 즉, 직선 i는 평면을 가장 많이 i부분으로 증가시킨다.따라서 점차적인 관계는 f(i)=f(i-1)+i로 쉽게 0개의 직선이 될 때 평면은 1부분으로 나타낼 수 있다.그래서 f(0)=1은 점차적인 출발점이다.이러한 분석은 다음 코드로 나타낼 수 있습니다(c++).
#define MAX 100
int f[MAX] // f（i）
int lines(int n){
// n
//
int i;
f(0)=1;
for(i=1;i<=n;i++){
f[i]=f[i-1]+3;
}
return f[i];
}
2. 여러 단계로 f(i)를 계산할 때 앞에서 계산한 여러 가지, 예를 들어Fibonacci 수열을 사용해야 한다.eg. Fibonacci의 10항을 구하세요.분석: 전체적으로 알다시피Fibonacci 수열 중의 n항은 n-1항에 n-2항을 더한 것이다.그래서 점차적인 관계는 f(i)=f(i-1)+f(i-2)이다.또한 f[0]=f[1]=1.C++ 코드는 다음과 같습니다.
#define MAX 100
int f[MAX];
int fib(int n){
// n
// n fib
int i;
f[0]=0;
f[1]=1;
for(i=2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n]
}
3. 간접적으로 f[i]를 계산할 때 중간량을 필요로 하고 중간량을 계산하려면 전에 계산한 항목을 사용해야 한다.eg. 현재 네 명이 패스 게임을 하고 있는데 공을 받은 후 바로 다른 사람에게 패스할 것을 요구한다.갑이 먼저 패스하고 첫 패스로 나섰다.10번의 패스를 거치고도 공이 여전히 서브인 갑의 패스 방식의 종류로 돌아오기를 바란다.분석: 두 가지 상태를 정의한다. 1) 현재 공이 갑에 있고 i번의 패스를 거친 후에도 공이 갑에 있다. 이 상황은 F로 기록하고 그의 패스 방식의 종류는 f(i)이다.2) 현재 공이 갑손에 없고 i번의 패스를 거친 후에 공이 갑손에 있다. 이 상태는 G로 기록하고 패스 방식의 종류는 g(i)이다.상태1): 갑이 공을 던지면 공을 받는 사람의 상태가 G(i-1)로 변한다. 갑은 3개의 다른 사람에게 패스할 수 있기 때문에 f(i)=3g(i-1).상태2): 공을 잡는 사람은 갑에게 공을 패스할 수 있는데 이때는 F(i-1)상태이다.공을 다른 두 사람, 즉 2G(i-1) 상태로 패스할 수도 있다.그래서 g(i)=f(i-1)+2*g(i-1).계산의 점차적인 출발점은 갑이 처음으로 공을 자신에게 패스할 수 없기 때문에 f(1)=0;다른 사람이 공을 한 번 패스하려면 공을 갑에게 패스해야 한다. 그것은 단지 한 가지 방식(직접 공을 갑에게 패스), 즉 g(1)=1.상술한 추이 관계는 바로 간접 추이다.c++를 사용하여 다음을 수행합니다.
#define MAX 100
int f[MAX];
int g[MAX];
int ball(int n){
// n
//
int i;
f[1]=0;
g[1]=0;
for(i=2;i<=n;i++){
f[i]=3*g[i-1];
g[i]=f[i-1]+2*g[i-1];
}
return f[n];
}
4. 역주행은 말 그대로 뒤에서 앞으로 밀기 시작한다.동전 바둑 게임.바둑판에 0정거장, 1정거장...100정거장이 표시되어 있다. 처음에 바둑알은 0정거장에 있는데 기사는 매번 동전을 한 번씩 던지고 동전의 정면이 위로 올라가면 두 정거장 앞으로 뛴다.그렇지 않으면 앞으로 한 정거장... 바둑돌이 99정거장(승리대본영), 100정거장(실패대본영)까지 뛸 때까지 게임이 끝납니다.만약 동전이 정반대가 나타날 확률이 모두 0.5라면, 각각 바둑알이 승리대본영에 도달할 확률과 패배대본영에 도달할 확률을 구한다.분석: 가설기는 i역에서 시작하여 마지막에 100정거장에 도착할 확률은 f(i)이다.i역에서 동전을 한 번 던지면 0.5의 확률로 i+1역에 도착하고 0.5의 확률로 i+2역에 도착한다.그래서 점차적인 관계는 f(i)=0.5f(i+1)+0.5f(i+2)이다.이득 점차적 기점 f(100)=1, f(99)=0.99정거장에 도착해서 게임이 끝났습니다.상술한 것은 바로 역전추의 한 과정이다.c++는 다음과 같이 구현됩니다.
#define MAX 100
double f[MAX];
double prob(){
//
// 100
int i;
f[100]=1.0;
f[99]=0;
for(i=98;i.=0;i--){
f[i]=0.5*f[i+1]+0.5*f[i+2];
}
return f[0];
}
5. 다차원 추이 원소는 하나의 다차원 행렬에 있고 추이 원소는 행렬의 다른 위치의 원소를 사용해야 한다.예는 훗날 갱신된다.
역귀함수
컴퓨터 과학에서 만약에 한 함수의 실현에 함수 자체에 대한 호출문이 나타나면 이 함수를 귀속함수라고 부른다.추이 알고리즘은 귀속 함수로 실현할 수 있다.일반적으로 순환 추출 알고리즘은 귀속 함수보다 빠르지만 귀속 함수의 가독성은 더욱 좋다.위의 부분의 추이 알고리즘을 귀속 함수로 바꾸다.1) 평면 구분
int lines(int i){
if(i<=0)
return 1;
else
return lines(i-1)+i;
}
2) Fibonacci 수
int fib(int i){
if(i==0)
return 0;
if(i==1)
return 1;
else
return fib(i-1)+fib(i-2);
}
위의 코드에서 분석할 수 있듯이 점차적 기점은 점차적 함수에서 점차적 마감 작용을 한다.
귀속 함수의 집행 과정
귀속 함수는 매번 호출할 때마다 활성화 프레임(프로그램의 매개 변수, 국부 변수, 반환 값, 그리고 이 프로그램이 실행된 후에 이전 층의 명령 주소 등을 포함)을 생성하고 계산 제어를 다음 호출에 맡긴다.이 활성화 프레임들은 시스템에서 먼저 나온 창고에 존재한다.따라서 프로그램의 귀속 호출이 너무 크면 창고가 넘칠 수 있다.
귀속
컴퓨터 과학에서, 마지막 호출은 하나의 함수 중의 마지막 동작이 하나의 함수 호출 상황을 가리킨다. 즉, 이 호출의 반환 값이 현재 함수에 의해 직접 되돌아오는 상황을 가리킨다.
위에서 말한 귀속 함수는 여러 번 호출할 때 많은 활성 프레임을 보존해야 하기 때문에 창고가 넘칠 수 있습니다.그러나 미귀환을 채택하면 이 상황을 피할 수 있다.프로그램의 마지막 동작은 함수를 호출하는 것일 뿐 다른 계산 문제와 관련이 없기 때문에 많은 중간의 활성화 프레임을 삭제할 수 있다.위의 귀속 함수fib()와 같이 마지막 단계는 덧셈과 관련되기 때문에 꼬리 귀속이 아니지만 꼬리 귀속으로 바꿀 수 있다.다음과 같습니다.
int fib(int n,int f1,int f2)
{
// f1=0;f2=1
if(n==0)
return f1;
else
return fib(n-1,f2,f1+f2)
}
위 코드에서 볼 수 있듯이 함수의 마지막 호출은 하나의 함수로 다른 계산과 관련이 없다.
소결
귀속 함수는 반드시 귀속 기점이 귀속 끝 표지로 있어야 한다.
좋은 웹페이지 즐겨찾기
