给定输入生成真值表？

发布于 2024-09-14 21:38:39 字数 218 浏览 5 评论 0 原文

是否有一种智能算法可以获取多个概率并在多维数组或容器内生成相应的真值表

例如：

我可以使用 for 循环和 If 来实现，但我知道我的方法会很慢且耗时。因此，我想问是否有一种高级功能可以让我尽可能高效地做到这一点？

原文

Is there a smart algorithm that takes a number of probabilities and generates the corresponding truth table inside a multi-dimensional array or container

Ex :

I can do it with for loops and Ifs , but I know my way will be slow and time consuming . So , I am asking If there is an advanced feature that I can use to do that as efficient as possible ?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

迷路的信 2024-09-21 21:38:39

如果我们允许在开始时用全零填充表，那么应该可以精确执行 2^n - 1 填充来设置我们想要的 1 位。这可能不会比编写手动循环更快，但它完全没有配置文件。

编辑：
std::vector 行表示> output(n, std::vector(1 << n)); 声明一个向量的向量。外部向量的长度为 n，内部向量的长度为 2^n（n 个输入的真值结果数），但我通过使用左移进行幂计算，以便编译器可以插入一个常量，而不是而不是调用pow。在 n=3 的情况下，我们最终得到一个 3x8 向量。我以这种方式组织它（而不是通常的 8x3，以行作为第一个索引），因为我们将在输出数据中利用基于列的模式。以这种方式使用 vector 构造函数还可以确保向量向量的每个元素都初始化为 0。因此，我们只需担心将所需的值设置为 1，而无需理会其余的值。

第二组嵌套的 for 循环仅用于在完成后打印结果数据，没有什么特别的。

第一组 for 循环实现了真正的算法。我们在这里利用输出数据中基于列的模式。对于给定的真值表，最左边的列将有两部分：前半部分全为 0，后半部分全为 1。由于我们预先填充了零，因此将应用从中间向下开始的一半列高的单次填充我们需要的所有 1。第二列将包含行 1/4th 0、1/4th 1、1/4th 0、1/4th 1。因此，两次填充将应用我们需要的所有 1。我们重复此操作，直到到达最右边的列，在这种情况下，每隔一行都是 0 或 1。

我们开始说“我需要一次填充一半的行”（unsigned num_to_fill = 1U << (n - 1);)。然后我们循环每一列。第一列从要填充的位置开始，并用 1 填充那么多行。然后我们增加行并将填充大小减少一半（现在我们一次填充 1/4 行，但然后我们跳过空白行并第二次填充）下一列。

例如：

#include <iostream>
#include <vector>

int main()
{
    const unsigned n = 3;
    std::vector<std::vector<int> > output(n, std::vector<int>(1 << n));

    unsigned num_to_fill = 1U << (n - 1);
    for(unsigned col = 0; col < n; ++col, num_to_fill >>= 1U)
    {
        for(unsigned row = num_to_fill; row < (1U << n); row += (num_to_fill * 2))
        {
            std::fill_n(&output[col][row], num_to_fill, 1);
        }
    }

    // These loops just print out the results, nothing more.
    for(unsigned x = 0; x < (1 << n); ++x)
    {
        for(unsigned y = 0; y < n; ++y)
        {
            std::cout << output[y][x] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

If we're allowed to fill the table with all zeroes to start, it should be possible to then perform exactly 2^n - 1 fills to set the 1 bits we desire. This may not be faster than writing a manual loop though, it's totally unprofiled.

EDIT:
The line std::vector<std::vector<int> > output(n, std::vector<int>(1 << n)); declares a vector of vectors. The outer vector is length n, and the inner one is 2^n (the number of truth results for n inputs) but I do the power calculation by using left shift so the compiler can insert a constant rather than a call to, say, pow. In the case where n=3 we wind up with a 3x8 vector. I organize it in this way (rather than the customary 8x3 with row as the first index) because we're going to take advantage of a column-based pattern in the output data. Using the vector constructors in this way also ensures that each element of the vector of vectors is initialized to 0. Thus we only have to worry about setting the values we want to 1 and leave the rest alone.

The second set of nested for loops is just used to print out the resulting data when it's done, nothing special there.

The first set of for loops implements the real algorithm. We're taking advantage of a column-based pattern in the output data here. For a given truth table, the left-most column will have two pieces: The first half is all 0 and the second half is all 1. Since we pre-filled zeroes, a single fill of half the column height starting halfway down will apply all the 1s we need. The second column will have rows 1/4th 0, 1/4th 1, 1/4th 0, 1/4th 1. Thus two fills will apply all the 1s we need. We repeat this until we get to the rightmost column in which case every other row is 0 or 1.

We start out saying "I need to fill half the rows at once" (unsigned num_to_fill = 1U << (n - 1);). Then we loop over each column. The first column starts at the position to fill, and fills that many rows with 1. Then we increment the row and reduce the fill size by half (now we're filling 1/4th of the rows at once, but we then skip blank rows and fill a second time) for the next column.

For example:

#include <iostream>
#include <vector>

int main()
{
    const unsigned n = 3;
    std::vector<std::vector<int> > output(n, std::vector<int>(1 << n));

    unsigned num_to_fill = 1U << (n - 1);
    for(unsigned col = 0; col < n; ++col, num_to_fill >>= 1U)
    {
        for(unsigned row = num_to_fill; row < (1U << n); row += (num_to_fill * 2))
        {
            std::fill_n(&output[col][row], num_to_fill, 1);
        }
    }

    // These loops just print out the results, nothing more.
    for(unsigned x = 0; x < (1 << n); ++x)
    {
        for(unsigned y = 0; y < n; ++y)
        {
            std::cout << output[y][x] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

回复收藏 0 原文