#不连续1的子串#递归与分治#acwing#中山大学机试

https://www.acwing.com/problem/content/3709/

/*请计算长度为 N且不含连续 1的 01串的个数。
例如，当 N=3时，答案为 5，因为长度为 3且不含连续 1的 01串一共 5个：000,001,010,100,101。
输入格式
一个整数 N。
输出格式
一个整数，表示结果。
数据范围
1≤N≤20*/

#include <iostream>
#include <cstdio>
#include <stack>
#include <string>

using namespace std;
int fun0(int i);
int fun1(int i);
int fun0(int i){
    if(i==1){
        return 1;
    }
    else {
        return fun0(i-1)+fun1(i-1);
    }
}
int fun1(int i){
    if(i==1){
        return 1;
    }
    else{
        return fun0(i-1)
    }
}
int main(){
    int n;
    scanf("%d",&n);
    printf("%d",fun0(n)+fun1(n));
    return 0;
}