要求用到45，我的程序到20就有点慢了
#include <iostream>
#include <cmath>
using namespace std;
void calculate();
int main()
{
  int times;
  cin >> times;
  for(int i = 0; i < times; i++)
  {
    cout << "Scenario #" << i+1 << ":" << endl;
    calculate();
  }
    return 0;
}
void calculate()
{
    int num;
    cin >> num;
    int t[num+1];
    t[0] = 1;
    int record[num];
    for(int i = 1; i <= num; i++)
        t[i] = t[i-1] * 2;
    int count = 0;
    for(int i = 0; i < t[num]; i++)
    {
        int temp = i;
        for(int j = num - 1; j >= 0; j--)
        {
            record[j] = temp / t[j];
            temp =temp - record[j] * t[j];
        }
        for(int j = 0; j < num - 1 ; j++)
        {
            if(record[j+1]==1 && record[j]==1)
            {
                count++;
                break;
            }
        }
    }
    cout << t[num]-count << endl;
}
Background

"KO-RE-A, KO-RE-A" shout 54,000 happy football fans after their team has reached the semifinals of the FIFA World Cup in their home country. But although their excitement is real, the Korean people are still very organized by nature. For example, they have organized huge trumpets (that sound like blowing a ship's horn) to support their team playing on the field. The fans want to keep the level of noise constant throughout the match.

The trumpets are operated by compressed gas. However, if you blow the trumpet for 2 seconds without stopping it will break. So when the trumpet makes noise, everything is okay, but in a pause of the trumpet, the fans must chant "KO-RE-A"!

Before the match, a group of fans gathers and decides on a chanting pattern. The pattern is a sequence of 0's and 1's which is interpreted in the following way: If the pattern shows a 1, the trumpet is blown. If it shows a 0, the fans chant "KO-RE-A". To ensure that the trumpet will not break, the pattern is not allowed to have two consecutive 1's in it.

Problem

Given a positive integer n, determine the number of different chanting patterns of this length, i.e., determine the number of n-bit sequences that contain no adjacent 1's. For example, for n = 3 the answer is 5 (sequences 000, 001, 010, 100, 101 are acceptable while 011, 110, 111 are not).

Input

The first line contains the number of scenarios.

For each scenario, you are given a single positive integer less than 45 on a line by itself.

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the number of n-bit sequences which have no adjacent 1's. Terminate the output for the scenario with a blank line.

Sample Input

2
3
1

Sample Output

Scenario #1:
5

Scenario #2:
2

#include <iostream>
#include <cmath>
using namespace std;
void calculate();
int main()
{
    int times;
    cin >> times;
    for(int i = 0; i < times; i++)
    {
        cout << "Scenario #" << i+1 << ":" << endl;
        calculate();
    }
    return 0;
}
void calculate()
{
    long int num, max, temp;
    cin >> num;
    char t[num];
    max = pow(2,num);
    for(int i = 0; i < num; i++)
    {
        t[i] = '0';
    }
    int count=0;
    for(int i = 1; i < max; i++ )
    {

        for(int j = 0; j < num ; j++)
        {
            if(t[j]=='0')
            {
                t[j]='1';
                //cout << t << "*"<<endl;
                break;
            }
            if(t[j]=='1')
            {
                t[j]='0';
            
            }
        }
        for(int j = 0; j < num - 1; j++)
        {
            if(t[j]=='1'&&t[j+1]=='1')
            {
                count++;
                break;
            }
        }

    }
    cout << max - count << endl;
}
换了一种思路 但还是不行 到30就很卡了

程序目的要求是啥啊
那些英文看不懂啊

输入一个数 这个数代表声音的气 1是上声 0是下声 不能连续1
例如 输入 3 ，有000 001 010 011 100 101 110 111，
011和110和111就是要去除的...

初步分析一下：
根据题意，输入N，简单的做法是要遍历2的N次方个数，其中有一部分是要去除的。
假定你的算法很优化（能直接不遍历那些需要去除的数），假定任何情况下都有一半是要去除的。
那么对于给定一个N=32的时候，你需要遍历的数达到了2的31次方，即2G个数。
知道这是什么概念么，即使空的循环2G次，稍差一点的机器也会卡的，如果是2的44次方，
那是16T了，对于现在的个人电脑，想在数秒内完成，几乎不可能。

因此需要换一个思路来解题。
对于一个给定的N。求连续两个1的个数、3个1的个数。。。一直到全部1的个数，汇总得T，
最后将2的N次方减去T即为所得。

谢谢 按照你的指导
我AC了代码改成了
#include <iostream>

using namespace std;

int main()
{
    int times;
    cin >> times;
    int a;
    int num[times];
    for(int i = 0; i < times; i++)
    {

        cout << "Scenario #" << i+1 << ":" << endl;
        num[0] = 2;
        cin >> a;
        num[1] = 3;
        for(int j = 2; j < a; j++)
        {
            num[j] = num[j-1] + num[j-2];
        }
        cout << num[a-1] << endl << endl;
    }
    return 0;
}

还可以进一步简化：
对于一个给定的N，求连续2个1的结果是
剩下的N-2个0可以全部在两1的前面，也可以部分在两个1的前面，
于是0个0在前面一直到N-2个0在前面，得到N-1种情况。其它的类推，对于全部1，可以想象
成剩余0个1，于是只有一种情况。
从而，对于N
从连续2个1开始，到全部1，
其情况是N-1、N-2、。。。1。
加起来就是一个梯形的面积（上底加下底，乘以高，除以2，这里上底为1，下底为N-1,
高（即个数）为N-1）,即（1+N-1)(N-1)/2 = N(N-1)/2

于是结果为2的N次方减去N(N-1)/2。

我得到的数据是
1-2
2-3
3-5
4-8
5-13
6-21
7-34
.
.
.

这里面有什么问题，
那个公式的思路感觉是对的
数据却不对
根据公式
数据如下
2-3
3-5
4-10
5-22
6-49
.
.
.