| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1291 人关注过本帖
标题:新手求助 这个问题可以优化吗
只看楼主 加入收藏
bbb222
Rank: 2
等 级:论坛游民
帖 子:31
专家分:54
注 册:2012-11-17
收藏
得分:0 
回复 8楼 elic_2000
1011
1101
被跳过了
2012-11-18 10:25
elic_2000
Rank: 2
等 级:论坛游民
帖 子:12
专家分:15
注 册:2012-11-4
收藏
得分:0 
嗯,我分析得还不够全面,忽略一些情况。
2012-11-18 10:30
bbb222
Rank: 2
等 级:论坛游民
帖 子:31
专家分:54
注 册:2012-11-17
收藏
得分:0 
回复 12楼 elic_2000
不过还是很谢谢你
2012-11-18 11:15
elic_2000
Rank: 2
等 级:论坛游民
帖 子:12
专家分:15
注 册:2012-11-4
收藏
得分:0 
这个问题我想得简单了点,仔细分析之后,感觉应该是这样的:
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
2012-11-18 18:23
elic_2000
Rank: 2
等 级:论坛游民
帖 子:12
专家分:15
注 册:2012-11-4
收藏
得分:0 
纠正:
若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
2012-11-18 21:06
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
回复 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;
}

2012-11-19 09:23
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
回复 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;
}

2012-11-19 09:23
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
代码可以简化
程序代码:
#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;
}
2012-11-19 09:25
bbb222
Rank: 2
等 级:论坛游民
帖 子:31
专家分:54
注 册:2012-11-17
收藏
得分:0 
回复 18楼 rjsp
好棒...不过C语言看不懂...
能解释一下吗...
2012-11-19 20:31
bbb222
Rank: 2
等 级:论坛游民
帖 子:31
专家分:54
注 册:2012-11-17
收藏
得分:0 
回复 12楼 elic_2000
麻烦加点注释可以吗...
新人不是很懂
2012-11-19 20:32
快速回复:新手求助 这个问题可以优化吗
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015375 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved