注册 登录
编程论坛 → C++教室

新手求助 这个问题可以优化吗

bbb222 发布于 2012-11-18 08:41， 1291 次点击
要求用到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


21 回复
#2
bbb2222012-11-18 08:55
#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就很卡了
#3
wp2319572012-11-18 08:59
程序目的要求是啥啊
那些英文看不懂啊
#4
bbb2222012-11-18 09:03
回复 3楼 wp231957
输入一个数 这个数代表声音的气 1是上声 0是下声 不能连续1
例如 输入 3 ，有000 001 010 011 100 101 110 111，
011和110和111就是要去除的...
#5
elic_20002012-11-18 09:23
初步分析一下：
根据题意，输入N，简单的做法是要遍历2的N次方个数，其中有一部分是要去除的。
假定你的算法很优化（能直接不遍历那些需要去除的数），假定任何情况下都有一半是要去除的。
那么对于给定一个N=32的时候，你需要遍历的数达到了2的31次方，即2G个数。
知道这是什么概念么，即使空的循环2G次，稍差一点的机器也会卡的，如果是2的44次方，
那是16T了，对于现在的个人电脑，想在数秒内完成，几乎不可能。
#6
elic_20002012-11-18 09:29
因此需要换一个思路来解题。
对于一个给定的N。求连续两个1的个数、3个1的个数。。。一直到全部1的个数，汇总得T，
最后将2的N次方减去T即为所得。
#7
bbb2222012-11-18 09:43
回复 5楼 elic_2000
谢谢 按照你的指导
我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;
}
#8
elic_20002012-11-18 09:53
还可以进一步简化：
对于一个给定的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。
#9
bbb2222012-11-18 09:58
回复 8楼 elic_2000
我得到的数据是
1-2
2-3
3-5
4-8
5-13
6-21
7-34
.
.
.
#10
bbb2222012-11-18 10:14
回复 8楼 elic_2000
这里面有什么问题，
那个公式的思路感觉是对的
数据却不对
根据公式
数据如下
2-3
3-5
4-10
5-22
6-49
.
.
.
#11
bbb2222012-11-18 10:25
回复 8楼 elic_2000
1011
1101
被跳过了
#12
elic_20002012-11-18 10:30
嗯，我分析得还不够全面，忽略一些情况。
#13
bbb2222012-11-18 11:15
回复 12楼 elic_2000
不过还是很谢谢你
#14
elic_20002012-11-18 18:23
这个问题我想得简单了点，仔细分析之后，感觉应该是这样的：
1、对于给定的N，要想不出现连续的1，那么该比特串最多只能包含K个1，其中K=(N+1)/2取整；
2、接下来就是求0~K个1的比特串分别有多少种情况；
3、对于m个1，剩下0的有N-m个，这N-m个0共形成N-m+1个空档，将这m个1填入这N-m+1个空档就一定不会出现1紧挨的情况；
4、因此对于m个1，其情况就是C(N-m+1,m)，即N-m+1取m的组合。
5、对于全部是0的情况当个案，其情况数为1。
6、汇总之后就是：

若N为偶数，则满足要求的数量是G=C(N,1)+C(N-1,2)+...+C(K,K-1) + 1，其中K=N/2
若N为奇数，则满足要求的数量是G=C(N,1)+C(N-1,2)+...+C(K,N-K+1) + 1，其中K=（N+1）/2
#15
elic_20002012-11-18 21:06
纠正：
若N为偶数，则满足要求的数量是G=C(N,1)+C(N-1,2)+...+C(K+1,K) + 1，其中K=N/2

代码如下：

// 求n取m的组合
static __int64 ComputeC( unsigned int n, unsigned int m )
{
  __int64 iResult = 0;
  double dResult = 0;
  __int64 iDev;
  if ( m <= n )
  {
    if ( m > ( n / 2 ) )
    {
      m = n - m;
    }
    iResult = 1;
    for( unsigned int i = 0; i < m; i++ )
    {
      iResult *= ( n - i );
      iDev = i + 1;
      iResult /= iDev;
    }
  }
  return iResult;
}

// 计算bits个比特为不含任意连续1的所有可能取值
static __int64 ComputeA( unsigned int bits )
{
  __int64 iResult = 0;
  unsigned int k = ( bits + 1 ) / 2;
  if ( !( bits & 1 ) )
  {
    k++;
  }
  for( unsigned int i = k; i <= bits; i++ )
  {
    iResult += ComputeC( i, bits - i + 1 );
  }
  return iResult + 1;
}

有点惊讶，其结果符合兔子数的规律：
001 -->                2
002 -->                3
003 -->                5
004 -->                8
005 -->               13
006 -->               21
007 -->               34
008 -->               55
009 -->               89
010 -->              144
011 -->              233
012 -->              377
013 -->              610
014 -->              987
015 -->             1597
016 -->             2584
017 -->             4181
018 -->             6765
019 -->            10946
020 -->            17711
021 -->            28657
022 -->            46368
023 -->            75025
024 -->           121393
025 -->           196418
026 -->           317811
027 -->           514229
028 -->           832040
029 -->          1346269
030 -->          2178309
031 -->          3524578
032 -->          5702887
033 -->          9227465
034 -->         14930352
035 -->         24157817
036 -->         39088169
037 -->         63245986
038 -->        102334155
039 -->        165580141
040 -->        267914296
041 -->        433494437
042 -->        701408733
043 -->       1134903170
044 -->       1836311903
045 -->       2971215073
046 -->       4807526976
047 -->       7778742049
048 -->      12586269025
049 -->      20365011074
050 -->      32951280099
051 -->      53316291173
052 -->      86267571272
053 -->     139583862445
054 -->     225851433717
055 -->     365435296162
056 -->     591286729879
057 -->     956722026041
058 -->    1548008755920
059 -->    2504730781961
060 -->    4052739537881
061 -->    6557470319842
062 -->   10610209857723
063 -->   17167680177565
064 -->   27777890035288
065 -->   44945570212853
066 -->   72723460248141
067 -->  117669030460994
068 -->  190392490709135
069 -->  308061521170129
070 -->  498454011879264
#16
rjsp2012-11-19 09:23
回复 15楼 elic_2000
分析得实在精彩，像这么复杂的组合排列我搞不定。
我根据你的结果，想出另一种思路，
对于 abcdefgh……
a可以取0
a也可以取1，但a取1的话，则b必须取0
即 abcdefgh……的数量 = bcdefgh……的数量 + cdefgh……的数量
即公式 f(n) = f(n-1) + f(n-2)
f(1)=2; f(2)=3;

程序代码：
#include <stdio.h>

int main()
{
    unsigned long long a = 2;
    unsigned long long b = 3;
    printf( "%03u -->%20llu\n", 1, a );
    printf( "%03u -->%20llu\n", 2, b );

    for( size_t i=3; i<=91; ++i )
    {
        unsigned long long c = a+b;
        a = b;
        b = c;
        printf( "%03u -->%20llu\n", i, c );
    }

    return 0;
}
#17
rjsp2012-11-19 09:23
回复 15楼 elic_2000
分析得实在精彩，像这么复杂的组合排列我搞不定。
我根据你的结果，想出另一种思路，
对于 abcdefgh……
a可以取0
a也可以取1，但a取1的话，则b必须取0
即 abcdefgh……的数量 = bcdefgh……的数量 + cdefgh……的数量
即公式 f(n) = f(n-1) + f(n-2)
f(1)=2; f(2)=3;

程序代码：
#include <stdio.h>

int main()
{
    unsigned long long a = 2;
    unsigned long long b = 3;
    printf( "%03u -->%20llu\n", 1, a );
    printf( "%03u -->%20llu\n", 2, b );

    for( size_t i=3; i<=91; ++i )
    {
        unsigned long long c = a+b;
        a = b;
        b = c;
        printf( "%03u -->%20llu\n", i, c );
    }

    return 0;
}
#18
rjsp2012-11-19 09:25
代码可以简化
程序代码：
#include <stdio.h>

int main()
{
    unsigned long long a = 1;
    unsigned long long b = 1;
    for( size_t i=1; i<=91; ++i )
    {
        unsigned long long c = a+b;
        a = b;
        b = c;
        printf( "%03u -->%20llu\n", i, c );
    }

    return 0;
}
#19
bbb2222012-11-19 20:31
回复 18楼 rjsp
好棒...不过C语言看不懂...
能解释一下吗...
#20
bbb2222012-11-19 20:32
回复 12楼 elic_2000
麻烦加点注释可以吗...
新人不是很懂
#21
rjsp2012-11-20 09:19
回复 19楼 bbb222
你让我给你解释C语言？
#22
elic_20002012-11-21 00:32
static __int64 ComputeA( unsigned int N );
static __int64 ComputeC( unsigned int n, unsigned int m );

// 求n取m的组合
// n取m的组合计算公式为：
// [n * ( n - 1 ) * ... * ( n - m + 1 )]/[m*(m-1)*...*1]
static __int64 ComputeC( unsigned int n, unsigned int m )
{
  __int64 iResult = 0;
  __int64 iDev;
  if ( m <= n )
  {
    if ( m > ( n / 2 ) )
    {
      // 对于c(n,m)当m> n/2时c(n,m)=c(n,n-m)
      // 因此为了简化计算，将m变成小于n/2的值
      m = n - m;
    }
    iResult = 1;
    for( unsigned int i = 0; i < m; i++ )
    {
      iResult *= ( n - i );   // 计算n*(n-1)*...*(n-m+1)
      iDev = i + 1;           // 同时除以1*2*..*m
      // 可以用数学方法证明先乘的乘数，同时除以小的除数
      // 可保证永远够除
      iResult /= iDev;
    }
  }
  return iResult;
}

// 计算bits个比特为不含任意连续1的所有可能取值
// 若N为偶数，则满足要求的数量是G=C(N,1)+C(N-1,2)+...+C(K+1,N-K+1) + 1，其中K=N/2
// 若N为奇数，则满足要求的数量是G=C(N,1)+C(N-1,2)+...+C(K, N-K+1) + 1，其中K=（N+1）/2
static __int64 ComputeA( unsigned int N )
{
  __int64 iResult = 0;
  unsigned int k = ( N + 1 ) / 2;
  if ( !( N & 1 ) )
  {
    // 对于偶数，从k+1开始计算
    k++;
  }
  for( unsigned int i = k; i <= N; i++ )
  {
    // 计算c( k, n-K+1)+...+c(N,1)
    // 当i=k时计算c(k, N-K+1)
    // 当i=N时计算c(N,1)
    iResult += ComputeC( i, N - i + 1 );
  }
  return iResult + 1;
}


另:
可以证明
c(n,k)+c(n,k+1)=c(n+1,k+1)

于是
当n为偶数时
f(n)   =         c(n,  0)+c(n,  1)+c(n-1,2)+...+c(k+1,k)
f(n+1) =c(n+1,0)+c(n+1,1)+c(n,  2)+c(n-1,2)+...+c(k+1,k+1)
f(n+2) =c(n+2,0)+c(n+2,1)+c(n+1,2)+c(n,  3)+...+c(k+2,k+1)

因c(n+1,0)=c(n+2,0)
c(n,0)+c(n+1,1)=c(n+2,1)
因此f(n+2)=f(n+1)+f(n)

当n为奇数时
f(n)   =         c(n,  0)  +c(n,  1)+c(n-1,2)+...+c(k+1,k-1)+c(k,k)
f(n+1) =c(n+1,0)+c(n+1,1)  +c(n,  2)+c(n-1,2)+...+c(k+1,k)
f(n+2) =c(n+2,0)+c(n+2,1)  +c(n+1,2)+c(n,  3)+...+c(k+2,  k)+c(k+1,k+1)

其中c(n+1,0)+c(n+1,1)=c(n+2,1)
c(n+2,0)=c(n,0)
c(k,k)=(k+1,k+1)
其它每组c(n,1)+c(n,2)=c(n+1,2)
也满足f(n+2)=f(n+1)+f(n)

根据上面，无论n为奇数或偶数都可以证明
f(n+2)=f(n+1)+f(n)

原来真的是兔子数啊。。。
1
©2025, BC-CN.NET
电脑版