알고리즘 을 되 찾 는 길 - 재 귀 와 분할 기초

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 전재 출처 를 밝 혀 주 십시오.http://blog.csdn.net/lttree********************************************
이번 주말 에 집에 일이 좀 있어 서 집에 갔다 가 학습 계획 을 좀 끊 었 습 니 다.
꽉 채 워!
첫 번 째 알고리즘 - 재 귀 와 분할
알다 시 피 분 치 알고리즘 의 기본 사상 은
직접적 으로 해결 하기 어 려 운 문 제 를 규모 가 작은 똑 같은 문제 로 나 누 어 각각 격파 하고 나 누 어 해결 하도록 한다.
이렇게 하면 우 리 는 복잡 한 알고리즘 을 유형 이 변 하지 않 고 규모 가 점점 작 아 지면 서 최종 적 으로 서브 문 제 를 쉽게 풀 수 있 고 이 를 통 해 재 귀 알고리즘 을 도입 할 수 있다.
사실은 분 치 와 재 귀 는 쌍둥이 형제 처럼 알고리즘 디자인 에 동시에 사용 할 수 있 고 이 로 인해 많은 효율 적 인 알고리즘 이 생 긴 다.
돌아오다
개념: 직접 또는 간접 적 으로 자신의 알고리즘 을 호출 하 는 것 을 재 귀 알고리즘 이 라 고 하고 함수 자체 로 정 의 된 함 수 를 재 귀 함수 라 고 합 니 다.
다음은 몇 가지 재 귀적 인 전형 적 인 예 를 보 여 줍 니 다.
① 단계 곱 하기
정의:      
n！동 당 n = 0
n (n - 1) 과 같다!n > 0

int  factorial(int n)
{
    if( n == 0 )    return 1;
    return n*factorial(n-1);
}

② 피 보 나치 수열
하나의 무한 한 수열, 서열 은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 이다.
정의:
F (n) = 1 당 n = 0
= 1 당 n = 1
= F (n - 1) + F (n - 2) n > 1

<span style="font-size:18px;">int fibonacci(int n)
{
    if( n <= 1 )    return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}</span>

③ Ackerman 함수
이것 은 이중 귀속 함수 입 니 다. 함수 와 그 변수 가 함수 자체 에 의 해 정 의 될 때 이 함 수 를 이중 귀속 함수 라 고 합 니 다.
Ackerman 함수 A (n, m) 는 두 개의 독립 된 정형 변수 m ≥ 0, n ≥ 0 이 있 는데 그 정 의 는 다음 과 같다.
A（1,0） = 2 m≥0
A（0,m） = 1 n≥2
A（n,0） = n+2 n≥2
A（n,m） = A（A（n-1，m），m-1） n,m≥1

int Ackerman( int n , int m )
{
    if( n==1 && m==0 )    return 2;
    if( n==0 )    return 1;
    if( m==0 )    return n+2;
    return Ackerman( Ackerman(n-1,m),m-1);
}

④ 배열 문제
n 개 요 소 를 모두 배열 합 니 다.
n = 1 일 때 Perm (P) = (r), 그 중에서 r 는 집합 R 의 유일한 요소 이다.
n > 1 시, Perm (P) 은 (r1) Perm (R1), (r2) Perm (R2),......, (rn) Perm (Rn) 로 구성 된다.

template< class Type >

inline void Swap(Type& a,Type& b)
{
    Type temp = a;
    a = b;
    b = temp;
}

void Perm(Type list[],int k ,int m )
{
    if( k==m )
    {
        for( int i = 0 ; i <= m; ++i )    cout<<list[i];
        cout<<endl;
    }
    else
    {
        for( int i = k ; i <= m ; ++i )
        {
            Swap(list[k],list[i]);
            Perm(list,k+1,m);
            Swap(list[k],list[i]);
        }
}

⑤ 정수 구분 문제
정수 n 을 일련의 정수 의 합 으로 표시 하 다.
n = n1 + n2 +... + nk (그 중 n1 ≥ n2 ≥ n3 ≥... ≥ nk)
예 를 들 어 정수 6 에 대한 구분:
6
5+1
4+2 4+1+1
3+3 3+2+1 3+1+1+1
2+2+2 2+2+1+1 2+1+1+1+1
1+1+1+1+1+1
총 11 가지 구분
최대 가산 n1 이 m 보다 크 지 않 은 구분 개수 에 따라 q (n, m) 로 기록 하면 다음 과 같은 귀속 관 계 를 구축 할 수 있다.
< 1 > q (n, 1) = 1, n ≥ 1 - 최대 가산 n1 이 1 보다 크 지 않 을 때 그 어떠한 정수 n 도 하나의 구분 형식 만 있다.
< 2 > q (n, m) = q (n, n), n ≥ m - 최대 가산 n1 은 실제 n 보다 크 면 안 됩 니 다.그러므로 q (1, m) = 1
< 3 > q (n, m) = q (n, m - 1) + q (n - m, m), n > m > 1 - 정수 n 의 최대 가산 n1 이 m 보다 크 지 않 은 구분 은 n1 = m 와 n1 ≤ m - 1 의 구분 으로 구성 된다.
위 에서 말 한 바 와 같이 요약 하면 다음 과 같다.
q(n,m)=
1 n=1,m=1
q(n,n) n1+q(n,n-1) n=m
q(n,m-1)+q(n-m,m) n>m>1

int q( int n , int m )
{
    if( (n<1) || (m<1) )    return 0;
    if( (n==1) || (m==1) )    return 1;
    if( n==m )    return q(n,m-1)+1;
    return q(n,m-1)+q(n-m,m);
}

⑥ 하노이 타 워 문제
매우 전형 적 인 재 귀 문 제 는 문 제 를 군말 하지 않 고 바로 알고리즘 을 쓴다.

void hanoi( int n , int a , int b , int c )
{
    if( n > 0 ){
        hanoi( n-1,a,c,b);
        move(a,b);
        hanoi( n-1,c,b,a);
    }
}

분 치
전에 도 말 했 듯 이 분 치 법의 기본 사상 은 규모 가 큰 문 제 를 서로 독립 되 고 원래 의 문제 와 똑 같은 소 규모 문제 로 나 누 는 것 이다.
그것 의 알고리즘 디자인 모델 은 다음 과 같다.

divide-and-conquer(P)
{
    if( |P| <= n0 )    adhoc(P);
    divide P into smaller subinstances P1,P2,P3,...,Pk;
    for( i = 1 ; i <= k ; ++i )
        yi = divide-and-conquer(Pi);
    return merge(y1,y2,...,yk);
}

이 가운데
| P | 문제 P 의 규 모 를 표시 합 니 다.
n0 은 1 궐 값 으로 현재 문제 P 의 규모 가 n0 을 초과 하지 않 을 때 문 제 를 쉽게 풀 수 있 고 더 이상 분해 할 필요 가 없다 는 것 을 나타 낸다.
adhoc(P)  이 분 치 법 중의 기본 서브 알고리즘 으로 쉽게 풀 수 있 는 문제 에 대해 직접 풀 수 있다.
merge(y1,y2...yk)    병합 서브 알고리즘 입 니 다. P 의 하위 문제 P1, P2,..., Pk 의 풀이 y1, y2,..., yk 를 P 로 합 친 풀이 입 니 다.
분 치 법의 계산 효율 은 보통 재 귀 방정식 으로 분석 하 는데 상기 디자인 모델 에 대해 | P | = n 의 문 제 를 푸 는 데 필요 한 계산 시간 은 다음 과 같다.
T(n) =   O (1) n = 1
             kT (n / m) + f (n) n > 1
이상 은 재 귀 와 분 치 의 기본 사상 과 원칙 이 고 다음 의 박문 은 구체 적 인 사례 로 설명 할 것 이다.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 전재 출처 를 밝 혀 주 십시오.http://blog.csdn.net/lttree********************************************