geekdoc-python-zh/docs/askpython/number-of-possible-strings.md

查找没有连续 1 的可能字符串的数量

原文：https://www.askpython.com/python/examples/number-of-possible-strings

在本教程中，我们将了解一个非常有趣的问题，称为形成没有连续 1 的字符串。我们先来了解一下，在这个问题上，我们想达到什么目的？

我们有一个整数 n ，它是字符串的大小，即最终字符串中的位数。

我们的目标是得到没有连续 1 的 n 位字符串，这意味着: 11在字符串中是非法的。

现在，对于任何字符串，可能有两种情况: 如果第一个元素是 0 ，那么下一个元素可以是 0 或 1。 在另一种情况下，即**，第一个元素是 1** ，那么我们对下一个元素的唯一选择是 0。

我们的目标是找到满足上述条件的所有可能字符串的计数。

---

如何求没有连续 1 的可能字符串的个数？

这个问题可以通过手工方式或递归方法来解决。递归方法是解决这个问题的更好、更有效、更快的技术。

如果你想知道更多关于递归的知识，请阅读下面提到的教程。

了解更多关于递归的知识:Python 中的递归

这两个案例如下:

• 第一位是 1 ，然后我们将第二位设置为 0 并检查最后一个字符串中剩余的 n-2 位。
• 第一个数字是 0 ，然后我们检查字符串中剩余的 n-1 位

首先，让我们看看从 0 开始的 n 的较低值的答案。

| n 的值 | 可能字符串的数量 | | Zero | Zero | | one | 2 ( 0,1) | | Two | 3 (00,01,10) |

对于 n 大于 2 的所有情况，我们将考虑两种情况。

---

用 Python 实现递归

def count_no_ways(n):
    if(n==0):
        return 0
    if(n<3):
        return n+1
    return count_no_ways(n-1) + count_no_ways(n-2)

n = int(input())
print(count_no_ways(n))

输出:

10 144

---

我希望在本教程结束时，我希望你理解了问题、解决方案和解决方案的代码实现。

感谢您的阅读！快乐学习！😇

---