Funkcja większości jest funkcją logiczną, która pobiera trzy dane logiczne i zwraca najczęściej. Na przykład jeśli maj(x,y,z)
jest funkcją większości i T
oznacza prawdę, a F
fałsz, to:
maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F
To pytanie dotyczy pisania funkcji boolowskich jako kompozycji funkcji większościowych. Przykład 5-arylowej kompozycji funkcji większościowych to (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5))
. Ta funkcja zwraca następujące dane wyjściowe dla tych przykładowych wektorów wejściowych:
(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
Zadanie
Napisz program, który wprowadza dodatnią liczbę całkowitą n oraz listę długości n wektorów boolean i wypisuje drzewo bramek większości, które zwraca wartość true dla wszystkich podanych wektorów, jeśli to możliwe. Funkcja może zwracać wartość true lub false w wektorach, które nie znajdują się na liście ograniczeń.
Lista wektorów może być wprowadzana w dowolnym formacie. Jeśli wolisz, zamiast wprowadzania wektora, możesz wprowadzić listę prawdziwych pozycji w wektorze. Na przykład,
[TTF,TFT,FTT]
lub[[T,T,F],[T,F,T],[F,T,T]]
lub[[1,2],[1,3],[2,3]]
(lista prawdziwych pozycji) są w porządku.Dane wyjściowe mogą być dowolnym poprawnym formatem drzewa. Na przykład,
maj(maj(x1,x2,x3),x4,x5)
działa. Prawdopodobnie będziesz chciał użyć pojedynczych liczb jako stand-ins dla zmiennych, jak w[[1,2,3],4,5]
. Na przykład polerowanie wsteczne123m45m
jest również w porządku.Jeśli żadna funkcja nie działa, twój program powinien wygenerować błąd lub wygenerować wartość falsey.
Jeśli działa wiele funkcji, Twój program może zwrócić dowolną z nich. Funkcja nie musi być uproszczona. Na przykład
maj(x1,x1,x2)
lubx1
są równoważne.
Punktacja
To jest kod golfowy: wygrywa najkrótsze rozwiązanie w bajtach.
Przypadki testowe:
Zauważ, że istnieje wiele możliwych danych wyjściowych dla każdego z tych przypadków, dlatego powinieneś napisać skrypt sprawdzający, który konwertuje dane wyjściowe na funkcję i sprawdź, czy funkcja zwraca wartość true dla każdego z określonych wektorów wejściowych.
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]]]]]