普及组Day2教案

递归专题

P1157 组合的输出

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n, r, x[25], len;
void work() {
    if (len == r) {
        for (int i=0; i<r; i++) printf("%3d", x[i]);
        printf("\n");
        return;
    }
    int last = len>0 ? x[len-1]+1 : 1;
    for (int i=last; i<=n; i++) { // 保证后面选择的数比前面都大
        x[len++] = i;
        work();
        len--; // 回溯
    }
}
int main() {
    scanf("%d %d", &n, &r);
    work();
    return 0;
}

Luogu P2386 放苹果

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int M, N, x[15], len, sum, K;
void work() {
    if (len == N) {
        if (sum == M) K++;
        return;
    }
    int last = len>0 ? x[len-1] : 0;
    for (int i=last; i<= M-sum; i++) {
        x[len++] = i;
        sum += i;
        work();
        sum -= i;
        len--;
    }
}
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        K = 0;
        scanf("%d %d", &M, &N);
        work();
        printf("%d\n", K);
    }
    return 0;
}