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]]]]]
Odpowiedzi:
JavaScript (ES6), 260 bajtów
Pobiera dane wejściowe jako tablicę tablic booleanów. Zwraca drzewo bramek 1-indeksowanej większości lub zgłasza błąd rekurencji (1), jeśli nie ma rozwiązania.
Główna funkcja f () rekurencyjnie próbuje znaleźć rozwiązanie, wywołując solver F () i zwiększając maksymalny poziom zagnieżdżenia m przy każdej iteracji.
(1) po długim czasie i przy założeniu nieskończonej pamięci
Próbny
Pokaż fragment kodu
Przykład
Poniżej znajduje się tabela sprawdzania poprawności rozwiązania znalezionego dla ostatniego przypadku testowego wersji demonstracyjnej.
źródło
Mathematica, 121 bajtów
Anonimowa funkcja, która bierze swój drugi argument jako listę list prawdziwych pozycji w wektorze wartości logicznych.
Sformatowane nieco ładniej:
W przeciwnym razie zastąpf1=f(x1,x1,x2,x3,…,xn−1) , f2=f(x1,x2,x2,x3,…,xn−1) oraz f3=f(x1,x2,x1,x3,…,xn−1)) , rozwiąż rekurencyjnie każdy z nich, a następnie ustawf=maj(f1(x1,x3,x4,…,xn),f2(x1,x2,x4,…,xn),f2(x2,x3,x4,…,xn)) .
Wyjaśnienie:
Jest to algorytm rekurencyjny, który ogranicza problem znalezienia rozwiązania problemu zmiennejn do znalezienia trzech rozwiązań problemów zmiennej n−1 . Kluczem obserwacja sprawia, że tej pracy jest to, że dla f jedna z funkcji szukamy mamy:
f(x1,…,xn)=maj(f(x1,x1,x3,x4,…,xn),f(x1,x2,x2,…),f(x3,x2,x3,…))
W pierwszej pozycji wymieniliśmyx2 ox1 , w drugim położeniux3 zx2 , w trzeciej pozycjix1 zx3 .
Gdy poznasz tę tożsamość, algorytm jest jasny: gdy istnieją dwie lub mniej zmiennych, problem jest trywialny. W przeciwnym razie rekurencyjnie rozwiąż trzy problemy reprezentowaniaf(x1,x1,x3,x4,…,xn) , f(x1,x2,x2,x4,…,xn) i f(x3,x2,x3,x4,…,xn)) i weź większość z nich.
Dlaczego to prawda? Cóż, funkcja większości spełnia dwie właściwości:
Jest „komplementarny”. To znaczy, jeśli!x jest negacja x , a maj(!x,!y,!z)=!maj(x,y,z) . W konsekwencji każda funkcja, którą możemy zbudować z funkcji większości, jest komplementarna.
Jest monotoniczny. To znaczy,maj(x,y,False)≤maj(x,y,True) . Ogólnie rzecz biorąc, jeśli powiemy, że False≤True i powiedzmy (x1,…,xn)≤(y1,…,yn) jeślixi≤yi dla wszystkichi , to mówię, że funkcjaf jest monotoniczna jeśli(x1,…xn)≤(y1,…,yn) implikujef(x1,…xn)≤f(y1,…,yn) . Skład funkcji monotonicznych jest monotoniczny, więc każda funkcja, którą możemy zbudować z funkcji większości, jest monotoniczna.
Okazuje się, że uzupełniające się funkcje monotoniczne są dokładnie klasą funkcji, które można zbudować z bram większości.
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) .
źródło