今天面试碰到这样一个问题

Question

规则，每一步1变成10
            0变成01
一开始给你1个1问第n步后有几组连续的0（0的个数>=2）？例
起始       1                              0
第一步    10                              0
第二步    1001                            1
第三步    10010110                        1
第四步    1001011001101001                3
最后一列是答案，求此题解法  

Answer 1

用归纳法得出LS的答案(n-2)*2-1；

Answer 2

以1开始的话，第N步的连续0个数记为F(n),
以0开始的话，第N步的连续0个数记为G(n),F(n)=F(n-1)+G(n-1) 当n为奇数时，
F(n)=F(n-1)+G(n-1)+1，当n为偶数时。然后就变成了数学题。
我数学比较一塌糊涂。但楼上的(n-2)*2-1，似乎代入3和4都不对啊。

Answer 3

(n-2)*2-1
这个肯定不对，楼主的例子里第二部和第三部都只有一组连续的0。
感觉这道题没有公式，但是写代码的话很容易算出来。先把0换成其它字符，比如a，然后把1换成10，把a换成01，算出第n部的字符串后，统计有多少个00就可以了。最多只会有2个0在一起，绝对不会有3个0的。

Answer 4

public class Test {
private static int N=6; 
public static void main(String[] args) {
String s="1";
for(int i=0;i<N;i++){
s=func(s);
System.out.println(s+"次数为："+(s.split("00").length-1));
}
}
private static String func(String s){
return s.replaceAll("1", "a").replaceAll("0", "01").replaceAll("a", "10");
}
}=================
10次数为：0
1001次数为：1
10010110次数为：1
1001011001101001次数为：3
10010110011010010110100110010110次数为：5
1001011001101001011010011001011001101001100101101001011001101001次数为：11

Answer 5

用S表示当前00的个数，用A表示当前10的个数，用B表示当前1的个数。
S（n）=A(n-1)=B(n-2)+S(n-2);
所以递推公式是S(n)=B(n-2)+S(n-2)

Answer 6

public static int cal(int n){
int count = 0; //记录00组数目
StringBuffer sb = new StringBuffer("1");
//产生所要的 StringBuffer
for(int i = 0; i < n ; i++){
int length = sb.length();
for(int j= 0; j < length; j++){
if(sb.charAt(j) == '0')
sb.append('1');
if(sb.charAt(j) == '1')
sb.append('0');
   // System.out.println(sb);
}
}
// System.out.println( sb.toString());
//计算00组数目
for(int i = 0; i <sb.length(); i++){
if( i < sb.length() && sb.charAt(i) == '0' ){
if(++i <sb.length() && sb.charAt(i) =='0')
count++;
}
}
return count;
}

Answer 7

public class Test { 
    public static void main(String[] args) {
     for(int i=1;i<20;i++){
     System.out.println(fun(i));
     }
 
    }
    public static long fun(int n) {
     if(n==1){
     return 0;
     }
     if(n==2){
     return 1;
     }
     return fun(n-2)+(1<<(n-3));
    }
} 结果:
F:\java>java Test
0
1
1
3
5
11
21
43
85
171
341
683
1365
2731
5461
10923
21845
43691
87381

Answer 8

fun(n-2)+(1<<(n-3));
这个东西把我弄胡了半天,我原来是
fun(n-2)+1<<(n-3);
结果不对.弄了半天,原来是<<的优先级比+低。

Answer 9

设a(n)为第n步连续的0的个数
  n                                       a(n)第1步    10                                a(1)= 0 
第2步    1001                              a(2)= 1 
第3步    10010110                          a(3)= 1 
第4步    1001011001101001                  a(4)= 3
第5步    10010110011010010110100110010110  a(5)= 5可以归纳出来的规律是：a(n) = 2^(n-2)  -  a(n-1)
递归代入，a(n) = 2^(n-2) - 2^(n-3) + 2^(n-4) ... + ((-1)^(n-3))*(2^1) + ((-1)^(n-2))*(2^0) + ((-1)^(n-1))* 0
则通项公式：
          
           a(n) = (2^(n-1) + 1*(-1)^n) / 3//懒得推公式就直接用程序：
#include <iostream>
#include <math.h>
using namespace std;
int a(int n)
{
if (n == 1)
return 0;
return pow(2,n-2) - a(n - 1);
}int main()
{
int n;
cin>>n;
cout<<a(n)<<endl;
return 0;
}

Answer 10

用C写程序,求2^(n-2)还用pow函数？为什么不用位运算？

Answer 11

然后 S(n)=2^(n-4)+2^(n-6)+S(n-4) 递推即可得到公式

Answer 12

f(n)=2^(n-4)+f(n-2)    n>=4  ,n为层数，

Answer 13

f(n)=2f(n-1)-1  n为奇数且n>1;
f(n)=2f(n-1)+1 n为偶数且n>1；
当n=1时f(n)=0.
或这样：
    当n=1时f(n)=0.
   f(n) = ((-1)^(n-1))∑(((-1)^(n))2^(n-2)) n>1;
                      n>=2

Answer 14

f(n)=2^(n-1) - f(n-1) 或 f(n)=2 * f(n-1) + (-1)^(n-1) 
  long fun(int n)
        {
            if (n < 1)
            {
                return 0;
            }
            // 2 * fun(n-1)+ (-1)^(n-1)            
            return (1 << (n - 1)) - fun(n - 1);
        } 

Answer 15

同38楼，就是一数列问题。
n=1, f(n) = 0;
n>=2, f(n) = 2^(n-2) - f(n-1)

Answer 16

 f(n)=2^(n-2) - f(n-1) 或 2 * f(n-1) + (-1)^(n) (上次把基数弄错了，呵呵稍微调整一下就好)
long fun(int n)
        {
            if (n < 2)
            {
                return 0;
            }
            //2^(n-2) - f(n-1)   
            return (((long)1) << (n -2)) - fun(n - 1);
        } 

Answer 17

bigbug9002  的答案最好了，相当的强悍