# DigitalCircuit

> 本关是一个由不同逻辑门（可能包含与非门、异或门等）构成的数字电路，包含 4 个输入端和 8 个输出端，初始输出为 `00000000`。
>
> 你需要通过合理输入，使得此电路能够输出 `11111111`。

本关的情况有点出乎意料，因为很多人过关不是依靠真的把题解出来，而是「一不小心碰出全 `1` 然后就通关了」，可见题目的复杂度还有待提升。我的预期好歹也是大家要测测电路，找找规律才行。

## 解析

这道题对于没学过数电的人来说并不友好，因为它不是一个简单的组合逻辑电路。在组合逻辑电路中，由确定的输入只会得出确定的输出。但在本题，你只要连续使用同样的输入来观测输出，就会发现输出结果是变化的。所以说，**这个电路很有可能是时序逻辑电路。**

具体的找规律过程就不提了，我直接说结果。

设输入为 $a\_3a\_2a\_1a\_0$，上一轮的输出为 $b\_7b\_6b\_5b\_4b\_3b\_2b\_1$，本轮输出为 $c\_7c\_6c\_5c\_4c\_3c\_2c\_1$，那么：

$c\_7c\_5c\_3c\_1$ 就等于你的输入，也就是说

$$$
c\_5=a\_2\\
c\_3=a\_1\\
c\_1=a\_0$$

$c\_6$ 只有在「本次输入与上次输入（上次输入的结果间接记录在了上次输出当中）完全相反」时，才会得到 `1`；否则得到 `0`。

$c\_4c\_2$ 组成二位计数器，也就是说

$$c\_4=b\_4\oplus b\_2\\
c\_2=\neg b\_2$$

$c\_0$ 则等于所有输入 $a\_k$、输出 $b\_k$ 的异或和。

以下 C++ 代码可以实现由输入和上次输出推算本次输出。

```c++
std::array<bool,preset::OutputNum> operate::signal(std::array<bool,preset::InputNum> &input,std::array<bool,preset::OutputNum> &output){
	std::array<bool,preset::OutputNum> result;
	//result[7,5,3,1]记录了本次的输入
	result[7]=input[3];
	result[5]=input[2];
	result[3]=input[1];
	result[1]=input[0];
	//result[6]只有在「本次输入与上次输入完全相反」时，才会得到true
	result[6]=input[3]^output[7]&&input[2]^output[5]&&input[1]^output[3]&&input[0]^output[1];
	//result[4,2]组成二位计数器
	result[4]=output[4]^output[2];
	result[2]=!output[2];
	//result[0]等于所有输入、输出的异或和
	result[0]=false;
	for(int i=0;i<preset::InputNum;i++)
		result[0]^=input[i];
	for(int i=0;i<preset::OutputNum;i++)
		result[0]^=output[i];
	return result;
}
```

回到我们的问题。我们的初始状态是 `00000000`，而我们希望到达全 `11111111`，这其实就是一个在有向图上寻找路径的问题，那么无论做广度优先搜索还是求最短路都是可行的。

### 人工推导

当然，这题不编程也完全可以做，我们试着寻找一下思路：

就像走迷宫那样，有的时候从终点开始要比从起点开始更加容易。

要想达到 `11111111`，最后一步的输入必定要是 `1111`，因为输出当中就有四位数等于输入。

而我们又要保证 $c\_6$ 等于 `1`，那么前一次的输入必须是 `0000` 才行。

同时，$c\_4c\_2$ 构成二位计数器，也就是说，在前一回合，它们的输出将是 $10$。

接下来的流程也可以照猫画虎地做，不过分岔会越来越多，很难逐个分析；因此我建议能编程的玩家还是试试编程求解一下。

### 编程求解

我们可以运用图论的知识建立一个有向图 $G(V,E)$，图上的点表示「输出的结果」，图中共有 $2^8=256$ 个点；边表示「经过一次输入，某个状态可以转移成另一个状态」，图中共有 $2^12=4096$ 条边。

我们还可以推断出这个图的一些特征，例如：因为有两位计数器每回合都会发生变化，所以任何一个状态在经历一次输入之后不可能返回它自身，因而 $G$ 中没有自环。（当然这是题外话了）

接下来就可以在图上搜索或者求最短路。我用的是 Floyd 算法。

```c++
#include<array>
#include<limits>
#include"operate.hpp"
#include"preset.hpp"
void operate::floyd(
	std::array<std::array<int,1<<preset::OutputNum>,1<<preset::OutputNum> &dist,
	std::array<std::array<int,1<<preset::OutputNum>,1<<preset::OutputNum> &prev
){
	for(int o=0;o<1<<preset::OutputNum;o++)
		for(int r=0;r<1<<preset::OutputNum;r++){
			dist[o][r]=std::numeric_limits<int>::max()/2;
			prev[o][r]=-1;
		}
	for(int o=0;o<1<<preset::OutputNum;o++){
		dist[o][o]=0;
		prev[o][o]=o;
		std::array<bool,preset::OutputNum> output;
		for(int d=0;d<preset::OutputNum;d++)
			output[d]=o&1<<d;
		for(int i=0;i<1<<preset::InputNum;i++){
			std::array<bool,preset::InputNum> input;
			for(int d=0;d<preset::InputNum;d++)
				input[d]=i&1<<d;
			std::array<bool,preset::OutputNum> result{operate::signal(input,output)};
			int r{0};
			for(int d=0;d<preset::OutputNum;d++)
				if(result[d])
					r+=1<<d;
			dist[o][r]=1;
			prev[o][r]=o;
		}
	}
	for(int k=0;k<1<<preset::OutputNum;k++)
		for(int i=0;i<1<<preset::OutputNum;i++)
			for(int j=0;j<1<<preset::OutputNum;j++)
				if(dist[i][j]>dist[i][k]+dist[k][j]){
					dist[i][j]=dist[i][k]+dist[k][j];
					prev[i][j]=prev[k][j];
				}
}
```

Floyd 算法应该是这里面最麻烦的了，不过我有不得不用的理由——那就是分析整个图的性质。

不过这些内容就是出题时需要考虑的了，如果我有空的话，之后会对此做进一步说明。
$$$
