随笔：递归的妙用<1>

起因

昨天闲的蛋疼在百度知道回答问题，看到一个很有趣的题目，要求用递归实现如下的输出

1
5 2
8 6 3
10 9 7 4

想了一段时间， 自己写了个代码，差不多实现了这功能，却又懒得去优化一下。好久没做算法题目lower_bound的参数都记得不太清楚了，不过还好自己写出来的没错，程序成功运行。

代码+结果

代码如下

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
#define LL long long
using namespace std;
const LL inf = 1e18;
const LL mod = 1e9+7;
int s[10] = {1, 3, 6, 10, 15, 21, 27};
int m;
void f(int n, int k, int cnt) {
    if(n == 1) {
        return;
    }
    else if(cnt == 0) {
        cnt = m - k - 1;
        k = m;
        f(cnt + 1, k, cnt);
        printf("%d\n", cnt + 1);
    }else {
        f(n + k, k - 1, cnt - 1);
        printf("%d ", n + k);
    }
}
int main() {
    //1 3 6 10 15 21 27
    //1 2 3 4  5  6  7
    //s = (1 + n) * n / 2
    int n;
    while(scanf("%d", &n) != EOF) {
        int k = lower_bound(s, s + 7, n) - s;
        m = k;
        f(k + 1, k, k);
        printf("%d\n", k + 1);
    }
    return 0;
}

结果如图

小结

有时间做做这类型的题目也很有意思，锻炼一下思维还是有好处的，这个写的比较烂，如果有更好的方法，不如说出来大家共同探讨一下。