计算没有连续1的二进制字符串数-yiteyi-C++库

给定一个正整数N，计算长度为N的所有可能的不同二进制字符串，这样就没有连续的1。

null

例如：

Input:  N = 2Output: 3// The 3 strings are 00, 01, 10Input: N = 3Output: 5// The 5 strings are 000, 001, 010, 100, 101

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

这个问题可以用动态规划来解决。设a[i]是长度为i的二进制字符串的数目，这些字符串不包含任何两个连续的1，并且以0结尾。类似地，设b[i]是以1结尾的此类字符串的数目。我们可以将0或1附加到以0结尾的字符串，但只能将0附加到以1结尾的字符串。这就产生了递归关系：

a[i] = a[i - 1] + b[i - 1]b[i] = a[i - 1]

上述复发的基本情况是a[1]=b[1]=1。长度为i的字符串总数仅为a[i]+b[i]。下面是上述解决方案的实现。在以下实现中，索引从0开始。所以a[i]表示输入长度为i+1的二进制字符串的数量。类似地，b[i]表示输入长度为i+1的二进制字符串。

C++

                         // C++ program to count all distinct binary strings                       
                         // without two consecutive 1's                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     countStrings(                                     int                                     n)                       
                         {                       
                                                 int                                     a[n], b[n];                       
                                                 a[0] = b[0] = 1;                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 a[i] = a[i-1] + b[i-1];                       
                                                 b[i] = a[i-1];                       
                                                 }                       
                                                 return                                     a[n-1] + b[n-1];                       
                         }                       
           
           
                         // Driver program to test above functions                       
                         int                                     main()                       
                         {                       
                                                 cout << countStrings(3) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         class                                     Subset_sum                       
                         {                       
                                                 static                                     int                                     countStrings(                                     int                                     n)                       
                                                 {                       
                                                 int                                     a[] =                                     new                                     int                                     [n];                       
                                                 int                                     b[] =                                     new                                     int                                     [n];                       
                                                 a[                                     0                                     ] = b[                                     0                                     ] =                                     1                                     ;                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 {                       
                                                 a[i] = a[i-                                     1                                     ] + b[i-                                     1                                     ];                       
                                                 b[i] = a[i-                                     1                                     ];                       
                                                 }                       
                                                 return                                     a[n-                                     1                                     ] + b[n-                                     1                                     ];                       
                                                 }                       
                                                 /* Driver program to test above function */                       
                                                 public                                     static                                     void                                     main (String args[])                       
                                                 {                       
                                                 System.out.println(countStrings(                                     3                                     ));                       
                                                 }                       
                         }                                     /* This code is contributed by Rajat Mishra */                       

Python3

                         # Python program to count                       
                         # all distinct binary strings                       
                         # without two consecutive 1's                       
           
                         def                                     countStrings(n):                       
           
                                                 a                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (n)]                       
                                                 b                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (n)]                       
                                                 a[                                     0                                     ]                                     =                                     b[                                     0                                     ]                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,n):                       
                                                 a[i]                                     =                                     a[i                                     -                                     1                                     ]                                     +                                     b[i                                     -                                     1                                     ]                       
                                                 b[i]                                     =                                     a[i                                     -                                     1                                     ]                       
                                   
                                                 return                                     a[n                                     -                                     1                                     ]                                     +                                     b[n                                     -                                     1                                     ]                       
           
                         # Driver program to test                       
                         # above functions                       
           
                         print                                     (countStrings(                                     3                                     ))                       
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# program to count all distinct binary                       
                         // strings without two consecutive 1's                       
                         using                                     System;                       
           
                         class                                     Subset_sum                       
                         {                       
                                                 static                                     int                                     countStrings(                                     int                                     n)                       
                                                 {                       
                                                 int                                     []a =                                     new                                     int                                     [n];                       
                                                 int                                     []b =                                     new                                     int                                     [n];                       
                                                 a[0] = b[0] = 1;                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 a[i] = a[i-1] + b[i-1];                       
                                                 b[i] = a[i-1];                       
                                                 }                       
                                                 return                                     a[n-1] + b[n-1];                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 Console.Write(countStrings(3));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal                       

PHP

                         <?php                       
                         // PHP program to count all distinct                       
                         // binary stringswithout two                       
                         // consecutive 1's                       
           
                         function                                     countStrings(                                     $n                                     )                       
                         {                       
                                                 $a                                     [                                     $n                                     ] = 0;                       
                                                 $b                                     [                                     $n                                     ] = 0;                       
                                                 $a                                     [0] =                                     $b                                     [0] = 1;                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 $a                                     [                                     $i                                     ] =                                     $a                                     [                                     $i                                     - 1] +                       
                                                 $b                                     [                                     $i                                     - 1];                       
                                                 $b                                     [                                     $i                                     ] =                                     $a                                     [                                     $i                                     - 1];                       
                                                 }                       
                                                 return                                     $a                                     [                                     $n                                     - 1] +                       
                                                 $b                                     [                                     $n                                     - 1];                       
                         }                       
           
                                                 // Driver Code                       
                                                 echo                                     countStrings(3) ;                       
           
                         // This code is contributed by nitin mittal                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to count all                       
                         // distinct binary strings                       
                         // without two consecutive 1's                       
                         function                                     countStrings(n)                       
                         {                       
                                                 let a = [];                       
                                                 let b = [];                       
                                                 a[0] = b[0] = 1;                       
                                   
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 {                       
                                                 a[i] = a[i - 1] + b[i - 1];                       
                                                 b[i] = a[i - 1];                       
                                                 }                       
                                                 return                                     a[n - 1] + b[n - 1];                       
                         }                       
           
                         // Driver code                       
                         document.write(countStrings(3));                       
           
                         // This code is contributed by rohan07                       
           
                         </script>                       

输出：

时间复杂性： O（N）

辅助空间： O（N） 资料来源： 当然。csail。麻省理工学院。edu/6.006/oldquizzes/solutions/q2-f2009-sol。pdf 如果我们更仔细地观察这个模式，我们可以观察到，当n>=1时，计数实际上是（n+2）个斐波那契数。这个斐波那契数是0，1，1，2，3，5，8，13，21，34，55，89，141…。

n = 1, count = 2  = fib(3)n = 2, count = 3  = fib(4)n = 3, count = 5  = fib(5)n = 4, count = 8  = fib(6)n = 5, count = 13 = fib(7)................

因此，我们也可以使用方法5在O（logn）时间内计算字符串在这里 .

相关帖子： 二进制表示中没有连续1的1到n位数字。本文由 分析师拉胡尔贾殷 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章