資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++ 中所有可能的子集乘積之和
在這個問題中，我們給定一個包含 N 個數字的陣列 arr[]。我們的任務是建立一個程式，找到所有可能的子集乘積之和。
在這裡，我們將找到所有子集，然後找到每個子集的所有元素的乘積。然後將所有值加起來計算總和。
讓我們舉個例子來理解這個問題，
輸入
arr[] = {4, 5, 6}輸出
209
解釋 -
All subsets of arr[] are: {4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
Sum of product
= (4) + (5) + (6) + (4*5) + (5*6) + (4*6) + (4*5*6)
= (4) + (5) + (6) + (20) + (30) + (24) + (120)
= 209解決這個問題的一個簡單方法是找到集合的所有子集，並計算每個子集的元素乘積。然後將所有乘積加起來，遍歷完所有子集後返回最終的總和。
示例
程式說明我們解決方案的工作原理，
#include<iostream>
#include<math.h>
using namespace std;
int findSumProductSubset(int *arr, int set_length) {
unsigned int size = pow(2, set_length);
int sum = 0;
int product;
for(int counter = 1; counter < size; counter++) {
product = 1;
for(int j = 0; j < size; j++) {
if(counter & (1<<j))
product *= arr[j];
}
sum += product;
}
return sum;
}
int main() {
int arr[] = {4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The sum of the product of all subsets is "<<findSumProductSubset(arr, n);
}輸出
The sum of the product of all subsets is 209
上述方法生成了所有子集，因此具有指數時間複雜度。因此，它不是最有效的方法。
更有效的方法是找到解決方案的模式。
現在，讓我們看看一組三個數字 x、y、z。
sum = x + y + z + xy + yz + xz + xyz
sum = x + xz + y + yz + xy + xyz + z + 1 - 1
sum = x(1+z) + y(1+z) + xy(1+z) + 1(z+1) - 1
sum = ( x + y + xy + 1 )( 1 + z ) - 1
sum = ( x(1 + y) + 1(1+y) )(1+z) - 1
sum = (1 + x) * (1 + y) * (1 + z) - 1
這可以用以下方式概括，
對於 n 個元素的集合，
sum = (1+ e1) * (1 + e2) * … * (1 + en) - 1
示例
程式說明我們解決方案的工作原理，
#include <iostream>
using namespace std;
int productOfSubsetSums(int arr[], int n) {
int sum = 1;
for (int i = 0; i < n; ++i )
sum *= (arr[i] + 1);
sum --;
return sum;
}
int main() {
int arr[] = {5, 6, 8 , 9};
int n = sizeof(arr)/sizeof arr[0];
cout<<"Sum of product of all possible subsets is "<<productOfSubsetSums(arr, n);
return 0;
}輸出
Sum of product of all possible subsets is 3779
更新於: 2020年8月14日
582 次瀏覽
廣告