取数游戏 Description

Question

题目描述
我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是间隔一个的不能同时被取走，如果1表示取走，0表示不取走，则不能出现101的连续串。
如果你能算出一共有多少种取法，那么你会被天神小泰泰奖励。
输入
输入仅包含一个数n（1≤ n ≤ 25）。
输出
输出仅包含一个数你的答案。
样例
输入 复制
4
输出 复制
12
提示
递归穷举即可。答案在2147483647以内。

Answer 1

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath> 
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <iomanip> 
using namespace std;

int result = 0;
int a[30];
void output(int n)
{
    int i;
    for(i=0;i<=n-1;i++)
     {
          if (i < n - 2)
        {
            if (a[i] == 1 && a[i + 1] == 0 && a[i + 2] == 1)
            {
                return;
            }
        }
        if (i == n - 1)
        {
            result++;
        }
     }
}

void search(int m,int n)                                     
{
     int i;
    if(m==n)
     {
          output(n);
     }
     else
     {
          for(i=0;i<=1;i++)
          {
               a[m]=i;
               search(m+1,n);
          }
     }
}

int main()
{
    int array[30]={0,2,4,7,12,21,37,65,114,200,351,616,1081,1897,3329,5842,10252,17991,31572,55405,97229,170625,299426,525456,922111,1618192};
    int n;
    cin>>n;
    search(0,n);
    if(array[n] != result)cout<<"error"<<endl;
    cout<<result<<endl;
    result = 0;
    return 0;
}

源码给你你继续研究吧