数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学用 C++ 统计具有特定 XOR 值的子集个数
给定一个包含正整数的数组 arr[] 和一个值 match。目标是找到 arr[] 的子集，这些子集的元素 XOR 值等于 match。
例如
输入
arr[] = {4, 2, 8, 10} match=12输出
Count of number of subsets having a particular XOR value are: 2
解释
Subsets of arr with XOR of elements as 0 are − [ 4,8 ], [4,2,10]
输入
arr[] = {3,5,2,7} match=5输出
Count of number of subsets having a particular XOR value are− 2
解释
ubsets of arr with XOR of elements as 0 are− [ 5 ], [2,7]
以下程序中使用的算法如下 −
在这个方法中，我们将使用动态规划的解决方案。数组 arr_2[][] 将在索引 i,j 处包含值，使得 arr_2[ i ][ j ] 的值为 arr[ 0 到 i−1 ] 的子集的元素的 XOR。将初始值 arr_2[0][0] 设置为 1，因为空集的 XOR 为 1。设置 arr_2[i][j] = arr_2[i−1][j] + arr_2[i−1][j ^ arr[i−1]]，如果子集 arr[0 到 i−2] 的 XOR 为 j，则子集 arr[0 到 i−1] 的 XOR 也为 j。同样，如果子集 arr[0 到 i−2] 的 XOR 为 j^arr[i]，则子集 arr[0 到 i−1] 的 XOR 也为 j，因为 j ^ arr[i−1] ^ arr[i−1]。结果将在 arr_2[ size ][ match ] 中找到。
取一个整数数组 arr[]。
取变量 match 为整数。
函数 subset_XOR(int arr[], int size, int match) 接收一个输入数组及其长度，并返回具有特定 XOR 值的子集个数。
最初取 highest = arr[0]。现在使用 for 循环遍历整个 arr[] 并找到最大值 highest。
计算 temp = (1 << (int)(log2(highest) + 1) ) − 1 作为最大可能的 XOR 值。
取数组 arr_2[size+1][temp+1] 来存储 XOR 值。
使用 for 循环用 0 初始化整个 arr_2。
设置 arr_2[0][0] = 1。
使用 for 循环从 i=0 到 i<=size，以及 j=0 到 j<=size，设置 temp_2 = arr_2[i−1][j ^ arr[i−1]] 并设置 arr_2[i][j] = arr_2[i−1][j] + temp_2。
在两个 for 循环结束时，我们将有 arr_2[size][match] 作为具有特定 XOR 值的子集个数。
返回 arr_2[size][match] 作为结果。
示例
#include<bits/stdc++.h>
using namespace std;
int subset_XOR(int arr[], int size, int match){
int highest = arr[0];
for (int i = 1; i < size; i++){
if(arr[i] > highest){
highest = arr[i];
}
}
int temp = (1 << (int)(log2(highest) + 1) ) − 1;
if( match > temp){
return 0;
}
int arr_2[size+1][temp+1];
for (int i = 0; i<= size; i++){
for (int j = 0; j<= temp; j++){
arr_2[i][j] = 0;
}
}
arr_2[0][0] = 1;
for (int i=1; i<=size; i++){
for (int j=0; j<=temp; j++){
int temp_2 = arr_2[i−1][j ^ arr[i−1]];
arr_2[i][j] = arr_2[i−1][j] + temp_2;
}
}
return arr_2[size][match];
}
int main(){
int arr[] = {4, 2, 8, 10, 3, 4, 4};
int match = 2;
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of number of subsets having a particular XOR value are: "<<subset_XOR(arr, size, match);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of number of subsets having a particular XOR value are − 8
334 次浏览
