генерировать таблицу истинности с учетом ввода?

Question

Есть умный алгоритм, который принимает ряд вероятностей и формирует соответствующую таблицу истинности внутри многомерного массива или контейнера

Ex:

n = 3 
N : [0 0 0 
    0 0 1 
    0 1 0 
    ... 
    1 1 1] 

я могу сделать это с для петель и Иф, но я знаю, что мой путь будет медленным и трудоемким. Итак, я спрашиваю, есть ли расширенная функция, которую я могу использовать, чтобы сделать это максимально эффективно?

Answer 1

Если мы позволили заполнить таблицу со всеми нулями, чтобы начать, это должно быть возможно затем выполнить точно 2^n - 1 заполняет, чтобы установить 1 бит мы желаем. Это может быть не быстрее, чем писать ручную петлю, хотя она полностью не обработана.

EDIT: Линия std::vector<std::vector<int> > output(n, std::vector<int>(1 << n)); объявляет вектор векторов. Внешним вектором является длина n, а внутренняя - 2^n (количество результатов истины для n входов), но я вычисляю мощность с использованием сдвига влево, поэтому компилятор может вставлять константу, а не вызов, например, pow. В случае, когда n=3 заканчивается вектором 3х8. Я организую его таким образом (а не обычный 8x3 с строкой в ​​качестве первого индекса), потому что мы собираемся использовать шаблон на основе столбцов в выходных данных.Использование конструкторов vector таким образом также гарантирует, что каждый элемент вектора векторов будет инициализирован равным 0. Таким образом, нам нужно только беспокоиться о том, чтобы установить значения, которые мы хотим использовать, и оставить остальных в покое.

Второй набор вложенных циклов for используется только для распечатки полученных данных, когда это сделано, ничего особенного нет.

Первый набор для циклов реализует реальный алгоритм. Здесь мы используем шаблон на основе столбцов в выходных данных. Для данной таблицы истинности самый левый столбец будет иметь две части: первая половина - это все 0, а вторая половина - все 1. Поскольку мы предварительно заполняем нули, применяется однократное заполнение половины высоты столбца, начиная с половины вниз все, что нам нужно. Второй столбец будет содержать строки 1/4th 0, 1/4th 1, 1/4th 0, 1/4th 1. Таким образом, два заливки будут применять все 1s, которые нам нужны. Повторяем это, пока не дойдем до самой правой колонки, в этом случае каждая другая строка равна 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; 
} 

Answer 2

Вы хотите записать числа от 0 до 2^N - 1 в двоичной системе цифр. В этом нет ничего умного. Вам просто нужно заполнить каждую ячейку двухмерного массива. Вы не можете сделать это быстрее, чем это.

Вы можете сделать это без повторения непосредственно по номерам. Обратите внимание, что самый правый столбец повторяется 0 1, затем следующий столбец повторяется 0 0 1 1, затем следующий 0 0 0 0 1 1 1 1 и так далее. Каждый столбец повторяет 2^columnIndex (начиная с 0) нулей, а затем единиц.

Answer 3

Вы можете разбить свою проблему на две части, заметив, что каждая из строк в матрице представляет собой двоичное число n бит, где n - количество вероятностей [sic].

так что вам нужно:

• перебрать все п разрядные числа
• преобразовать каждое число в строку вашего 2d контейнера

редактировать:

если вы только беспокоится о времени выполнения, а затем для постоянного n вы всегда можете прекомпопутировать таблицу, но она думает, что вы застряли в сложности O (2^n), когда она вычисляется

Answer 4

Чтобы уточнить ответ для JK ... Если у вас есть п булевых значений («вероятность»?), То вам нужно

• создать массив таблицы правды, что это п на 2^п
• петли i от 0 до (2^n-1)
• внутри этого цикла, цикл j от 0 до n-1
• внутри цикла THAT, set truthTable [i] [j] = jth бит i (например, (Я >> J) & 1)

Answer 5

Карта Карно или Куайна-Маккласки

http://en.wikipedia.org/wiki/Karnaugh_map http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm

Это должно возглавить вас в правильном направлении для минимизации результирующей таблицы истинности.