for 순환 안의 귀속 호출 연구
8490 단어 귀속
for 순환 안의 귀속 호출 연구
귀환은 원래 순환 문제를 간소화하려고 하지만, 프로그램에서는 왕왕 for와 귀환을 함께 사용하는 경우가 있다.
우리는 for 안에서 for를 할 수 있거나, for 안의 for가 다시 for를 할 수 있다면, 모두 매우 직관적으로 이해할 수 있다.
for에 귀환이 들어가면 이해의 차원이 3차원에서 4차원으로 뛰기 때문에 직접 보기 어렵고 무한한 상상력에 의존해야 한다.
먼저 작은 코드를 분석해 보겠습니다.
이 코드에서 포는 귀속 호출을 할 수 있는데, 당신은 포가 실행하는 결과를 어떻게 예측해야 한다고 생각합니까?
#include <stdio.h>
#include <stdlib.h>
void recur(int, int);
static int count = 0;
int main(int argc, char **argv)
{
if(argc < 2)
{
printf("args need a interger
");
return -1;
}
int n = atoi(argv[1]);
recur(0, n);
printf(" COUNT= %d
", count);
return 0;
}
void recur(int i, int n)
{
count++;
printf("B>");
for(i; i <= n; i++){
printf("I>");
recur(i + 1, n);
printf("R>");
}
}n회의 for 순환 실행 횟수는 n이고 n회의 귀속 호출 횟수도 n이다. 둘을 합치면 이상적인 상태는 n2회일 것이다. 그러나 귀속의 특성 때문에 복잡도가 크게 증가했다.코드의 집행을 분석해 보도록 하겠습니다.
1.n=1시 프로그램의 출력은 B>I>B>I>B>R>R>I>B>R>COUNT=42.즉recur가 4번 호출되었는데, 우리가 예상한 결과 n2와 같다.n=2시, 프로그램 출력은 B>I>B>I>B>I>B>R>I>B>R>R>I>B>I>B>R>R>I>B>R>I>B>R>R>R>COUNT=84.이때 Recur 호출 횟수는 2n이다. 이어서 우리는 서로 다른 n 테스트를 해서 2n의 정확성을 검증했다.왜 for 순환으로 귀속을 호출해야 합니까?그것은 문제를 해결하는 사고방식에서 시작해야 한다. 문제의 해결 사고방식은 다음과 같다.
(1) 하나의 문제가 존재한다. (2) 이 문제는 분해를 통해 작은 것과 같은 문제를 형성할 수 있다. (3) 작은 문제는 계속 작은 문제로 분해할 수 있다. (4) 마지막으로 가장 작은 문제는 문제가 아니다. 가장 작은 문제는 문제가 아니다. 예를 들어 n의 배열을 계산하는 문제이다. 우리는 그것을 계산(n - 1)으로 분해할 수 있다.(n−1)! 계속 분해(n-3-1-3)!마지막에 반드시 가장 작은 문제 하나를 얻어낼 것이다: 0!(5) 문제가 하나가 아닐 때 큰 문제가 존재한다. 그 안에 N개의 동등한 중문제가 있고 이 N개의 동등한 중문제는 모두 돌아가는 사고방식에 따라 문제를 풀 수 있다. 이럴 때 for로 N개의 문제를 두루 훑어보아야 한다.(6) 왜 for가 귀속할 수 있는 횟수가 2n입니까?그것은 매번의 for는 두 번의 함수를 호출해야 하기 때문이다. 그 중에서 for는 한 번 실행하고 for 호출은 다시 한 번 실행해야 하며 곱셈의 정리에 따라 하나의 과정이 두 단계로 나뉘면 첫 번째 단계는 m종의 가능한 결과가 있고 이 단계의 결과에 대해 두 번째 단계는 n종의 가능한 결과가 있기 때문에 지정된 횟수 순서에 따라 전체 과정을 완성하는 데 모두 mn가지 방법이 있다.이렇게 하면 2n이 나온다.
for 호출 귀속의 복잡성은 여기에 그치지 않는다. 여러분은 아래의 프로그램을 보십시오. 단지 위의 프로그램에 변수를 많이 넣어야 하기 때문에 프로그램의 운행 복잡도는 크게 증가했습니다.
#include <stdio.h>
#include <stdlib.h>
void recur(int, int);
static int count = 0;
int main(int argc, char **argv)
{
if(argc < 2)
{
printf("args need a interger
");
return -1;
}
int n = atoi(argv[1]);
recur(0, n);
printf(" COUNT = %d
", count);
return 0;
}
void recur(int i, int n)
{
int j;
count++;
printf("B>");
for(j = i; j <= n; j++){ /* i j*/
printf("I>");
recur(i + 1, n);
printf("R>");
}
}n이 1이면 실행 결과는 다음과 같습니다.
B>I>B>I>B>R>I>B>I>B>R>R>R>COUNT=5 프로그램에서 모두 다섯 차례의 Recur 함수를 호출했습니다.
n이 2인 경우 실행 결과는 다음과 같습니다.
B>I>B>I>B>I>B>R>R>I>B>I>B>R>I>B>I>B>I>I>B>B>R>R>I>B>I>B>R>R>R>R>R>I>B>I>I>B>R>I>B>R>R>R>R>R>R>R>R>R>R>R>R>R>R>R>COUNT=16 recur 함수의 호출이 한 번에 16번 올라갔어요.
n이 3이면 실행 결과는 다음과 같습니다.
B>I>B>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>R>I>B>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>R>I>B>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>R>I>B>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>I>B>I>B>I>B>R>R>I>B>I>B>R>R>R>R> COUNT=65 n=3시는 더욱 무섭다. 아래 n의 수치가 10시와 같으면 프로그램의 실행 결과가 되돌아오기를 기다리는 것은 긴 과정이다.
n=1시 코드 실행 절차를 분석해 보도록 하겠습니다.
정리 절차: main() 호출 ① recur(i=0,)-> ① for (j=0, i=0) 호출 ② recur (i=1) -> ② for (j=1, i=0) -> ① for(j=0, i=0) 호출 -> ③ for (j=0, i=0) ② recur (i=1) (i=1) - 1) 호출 ③ recur (j=0, i=0) 호출 호출 호출 ② 호출 ② 호출 - 1 (j=0 =0, i=0) 호출 호출 - 1) - 1 (j+++ =2))) - 1 (j++ = 1 = 1 = 1 = 1 = 1 = 1) ② uri=1 = 1) ① ur (j=1, i=0) 호출 ④ recur(i=1)-> ④ for(j=i=1) 호출 ⑤ recur(i=2)-> ⑤ for(i=i=2) ⑤ recur(i=2)에서 ④ for(j=i=2) ④ recur(i=1) 호출① for (j=2, i=0) 을main ()에서 되돌려받을 때 주의해야 할 것은 ① for (j++) 에서 i값이 변하지 않고 0이며,recur를 호출할 때 i=i+1=2 이 값으로 호출된다는 것이다.
전체 과정의 복잡도를 보면 알 수 있다. 만약에 n이 1을 더 증가하면 나는 비인간적인 재능으로 명확하게 분석할 수 있기를 바란다.
좋은 웹페이지 즐겨찾기
