UVA 580 Critical Mass

题目大意就是，对于输入的n，n<=30，求有多少个不超过n位2进制的数，有连续的3个1。

f（3）=1,111

f（4）=3，0111,1110,1111

f（5）=8,11100,11101,11110,11111,01110,01111,10111,00111

等等。。。

题目：

可以求出递推公式：list[i] = list[i - 1] * 2+ pow(2, i - 4) -list[i-4]

可以把右边理解为2部分。

第一部分，不管最左边的是L还是U，只要右边n-1个里面有3个连续的U，那么这n个也是的了，所以是 list[i - 1] * 2

第二部分，右边n-1个里面没有3个连续的U，但是最左边加了一个字符之后，就有了。

那么，这n个字符必须以UUUL开头，而且剩下的n-4个是不能有3个连续的U的，所以是pow(2, i - 4) -list[i-4]

代码1：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int list[31];
     
    
   

    

     

    
    

     

      	list[0] = 0;
     
    
   

    

     

    
    

     

      	list[1] = 0;
     
    
   

    

     

    
    

     

      	list[2] = 0;
     
    
   

    

     

    
    

     

      	list[3] = 1;
     
    
   

    

     

    
    

     

      	list[4] = 3;
     
    
   

    

     

    
    

     
	for (int i = 5; i < 31; i++)list[i] = list[i - 1] * 2 -list[i-4]+ pow(2, i - 4);
     
    
   

    

     

    
    

     
	for (int i = 0; i < 31; i++)cout << list[i] << ",";
     
    
   

    

     

    
    

     
	system("pause>nul");
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

因为我是win10，所以爽到爆的一点就是，dos是可以复制也可以粘贴的。

于是我把代码1的输出复制粘贴到代码2

代码2：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int list[31] = { 0, 0, 0, 1, 3, 8, 20, 47, 107, 238, 520, 1121, 2391, 5056, 10616, 22159, 46023, 95182, 196132, 402873, 825259, 1686408, 3438828, 6999071, 14221459, 28853662, 58462800, 118315137, 239186031, 483072832, 974791728 };
     
    
   

    

     

    
    

     
	int n;
     
    
   

    

     

    
    

     
	while (cin >> n)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (n == 0)break;
     
    
   

    

     

    
    

     

      		cout << list[n] << endl;
     
    
   

    

     

    
    

     

      	}	
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/52066885