与或异或
蓝桥杯逐日一题 2024-12-26 与或异或 DFS
题目描述
小蓝有一张门电路的逻辑图，如下图所示： 图中每个三角形代表着一种门电路，大概是与门、或门、异或门中的任何一种，它担当上一层中的两个圆形中的数据作为输入，产生一个输出值输出到 下一级 (如图中箭头所示)。图中圆形表示的是暂存的输出结果，取值只大概是 0 或 1，为了便于表示我们用 a r r [ i ] [ j ] arr[j] arr[j] 表示第 i ( 0 ≤ i ≤ 4 ) i(0\leq i\leq 4) i(0≤i≤4) 行第 j ( 0 ≤ j ≤ i ) j(0\leq j\leq i) j(0≤j≤i) 个圆形的值。此中 a r r [ 0 ] = ( I n [ 0 ] , I n [ 1 ] , I n [ 2 ] , I n [ 3 ] , I n [ 4 ] ) arr[0]=(In[0],In[1],In[2],In[3],In[4]) arr[0]=(In[0],In[1],In[2],In[3],In[4]) 表示的是输入数据，对于某个 a r r [ i ] [ j ] ( i ≥ 0 ) arr[j](i\geq 0) arr[j](i≥0)，计算方式为 a r r [ i ] [ j ] = a r r [ i − 1 ] [ j ] o p a r r [ i − 1 ] [ j + 1 ] arr[j]=arr[i−1][j] \ op \ arr[i−1][j+1] arr[j]=arr[i−1][j] op arr[i−1][j+1]，此中 o p op op 表示的是将 a r r [ i − 1 ] [ j ] arr[i−1][j] arr[i−1][j]、 a r r [ i − 1 ] [ j + 1 ] arr[i−1][j+1] arr[i−1][j+1] 作为输入，将 a r r [ i ] [ j ] arr[j] arr[j] 作为输出的那个门电路，与门、或门、异或门分别对应于按位与 &、按位或 ( ∣ ) (|) (∣) 、按位异或(^)运算符。 如今已知输入为 I n [ 0 ] = 1 , I n [ 1 ] = 0 , I n [ 2 ] = 1 , I n [ 3 ] = 0 , I n [ 4 ] = 1 In[0]=1,In[1]=0,In[2]=1,In[3]=0,In[4]=1 In[0]=1,In[1]=0,In[2]=1,In[3]=0,In[4]=1，小蓝想要使得最终的输出 O u t Out Out 的值为 1，叨教一共有多少种差别的门电路组合方式？此中上图中表现的就是一种合法的方式。
解题思绪
那这道题就是通过遍历来找出所能够满意条件的方法，首先详细怎么遍历，就是先通过每一遍历运算符的操作，然而每遍历一次操作，就要判定是否要换行，是否要结束递归，更新到下一个操作之后就有要进行操作符的遍历。
Accepted
- #include <iostream>
- using namespace std;
- int res = 0;
- int arr[6][10] = {{1,0,1,0,1}};
- void dfs(int r,int c,int k) {
- if(k == 1) {
- arr[r][c] = arr[r-1][c] | arr[r-1][c+1];
- }
- if(k == 2) {
- arr[r][c] = arr[r-1][c] ^ arr[r-1][c+1];
- }
- if(k == 3) {
- arr[r][c] = arr[r-1][c] & arr[r-1][c+1];
- }
- // 判断结束条件
- if(r == 4 && c == 0) {
- if(arr[r][c] == 1) {
- res ++;
- }
- return ;
- }
- // 当前行结束
- if(r + c == 4) {
- r++;
- c = 0;
- } else c++;
- for(int i = 1;i <= 3;i++) {
- dfs(r,c,i);
- }
- }
- int main()
- {
- int op[3] = {1,2,3};
-
- for(int k = 1;k <= 3;k++){
- dfs(1,0,k);
- }
- cout<<res<<endl;
- return 0;
- }
|
