6

我有一个字符串，其大小可以大到“10,000”。我必须计算那些能被 9 整除的子序列。

子序列：子序列是保持给定字符串的字符顺序的排列。例如：如果给定字符串是 10292，那么它的一些子序列是 1、102、10、19、12、12（12 是 2 的两倍）、129、029、09、092 等。有些数字不是给定字符串的子序列是：201（2 和 0 不能在 1 之前）、921、0291 等。

我尝试使用位移生成给定字符串的所有子序列（powerset），并检查每个字符串是否可被 9 整除。但只要字符串的长度<=10，这就可以正常工作。之后，我没有得到正确的子序列（一些子序列显示为负数）。

下面是我的代码：

    scanf("%s", &str); //input string 

    int n=strlen(str); //find length of string

    //loop to generate subsequences
    for(i=1;i<(1<<n);++i){

        string subseq;

        for(j=0;j<n;++j){

            if(i&(1<<j)){

                subseq+=str[j]; // generate subsequence
            }
        }

        //convert generated subseq to int; number is 'long' tpye
        number=atol(subseq.c_str());printf("%ld\n", number); 

        //ignore 0 and check if number divisible by 9
        if(number!=0&&number%9==0)count++;
    }

        printf("%ld\n", count);
4

4 回答 4

4

由于一个数字可以被 9 整除当且仅当它的数字之和可以被 9 整除，所以你可以使用O(n)递归算法来解决这个问题。

这个想法如下：在每一步，将子序列分成两个并确定（递归地）有多少序列的数字之和为i % 9，i范围从0到8。然后，您通过以下方式“合并”两个表，为整个范围构建同一个表O(1)。假设L是左侧拆分表和右侧拆分表R，您需要F为整个范围构建表。

然后你有：

for (i = 0; i < 9; i++) {
  F[i] = L[i] + R[i];
  for (j = 0; j < 9; j++) {
    if (j <= i)
      F[i] += L[j] * R[i - j]
    else
      F[i] += L[j] * R[9 + i - j]
  }
}

只有一位数字的子序列的基本情况d很明显：只需将F[d % 9] = 1所有其他条目设置为零。

完整的 C++11 实现：

#include <iostream>
#include <array>
#include <tuple>
#include <string>

typedef std::array<unsigned int, 9> table;

using std::tuple;
using std::string;

table count(string::iterator beg, string::iterator end)
{
    table F;
    std::fill(F.begin(), F.end(), 0);
    if (beg == end)
        return F;
    if (beg + 1 == end) {
        F[(*beg - '0') % 9] = 1;
        return F;
    }
    size_t distance = std::distance(beg, end);
    string::iterator mid = beg + (distance / 2);
    table L = count(beg, mid);
    table R = count(mid, end);

    for (unsigned int i = 0; i < 9; i++) {
        F[i] = L[i] + R[i];
        for(unsigned int j = 0; j < 9; j++) {
            if (j <= i)
                F[i] += L[j] * R[i - j];
            else
                F[i] += L[j] * R[9 + i - j];
        }
    }
    return F;
}

table count(std::string s)
{
    return count(s.begin(), s.end());
}

int main(void)
{
    using std::cout;
    using std::endl;
    cout << count("1234")[0] << endl;
    cout << count("12349")[0] << endl;
    cout << count("9999")[0] << endl;
}
于 2012-08-03T18:00:33.287 回答
4

我有个主意！

由于您只需要计算子字符串，因此您不必关心它们实际上是什么。因此，您可以只存储它们可能总和的计数。

那么，如果你有一个函数可以组合两个子串集的计数表，并给你它们组合的计数呢？

既然我知道这是一个可怕的解释，我会举一个例子。假设你得到了号码：

2493

将其分成两半并继续拆分，直到获得单个数字：

   2493
   /  \
 24    93
 /\    /\
2  4  9  3

可以2总结什么？容易： 2。并且4只能求和4。您可以构建每个值有多少子字符串总和的表（mod 9）：

   0 1 2 3 4 5 6 7 8
2: 0 0 1 0 0 0 0 0 0
4: 0 0 0 0 1 0 0 0 0
9: 1 0 0 0 0 0 0 0 0
3: 0 0 0 1 0 0 0 0 0

组合两个表很容易。添加第一个表、第二个表以及两个 mod 9 的每个组合（对于第一个组合，这相当于2、4和24；对于第二个、9、3和93）：

    0 1 2 3 4 5 6 7 8
24: 0 0 1 0 1 0 1 0 0
93: 1 0 0 2 0 0 0 0 0

然后再做一次：

      0 1 2 3 4 5 6 7 8
2493: 3 0 2 2 2 2 2 2 0

这就是你的答案，坐在0专栏里： 3。这对应于子字符串243、2493和9。但是，您不知道，因为您只存储了计数 - 幸运的是，您不在乎！

一旦实施，这将为您提供O(n)性能 - 您只需弄清楚如何在O(1). 但是，嘿 - 作业，对吧？祝你好运！

于 2012-08-03T18:19:26.287 回答
0

如果你使用int那么你不应该把它左移太多。如果这样做，则设置符号位。使用无符号整数。或者不要离开太多。如果你坚持int ，你可以在完成后右移。

为了

printf("%ld\n", count);

printf 在显示长整数类型时可能会出现问题。你试过 cout 吗？

于 2012-08-03T17:33:26.943 回答
0

这是根据 Akappa 算法的 C++ 代码。然而，该算法对于包含一个或多个 0 的数字（即在“10292”和“0189”的情况下失败）但对“1292”和“189”给出正确答案。如果有人可以调试它以给出所有情况的答案，将不胜感激。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#include<cctype>
#include<list>
#include<set>
#include<set>
#include<map>
using namespace std;
typedef vector<int> table;
table count(string::iterator beg, string::iterator end)
{

    table F(9);
    std::fill(F.begin(), F.end(), 0);
    if (beg == end)
        return F;

    if (beg + 1 == end) {
        F[(*beg - '0') % 9] = 1;
        return F;
    }

    size_t distance = std::distance(beg, end);
    string::iterator mid = beg + (distance / 2);
    table L = count(beg, mid);
    table R = count(mid, end);

    for (unsigned int i = 0; i < 9; i++) {
        F[i] = L[i] + R[i];
        for(unsigned int j = 0; j < 9; j++) {
            if (j <= i)
                F[i] += L[j] * R[i - j];
            else
                F[i] += L[j] * R[9 + i - j];
        }
    }
    return F;
}

table count(std::string s)
{

    return count(s.begin(), s.end());
}

int main()
{


     cout << count("1234")[0] << endl;

    cout << count("12349")[0] << endl;

    cout << count("9999")[0] << endl;

    cout << count("1292")[0] << endl;cout << count("189")[0] << endl;
    cout << count("10292")[0] << endl;cout << count("0189")[0] << endl;
    system("pause");


   }
于 2012-08-07T18:04:25.317 回答