Некоторое время назад Стас Кельвич подкинул мне занятную головоломку про логические вентили . Задача формулируется крайне просто, а вот найти решение среднему по больнице человеку не так-то легко. Должен предупредить, что это одна из тех задач, которая не будет давать вам спать, пока вы ее не решите. Также должен предупредить, что в этой заметке содержится полное решение.
Задача формулируется следующим образом:
Есть три логических входа: A, B, C. Нужно построить цепь на логических вентилях, выдающую на выходе !A, !B и !C. При этом в цепи можно использовать не более двух вентилей НЕ, а также неограниченное количество И и ИЛИ. Другие вентили (XOR, NAND, …) использовать нельзя.
Если вы не сильно интересуетесь железом, то задачу можно переформулировать и так:
Есть процедура, принимающая три булевых аргумента — a, b и c. Нужно посчитать !a, !b и !c, используя не более двух логических отрицаний. Вы не можете использовать условные операторы, циклы и прочие конструкции выбранного вами языка программирования. Вы только можете объявлять переменные булева типа, а также использовать присваивание, неограниченное количество операторов логического И и ИЛИ, а также не более двух операторов НЕ.
Ниже приведено решение задачи на SystemVerilog :
module puzzle (
input logic CLK100MHZ ,
input logic [ 3 : 0 ] sw ,
output logic [ 3 : 0 ] led
) ;
always_ff @ ( posedge CLK100MHZ )
begin
logic a , b , c ,
two_or_more_high , two_or_more_low ,
odd_high , even_high ,
zero_high , one_high , two_high ,
not_a , not_b , not_c ;
a <= sw [ 0 ] ;
b <= sw [ 1 ] ;
c <= sw [ 2 ] ;
two_or_more_high <= ( a && b ) || ( b && c ) || ( a && c ) ;
two_or_more_low <= ! two_or_more_high ;
odd_high <= ( a && b && c ) || ( ( a || b || c ) && two_or_more_low ) ;
even_high <= ! odd_high ;
zero_high <= two_or_more_low && even_high ;
one_high <= two_or_more_low && odd_high ;
two_high <= two_or_more_high && even_high ;
not_a <= zero_high || ( one_high && ( b || c ) ) || ( two_high && b && c ) ;
not_b <= zero_high || ( one_high && ( a || c ) ) || ( two_high && a && c ) ;
not_c <= zero_high || ( one_high && ( a || b ) ) || ( two_high && a && b ) ;
led [ 0 ] <= not_a ;
led [ 1 ] <= not_b ;
led [ 2 ] <= not_c ;
end
endmodule
Легко проверить, что в нем используются только операторы && и || , а также ровно два логических отрицания. С тем же успехом можно предложить решение на C или любом другом языке. Просто я увидел возможность попрактиковаться в SystemVerilog и воспользовался ей.
Если вам нравятся головоломки, вас также могут заинтересовать следующие заметки из этого блога:
- Интересные задачки с собеседований (и типа конкурс) ;
- Решение задачи про игру «кошки-мышки» на OCaml ;
- Решение задачи «кто на ком женат» с помощью Haskell ;
- Мое решение задачи об олимпийских кольцах на Erlang ;
- Решение задачи о кодировании цифр на Haskell и Perl ;
- Задача о роботе-пылесосе без датчиков и решение на Haskell ;
- Алгоритм поиска A* на Haskell и превращение мухи в слона ;
А какие задачки / головоломки знаете вы?