資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中計算使 A 和 B 的異或結果等於 C 所需翻轉的最小位數
給定三個長度為 N 的二進位制序列 A、B 和 C。每個序列代表一個二進位制數。我們必須找到在 A 和 B 中需要翻轉的位數，以便 A 和 B 的異或結果為 C。A XOR B 等於 C。
首先，讓我們學習一下異或運算的真值表：
| X | Y | X XOR Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
從上表可以看出，當 X 和 Y 值相同時，X XOR Y 的結果為 0，否則結果為 1。這將有助於找到需要在 A 和 B 中翻轉的位以達到 C。情況如下：
- 如果 A[i]==B[i] 且 C[i]==0，則無需翻轉；
- 如果 A[i]==B[i] 且 C[i]==1，則翻轉 A[i] 或 B[i]，並將翻轉計數增加 1；
- 如果 A[i]!=B[i] 且 C[i]==0，則翻轉 A[i] 或 B[i]，並將翻轉計數增加 1；
- 如果 A[i]!=B[i] 且 C[i]==1，則無需翻轉。
輸入
A[]= { 0,0,0,0 } B[]= { 1,0,1,0 } C= {1,1,1,1}輸出
Required flips : 2
解釋
A[0] xor B[0] 0 xor 1 = 1 C[0]=1 no flip A[1] xor B[1] 0 xor 0 = 0 C[0]=1 flip count=1 A[2] xor B[2] 0 xor 1 = 1 C[0]=1 no flip A[3] xor B[3] 0 xor 0 = 0 C[0]=1flip count=2
輸入
A[]= { 0,0,1,1 } B[]= { 0,0,1,1 } C= {0,0,1,1}輸出
Required flips : 2
解釋
A[0] xor B[0] 0 xor 0 = 0 C[0]=0 no flip A[1] xor B[1] 0 xor 0 = 0 C[0]=0 no flip A[2] xor B[2] 1 xor 1 = 0 C[0]=1 flip count=1 A[3] xor B[3] 1 xor 1 = 0 C[0]=1 flip count=2
下面程式中使用的演算法如下：
陣列 a[]、b[] 和 c[] 用於儲存二進位制數。
函式 flipCount(int A[], int B[], int C[], int n) 將陣列 a、b、c 及其長度 n 作為輸入，並返回在 A[] 或 B[] 的位中獲得 C[] 作為 A 異或 B 所需的翻轉次數。
變數 count 表示翻轉計數，並初始化為 0。
使用 for 迴圈遍歷從 i = 0 到 i 的單元格中的每一位。
對於每一位 A[i] 和 B[i]，如果它們相等且 C[i] 為 1，則增加計數。
對於每一位 A[i] 和 B[i]，如果它們不相等且 C[i] 為 0，則增加計數。
返回計數作為所需結果。
示例
#include<bits/stdc++.h>
using namespace std;
int flipCount(int A[], int B[], int C[], int N){
int count = 0;
for (int i=0; i < N; ++i){
// If both A[i] and B[i] are equal then XOR results 0, if C[i] is 1 flip
if (A[i] == B[i] && C[i] == 1)
++count;
// If Both A and B are unequal then XOR results 1 , if C[i] is 0 flip
else if (A[i] != B[i] && C[i] == 0)
++count;
}
return count;
}
int main(){
//N represent total count of Bits
int N = 5;
int a[] ={1,0,0,0,0};
int b[] ={0,0,0,1,0};
int c[] ={1,0,1,1,1};
cout <<"Minimum bits to flip such that XOR of A and B equal to C :"<<flipCount(a, b, c,N);
return 0;
}輸出
Minimum bits to flip such that XOR of A and B equal to C :2
更新於：2020年7月28日
309 次瀏覽
廣告