귀속(분치)

분치(divide and conquer): 원래의 문제를 규모가 비교적 작은 구조와 원문제가 같거나 비슷한 자문제로 나누어 각각 이 자문제를 해결하고 마지막에 자문제를 합쳐서 원문제의 해를 얻는다.

1. n의 곱셈을 되돌려 구한다

#include 
using namespace std;
int F(int n) {
    if (n == 0) return 1;
    else return F(n - 1) * n;
}
int main() {
    int n;
    scanf("%d",&n);
    cout<return 0;
}

1. n = 3 을 입력합니다.호출 F(3), 2.n≠≠0, F(2)*3 반환;3.n = 2≠0, F(1)*2로 돌아가기;4.n = 1≠0, F(0)*1로 되돌아오기;5,n = 0, F(0) = 1; 6.F(1) = 1; 7.F(2) = F(1) * 2 = 2; 8.F(3) = F(2) * 3 = 6;

2.Fibonacci 수열의 n항

앞에 열거한 항목 1, 2, 3, 5, 8, 13, 21......F(0) = 1, F(1) = 1, F(n) = F(n-1) + F(n-2) (n>=2)

#include 
using namespace std;
int F(int n) {
    if (n == 0 || n == 1) return 1;
    else return F(n - 1) + F(n - 2);
}
int main() {
    int n;
    scanf("%d",&n);
    cout<return 0;
}

1, n = 3 을 입력하고 F (2) + F (1) 를 반환합니다.2, F(1) = 1; F(2) = F(0) + F(1) = 2; 3. F(3) = 3;

3. 전체 정렬(Full Permutation)

전체 배열은 n개의 정수의 모든 배열을 가리키며 작은 순서에서 큰 순서로 n개의 정수를 출력하는 전체 배열을 말한다. 그 중에서 (a1, a2,....an a 1,a2,.... a n)의 순서가 (b1,b2...bn b 1,b 2..bn)보다 작다(b1=b1,a2=b2...an=bn,ai#include using namespace std; const int maxn = 4; int n, P[maxn], hashTable[maxn] = {false}; void generateP(int index) { if (index == n+1) { for (int i = 1; i <= n; i++) { cout<

cout<for (int x = 1; x <= n; x++) { if (hashTable[x] == false) { P[index] = x; hashTable[x] = true; generateP(index + 1); hashTable[x] = false; } } } int main() { n = 3; generateP(1); return 0; }