要求用到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就是要去除的...

谢谢 按照你的指导
我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;
}

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

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

1011
1101
被跳过了

不过还是很谢谢你

好棒...不过C语言看不懂...
能解释一下吗...

麻烦加点注释可以吗...
新人不是很懂