Алло, мы ищем логических дизайнеров!
Oct. 12th, 2015 07:13 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkОктябрьская задачка на IBM Ponder This прямо как доктор прописал:
Нужно построить логическую цепь, вычисляющую сумму 12 однобитных значений, использовав минимальное число функций "5 бит -> 2 бита".
Пока рекорд, если верить количеству звездочек в списке решивших задачу, 6 функций (upd: раньше казалось, что 5, но там в одном месте в количестве звездочек была опечатка).![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
ftdf столько может, и я тоже.
А кто сколько может? Кто из программистов может думать в терминах логических цепей?
Пусть 12 входных значений обозначены буквами A-L. Выходы будем обозначать, как это сделал kcmamu в своем решении из 7 функций, буквами U, D, Q, O для разряда единиц, двоек, четверок и восьмерок соответственно, и номером функции. UU, DD, QQ, OO - окончательные результаты.
Первым делом сложим (по модулю 4, с разрядом четверок разберемся позже) две группы по 5 входов:
{D1,U1} = A+B+C+D+E
{D2,U2} = F+G+H+I+J
Теперь как можно быстрее получим окончательное значение разряда единиц (тоже складывая по модулю 4):
{D3,UU} = U1+U2+K+L
Осталось сложить D1, D2, D3 и соответствующие разряды четверок ("Q1", "Q2" и "Q3"), которые нужно как-то образовать.
Заметим, что при сложении 5 однобитных значений для получения разряда четверок достаточно посмотреть на значение суммы по модулю 4 (S) и на два любых входных значения: если S = 2 или S = 3, то разряд четверок гарантированно 0; если S = 0, то достаточно посмотреть на любые 2 входных бита, чтобы отличить 0 от 4 - хотя бы один из них должен быть равен единице, чтобы в результате было 4; если S = 1, то тоже достаточно посмотреть на любые 2 входных бита, чтобы отличить 1 от 5 - оба должны быть равны единице, чтобы в результате было 5. Таким образом, нужно всего 4 входа для получения разряда четверок при суммировании 5 бит, т.е. Qx=f(Dx, Ux, Y, Z), где Y и Z - любые 2 входа при вычислении {Dx,Ux}. Подчеркнём, что Qx и Dx не могут быть равны единице одновременно.
Тогда, виртуальное Q1 (функцию, зависящую от D1, U1 и любых двух входов первой суммы, пусть A и B) можно сложить с D1 (которое уже есть на входе) и с D3 (пятым входом) с помощью одной функции. В результате переноса в третий бит не возникнет, т.к. Q1 и D1 не могут быть равны единице одновременно (это от меня при решении в уме ускользнуло).
{Q4, D4} = 2*"Q1" + D1 + D3, где Q1 = f(D1, U1, A, B)
Осталось сложить D2, D4, "Q2" и "Q3". С Q2, D2 и D4 поступаем аналогично:
{Q5, DD} = 2*"Q2" + D2 + D4, где Q2 = f(D2, U2, F, G)
Тем самым образуется окончательное значение разряда двоек, т.к. больше в разряде двоек складывать нечего.
Осталось сложить "Q3", Q4 и Q5. "Q3" получилось в результате суммирования не пяти, а четырех бит, поэтому для того, чтобы Q3 было единице, D3 и UU должны быть равны нулю, а любой произвольный входной бит - единице. Это можно записать и как Q3 = f(D3, UU, U1, 0).
{OO, QQ} = "Q3" + Q4 + Q5, где Q3 = f(D3, UU, U1, 0).
(Описанное решение принадлежит ftdf, мое решение начинается с
{D1,U1} = A+B+(C^D^E)
{D2,U2} = F+G+(H^I^J)
т.е. пользуется разрывом трехбитных сумматоров на две части, как у kcmamu)
Нужно построить логическую цепь, вычисляющую сумму 12 однобитных значений, использовав минимальное число функций "5 бит -> 2 бита".
Пока рекорд, если верить количеству звездочек в списке решивших задачу, 6 функций (upd: раньше казалось, что 5, но там в одном месте в количестве звездочек была опечатка).
ftdf столько может, и я тоже.А кто сколько может? Кто из программистов может думать в терминах логических цепей?
Пусть 12 входных значений обозначены буквами A-L. Выходы будем обозначать, как это сделал kcmamu в своем решении из 7 функций, буквами U, D, Q, O для разряда единиц, двоек, четверок и восьмерок соответственно, и номером функции. UU, DD, QQ, OO - окончательные результаты.
Первым делом сложим (по модулю 4, с разрядом четверок разберемся позже) две группы по 5 входов:
{D1,U1} = A+B+C+D+E
{D2,U2} = F+G+H+I+J
Теперь как можно быстрее получим окончательное значение разряда единиц (тоже складывая по модулю 4):
{D3,UU} = U1+U2+K+L
Осталось сложить D1, D2, D3 и соответствующие разряды четверок ("Q1", "Q2" и "Q3"), которые нужно как-то образовать.
Заметим, что при сложении 5 однобитных значений для получения разряда четверок достаточно посмотреть на значение суммы по модулю 4 (S) и на два любых входных значения: если S = 2 или S = 3, то разряд четверок гарантированно 0; если S = 0, то достаточно посмотреть на любые 2 входных бита, чтобы отличить 0 от 4 - хотя бы один из них должен быть равен единице, чтобы в результате было 4; если S = 1, то тоже достаточно посмотреть на любые 2 входных бита, чтобы отличить 1 от 5 - оба должны быть равны единице, чтобы в результате было 5. Таким образом, нужно всего 4 входа для получения разряда четверок при суммировании 5 бит, т.е. Qx=f(Dx, Ux, Y, Z), где Y и Z - любые 2 входа при вычислении {Dx,Ux}. Подчеркнём, что Qx и Dx не могут быть равны единице одновременно.
Тогда, виртуальное Q1 (функцию, зависящую от D1, U1 и любых двух входов первой суммы, пусть A и B) можно сложить с D1 (которое уже есть на входе) и с D3 (пятым входом) с помощью одной функции. В результате переноса в третий бит не возникнет, т.к. Q1 и D1 не могут быть равны единице одновременно (это от меня при решении в уме ускользнуло).
{Q4, D4} = 2*"Q1" + D1 + D3, где Q1 = f(D1, U1, A, B)
Осталось сложить D2, D4, "Q2" и "Q3". С Q2, D2 и D4 поступаем аналогично:
{Q5, DD} = 2*"Q2" + D2 + D4, где Q2 = f(D2, U2, F, G)
Тем самым образуется окончательное значение разряда двоек, т.к. больше в разряде двоек складывать нечего.
Осталось сложить "Q3", Q4 и Q5. "Q3" получилось в результате суммирования не пяти, а четырех бит, поэтому для того, чтобы Q3 было единице, D3 и UU должны быть равны нулю, а любой произвольный входной бит - единице. Это можно записать и как Q3 = f(D3, UU, U1, 0).
{OO, QQ} = "Q3" + Q4 + Q5, где Q3 = f(D3, UU, U1, 0).
(Описанное решение принадлежит ftdf, мое решение начинается с
{D1,U1} = A+B+(C^D^E)
{D2,U2} = F+G+(H^I^J)
т.е. пользуется разрывом трехбитных сумматоров на две части, как у kcmamu)
