-1

这篇文章很好地解释了子序列的概念：生成子序列

但我不明白那个问题的答案，因为我是初学者。

我想知道的是我是否可以在不使用函数的情况下使我的 C 程序更高效，同时仍然保持简单易懂？

#include <stdio.h>
#define NUM 123456

int main(void) {

    int i,num=NUM,x,y,mask,digits=0,max=1;

    while ( num != 0 ) {  //calculate digits
        num /= 10;
        digits++;
    }

    for ( i = 1; i <= digits; i++ ) {  //calculate max number of subsequences
        max *= 2;     
    }
    max=max-2;

    printf("Subsequences are:\n");
    for ( i = 1; i <= max ; i++ ) {
        mask = i;     //digit selector
        x = 1;        //multiplier
        num = NUM;
        y=0;          //subsequence value

        while ( num != 0 ) {
            if ( mask % 2 == 1 ) {
                y += num % 10 * x;
                x *= 10; 
            }
            num /= 10;
            mask /= 2;
        }
        printf("%d \n" , y);
    } 

    return 0;
}

请注意，当我们将 NUM 定义为诸如 5111 或 100 之类的数字时，某些子序列会出现两次。有什么简单的方法可以解决这个问题吗？谢谢！

4

2 回答 2

0

某些子序列与某些数字出现多次的原因的根源是因为这些数字具有相同数字的重复。

可以通过将每个子序列保存在数组中并检查该数组以查看特定子序列是否已经在数组中来消除这种重复。如果已经在数组中，则不要打印。否则，将子序列添加到数组内容并打印

于 2015-11-12T00:19:06.173 回答
0

这个问题可以分为两个任务：（1）找到一个数字数组的所有子序列，（2）将整数打包和解包成数字。

让我们考虑数组的子序列{a, b, c}。您可以通过从左到右遍历数组并遵循两条路径来生成它们：一种是在子序列中包含当前元素，另一种是不包含。

这导致了一种递归方法，我们可以将其表示为一棵树：

                  {}
               /      \
         {}               {a}
       /    \           /     \
    {}        {b}     {a}      {ab}
   /  \      /   \   /   \    /    \
  {}  {c}  {b} {bc} {a} {ac} {ab} {abc}

当我们向左分支时，我们跳过当前元素，当我们向右分支时，我们包含该元素。元素本身就是树的深度：在第一层我们处理 element a，在 nextb和 last c。

底行包含所有子序列。这包括您不想要的空序列和完整序列。但现在让我们将它们包括在内。（底行中的数组通常称为幂集，这是一个很好的网络搜索术语。）

我提到了递归，它需要递归函数，而函数已经出来了。

所以我们需要用另一种方式来解决这个问题。让我们把树翻过来。破折号表示该元素已被跳过。右边的符号使用另一种符号：0表示元素被跳过，1表示元素被包含：

- - -        000
- - c        001
- b -        010
- b c        011
a - -        100
a - c        101
a b -        110
a b c        111

我希望右边的代码看起来很熟悉，因为这就是你从二进制数000到的方式。111这是枚举我们的元素的好方法。现在我们需要一种方法来判断每个数字中设置了哪些位。

当数字为奇数时，设置最右边的位。我们可以通过重复将数字除以 2 来找出其他位，这在二进制中是向右移位，丢弃最右边的位。

现在如何从原始号码中提取数字？该数字是十进制数；它以 10 为底。我们可以使用与查找二进制数中的位相同的方法，因为位 0 和 1 是二进制数字。

从数字开始。最后一位数字是除以 10 后取余数的结果。然后将该数字除以 10 直到为零。此代码产生从右到左的数字。查找位的代码也是如此，这意味着我们可以在单个循环中查找是否设置了位以及要打印的数字，总是取最右边的位，如果设置了，则打印原始数字的最右边的数字。

空子序列和完整子序列是枚举中的第一项和最后一项。如果您不想要它们，请跳过它们。

如果数字有重复数字，这就留下了重复子序列的问题。除了 user3629249 建议创建子序列并稍后检查是否已经打印之外，我没有看到解决此问题的简单方法。

一个简单的方法是保留一个子序列数组。该数组有max条目。填充该数组后，对其进行排序然后打印它，但跳过与前一个条目相等的条目。

这是一个使用数字数组的示例实现，因此不必每次都分解原始数字。它使用qsort来自的排序函数<stdlib.h>，这需要一个排序函数：

#include <stdlib.h>
#include <stdio.h>

#define NUM 412131

typedef unsigned int uint;

int uintcmp(const void *pa, const void *pb)
{
    const uint *a = pa;
    const uint *b = pb;

    return (*a > *b) - (*a < *b);
}

int main(void)
{
    uint digit[20];             // array of digits
    size_t ndigit = 0;          // length of array
    uint num = NUM;
    uint max = 1;
    size_t i;

    while (num) {
        digit[ndigit++] = num % 10;
        num /= 10;
        max *= 2;
    }

    uint res[max];              // array of subsequences

    for (i = 0; i < max; i++) {
        uint mask = i;          // mask for bit detection
        uint j = ndigit;        // index into digit array
        uint s = 0;

        while (j--) {
            if (mask % 2) s = s*10 + digit[j];
            mask /= 2;
        }

        res[i] = s;
    }

    qsort(res, max, sizeof(*res), uintcmp);

    for (i = 1; i < max - 1; i++) {
        if (res[i] != res[i - 1]) printf("%u\n", res[i]);
    }

    return 0;
}
于 2015-11-12T07:18:47.963 回答