用3构成可除法电路

Question

TCS中的布尔电路基本上是由和，或者不是门组成的达格，根据已知的“功能完整性”，它们可以计算所有可能的函数。这是阿鲁的基本原理。

挑战:创建一个电路，以确定一个8位数是否可被3除，并以某种方式将结果可视化(如在某种图片中)。

选民的判断标准是基于生成电路的代码是否能很好地概括成任意大小的数字，以及算法创建的可视化是否紧凑/平衡，但仍然是人类可读的(即不允许手工安排可视化)。即可视化只适用于n=8，但理想情况下，代码将适用于所有的'n‘。获胜只是最高的投票。

有点类似的问题：使用NAND逻辑门构建乘法机

Answer 1

图在每个i级保持3个布尔值。它们表示数字的高阶I位等于0、1或2 mod 3。在每个级别上，我们根据前三位和下一输入位计算下三位。

下面是生成图形的python代码。只需改变N，得到不同的位数，或改变K，得到不同的模。通过点运行python程序的输出以生成映像。

N = 8
K = 3
v = ['0']*(K-1) + ['1']
ops = {}

ops['0'] = ['0']
ops['1'] = ['1']
v = ['0']*(K-1) + ['1']
for i in xrange(N):
  ops['bit%d'%i] = ['bit%d'%i]
  ops['not%d'%i] = ['not','bit%d'%i]
  for j in xrange(K):
    ops['a%d_%d'%(i,j)] = ['and','not%d'%i,v[(2*j)%K]]
    ops['b%d_%d'%(i,j)] = ['and','bit%d'%i,v[(2*j+1)%K]]
    ops['o%d_%d'%(i,j)] = ['or','a%d_%d'%(i,j),'b%d_%d'%(i,j)]
  v = ['o%d_%d'%(i,j) for j in xrange(K)]

for i in xrange(4):
  for n,op in ops.items():
    for j,a in enumerate(op[1:]):
      if ops[a][0]=='and' and ops[a][1]=='0': op[j+1]='0'
      if ops[a][0]=='and' and ops[a][2]=='0': op[j+1]='0'
      if ops[a][0]=='and' and ops[a][1]=='1': op[j+1]=ops[a][2]
      if ops[a][0]=='and' and ops[a][2]=='1': op[j+1]=ops[a][1]
      if ops[a][0]=='or' and ops[a][1]=='0': op[j+1]=ops[a][2]
      if ops[a][0]=='or' and ops[a][2]=='0': op[j+1]=ops[a][1]

for i in xrange(4):
  used = set(['o%d_0'%(N-1)])|set(a for n,op in ops.items() for a in op[1:])
  for n,op in ops.items():
    if n not in used: del ops[n]

print 'digraph {'
for n,op in ops.items():
  if op[0]=='and': print '%s [shape=invhouse]' % n
  if op[0]=='or': print '%s [shape=circle]' % n
  if op[0]=='not': print '%s [shape=invtriangle]' % n
  if op[0].startswith('bit'): print '%s [color=red]' % n
  print '%s [label=%s]' % (n,op[0])
  for a in op[1:]: print '%s -> %s' % (a,n)
print '}'

Answer 2

2×24 NOT，2×10+5和，2×2+5 OR，2×2 NOR或

这完全没有规模。一点也不像。也许我会试着改进它。

我测试了这个数字，直到30个，而且效果很好。

这两个大电路正在计算有源输入的数量：

• 右上角以偶数幂(0到4)数位数。
• 左下角以奇数幂(0到4)数位数。

如果这些数字的差异是0或3，则该数字可被3整除。右下角电路基本上将每个有效组合(4,4、4,1、3,3、3,0、2, 2、1, 1、0, 0)映射为or。

中间的小圆圈是一个LED，如果数字可被3除，则为开，否则为off。