Мажоритарная функция - это логическая функция, которая принимает три логических входа и возвращает наиболее распространенные. Например, если maj(x,y,z)
является мажоритарной функцией и T
обозначает true и F
обозначает false, то:
maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F
Этот вопрос касается написания булевых функций как составов функций большинства. Примером 5-арной композиции мажоритарных функций является (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5))
. Эта функция возвращает следующие выходные данные для этих примеров входных векторов:
(T,T,F,F,F) => maj(T,T,maj(F,F,F)) = maj(T,T,F) = T
(T,F,T,T,F) => maj(T,F,maj(T,T,F)) = maj(T,F,T) = T
(T,F,T,F,F) => maj(T,F,maj(T,F,F)) = maj(T,F,F) = F
(F,F,F,T,T) => maj(F,F,maj(F,T,T)) = maj(F,F,T) = F
задача
Напишите программу, которая вводит положительное целое число n и список логических векторов длины n и выводит дерево мажоритарных вентилей, которое возвращает true для всех заданных векторов, если это возможно. Функция может возвращать true или false для векторов, не входящих в список ограничений.
Список векторов может быть введен в любом формате, который вам нравится. Если вы предпочитаете, вместо ввода вектора, вы можете ввести список истинных позиций в векторе. Так, например,
[TTF,TFT,FTT]
или[[T,T,F],[T,F,T],[F,T,T]]
или[[1,2],[1,3],[2,3]]
(список истинных позиций) все в порядке.Выходными данными может быть любой допустимый формат дерева. Например,
maj(maj(x1,x2,x3),x4,x5)
работает. Возможно, вы захотите использовать отдельные числа в качестве резервных для переменных, как в[[1,2,3],4,5]
.123m45m
Например, обратная полировка тоже подойдет.Если функция не работает, ваша программа должна выдать ошибку или вывести значение Falsey.
Если работает несколько функций, ваша программа может вернуть любую из них. Функция не нуждается в упрощении. Например,
maj(x1,x1,x2)
илиx1
эквивалентны.
счет
Это код гольф: выигрывает самое короткое решение в байтах.
Тестовые случаи:
Обратите внимание, что существует много возможных выходных данных для каждого из этих случаев, поэтому вы должны написать скрипт проверки, который преобразует ваши выходные данные в функцию и проверяет, что ваша функция возвращает true для каждого из указанных входных векторов.
Input: 3, [TFF]
Output: 1 or [1,1,2] or [1,[1,2,2],[1,1,3]] or other equivalent
Input: 3, [TFF,FTF]
Output: Falsey or error (it's not possible)
Input: 3, [TTF,TFT]
Output: [1,2,3] or 1 or other equivalent
Input: 3, [TTF,TFT,FTT]
Output: [1,2,3] or [1,3,2] or other equivalent
Input: 4, [TTFF,TFTF,FFTT]
Output: Falsey or error
Input: 4, [TTTF,TTFT,TFTT,FTTT]
Output: [1, 2, 3] or [2,3,4], or many other options
Input: 5, [TTTFF,FTTFT,TFFFT]
Output: [1,[1,[1,2,5],[2,4,5]],3] or many other options
Input: 6, [TTTFFF,FTFTTF,TFFTFT]
Output: [1, 2, 4] or [1, [1, 2, 4], [2, 3, 4]] or others
Input: 5, [TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT]
Output: [[1, [1, 3, 5], 4], [1, 2, [2, 4, 5]], [2, 3, [3, 4, 5]]] or others
Input: 7, [TTTTFFF,TTTFTFF,TTTFFTF,TTTFFFT,TTFTTFF,TTFTFTF,TTFTFFT,TTFFTTF,TTFFTFT,TTFFFTT,TFTTTFF,TFTTFTF,TFTTFFT,TFTFTTF,TFTFTFT,TFTFFTT,TFFTTTF,TFFTTFT,TFFTFTT,TFFFTTT,FTTTTFF,FTTTFTF,FTTTFFT,FTTFTTF,FTTFTFT,FTTFFTT,FTFTTTF,FTFTTFT,FTFTFTT,FTFFTTT,FFTTTTF,FFTTTFT,FFTTFTT,FFTFTTT,FFFTTTT]
Output: [[[1, [1, [1, 4, 7], 6], 5], [1, [1, 3, [3, 6, 7]], [3, 5, [5, 6, 7]]], [3, 4, [4, [4, 5, 7], 6]]], [[1, [1, [1, 4, 7], 6], 5], [1, 2, [2, [2, 5, 7], 6]], [2, [2, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]], [[2, [2, [2, 4, 7], 6], 5], [2, 3, [3, [3, 5, 7], 6]], [3, [3, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]]]
Ответы:
JavaScript (ES6), 260 байт
Принимает ввод как массив массивов логических значений. Возвращает дерево 1-индексированных мажорных ворот или выдает ошибку рекурсии (1), если решения не существует.
Основная функция f () рекурсивно пытается найти решение, вызывая решатель F () и увеличивая максимальный уровень вложенности m на каждой итерации.
(1) после долгого времени и принимая бесконечную память
демонстрация
Показать фрагмент кода
пример
Ниже приведена таблица проверки решения, найденного для последнего контрольного примера демонстрации.
источник
Mathematica, 121 байт
Анонимная функция, которая принимает второй аргумент в виде списка истинных позиций в векторе логических значений.
Отформатирован немного лучше:
Объяснение:
Почему это правда? Ну, функция большинства удовлетворяет двум свойствам:
It turns out that complementary monotonic functions are exactly the class of functions that can be built out of majority gates.
Now, we show that forf a complementary monotonic function, our identity holds:
f(x1,…,xn)=maj(f(x1,x1,x3,x4,…,xn),f(x1,x2,x2,x4,…,xn),f(x3,x2,x3,x4,…,xn))
Let's setf1(x1,x2,x3,…,xn)=f(x1,x1,x3,x4,…,xn) , f2(x1,…,xn)=f(x1,x2,x2,x4,…,xn) and f3(x1,…,xn)=f(x3,x2,x3,x4,…,xn) . To show that f=maj(f1,f2,f3) , we need to show that for any input, at least two of f1 , f2 , and f3 are equal to f . We divide up into cases based on the values of x1 , x2 and x3 . If x1=x2=x3 then f1=f2=f3=f .
Suppose not all ofx1 , x2 , and x3 are the same. By permuting the variables of f , we can assume that x1=x2 and x3 is different and because f is complementary, it suffices to deal with the case x1=x2=False and x3=True . In this case, (x1,x1,x3)=(False,False,True)=(x1,x2,x3) , (x1,x2,x2)=(False,False,False)≤(x1,x2,x3) and (x3,x2,x3)=(True,False,True)≥(x1,x2,x3) . By monotonicity we deduce that f2≤f1=f≤f3 . If f=False then f2≤False implies f2=False=f and if f=True then f3≥True implies f3=True . Thus, at least two of f1 , f2 , and f3 are equal to f in all cases so f=maj(f1,f2,f3) .
источник