将数字字符串分割成小于26的数字的方法计数

Question

将数字字符串分割成小于26的数字的方法计数

c++algorithm

4

给定一个数字字符串，我想找到将该字符串分解为小于26的单个数字的方法数。

例如，"8888888"只能被分解为"8 8 8 8 8 8 8"。而"1234567"可以被分解为"1 2 3 4 5 6 7"、"12 3 4 5 6 7"和"1 23 4 5 6 7"。

我想要一个递归关系的解决方案，并且需要使用动态规划的代码。

这是我目前得到的内容。它仅涵盖了基本情况，即空字符串应返回1，一个数字字符串应返回1，所有数字都大于2的字符串应返回1。

int countPerms(vector<int> number,  int currentPermCount)
{
    vector< vector<int> > permsOfNumber;
    vector<int> working;
    int totalPerms=0, size=number.size();
    bool areAllOverTwo=true, forLoop = true;

    if (number.size() <=1)
    { 
        //TODO: print out permetations
        return 1;
    }
    for (int i = 0; i < number.size()-1; i++) //minus one here because we dont care what the last digit is if all of them before it are over 2 then there is only one way to decode them
    {
        if (number.at(i) <= 2)
        {
            areAllOverTwo = false;
        }
    }
    if (areAllOverTwo) //if all the nubmers are over 2 then there is only one possable combination 3456676546 has only one combination.
    {
        permsOfNumber.push_back(number);
        //TODO: write function to print out the permetions
        return 1;
    }
    do
    {
        //TODO find all the peremtions here
    } while (forLoop);

    return totalPerms;
}

- Lupus

2

你能详细说明为什么 '88888888' 返回 1，而 '12345678' 返回 3 吗？ - billz

@billz 当输入'88888888'时，它返回1，因为26以下的唯一数字是8，所以得到字符串'88888888'的唯一方法就是这个字符串本身。至于'12345678'，数字会变成'1 2 3 4 5 6 7 8'、'12 3 4 5 6 7 8'和'1 23 4 5 6 7 8'。 - Lupus

所以，您想找到将字符串拆分为数字（对或单个数字）的不同方式的数量，这些数字小于26。现在，为此，您可以始终使用彼此构建的不同子字符串，这就是线性编程可能会派上用场的原因。例如，1234可以拆分为1和234的不同拆分，或者拆分为12和34的不同拆分。 - Ulrich Eckhardt

数字可以以 0 开头吗？（因此 101 可以是 1 0 1，10 1 或 1 01 吗？） - Jarod42

@Jarod42 是的，它可以以0开头，但0必须单独计算。（因此，“101”只能是“1 0 1”，同样，“010”只能是“0 1 0”） - Lupus

显示剩余4条评论

3个回答

1

另一种思考方式是，除了最初的单个数字可能性外，在每个连续可能数字对（例如111或12223）的序列中，长度为n，我们将结果乘以：

1 + sum, i=1 to floor (n/2), of (n-i) choose i

例如，对于序列11111，我们可以有：

i=1, 1 1 1 11 => 5 - 1 = 4 choose 1 (possibilities with one pair)
i=2, 1 11 11 => 5 - 2 = 3 choose 2 (possibilities with two pairs)

这似乎与维基百科对Fibonacci数列“在数学中的应用”有直接关系，例如，在计算“由1和2组成的总和为给定总数n的组合数量”方面（http://en.wikipedia.org/wiki/Fibonacci_number）。

使用组合方法（或其他快速的Fibonacci方法）可能适用于具有非常长序列的字符串。

- גלעד ברקן

1

如果我理解正确，只有25种可能性。我的第一步是初始化一个由25个int组成的数组，全部设置为零，当我找到小于25的数字时，将该索引设置为1。然后，在完成查看字符串后，我将计算数组中所有1的数量。

你说的“recurrence”是什么意思？如果您正在寻找递归函数，您需要找到一种将数字字符串递归拆分的好方法。我不确定这是最佳方法。我会逐位查看数字，如果数字小于或等于2，则存储它并测试添加下一个数字...即10 * digit + next。希望这有所帮助！祝你好运。

- John

通过递归，我指的是像找到斐波那契数列公式一样的东西，即F(n) = F(n-1) + F(n-2)。但是我的函数不应该是递归的。 - Lupus

这个想法不错，但它只会给我可能的字符串之一。如果我正确地按照逻辑来处理字符串12121212，那么你的数组看起来应该是这样的[0,4,4,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,3,0,0,0,0]，或者我只是搞砸了你的想法？ - Lupus

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Hankin · Accepted Answer

假设您没有零，或者不允许以零开头的数字，则递归关系如下：

N(1aS) = N(S) + N(aS)
N(2aS) = N(S) + N(aS) if a < 6.
N(a) = 1
N(aS) = N(S) otherwise

这里，a指的是一个数字，S指的是一个数。递归关系的第一行表示如果你的字符串以1开始，则可以将其单独使用或与下一个数字连接。第二行表示如果你以2开头，则可以将其单独使用或将其与下一个数字连接，假设这样可以得到一个小于26的数字。第三行是终止条件：当你只剩下1个数字时，结果为1。最后一行表示如果你无法匹配前面的规则之一，则第一个数字不能与第二个数字连接，因此它必须独立存在。

递归关系可以直接实现为迭代式动态规划解决方案。以下是Python代码，但很容易转换成其他语言。

def N(S):
    a1, a2 = 1, 1
    for i in xrange(len(S) - 2, -1, -1):
        if S[i] == '1' or S[i] == '2' and S[i+1] < '6':
            a1, a2 = a1 + a2, a1
        else:
            a1, a2 = a1, a1
    return a1

print N('88888888')
print N('12345678')

输出：

1
3

有趣的观察是，N('1' * n) 是第 n+1 个斐波那契数：

for i in xrange(1, 20):
    print i, N('1' * i)

输出：