Tổng hiệu các tập con trong C++

Trong bài toán này, ta được cho tập hợp S gồm n số. Nhiệm vụ: tạo chương trình tìm tổng hiệu các tập con, tức hiệu giữa phần tử cuối và phần tử đầu của tập con.

Công thức:

sumSubsetDifference = Σ [last(s) - first(s)] với s là các tập con của S.

Ví dụ minh họa

Đầu vào –

S = {1, 2, 9}, n = 3

Đầu ra –

24

Giải thích – Tất cả tập con:

{1}: last-first = 0
{2}: 0
{9}: 0
{1, 2}: 1
{1, 9}: 8
{2, 9}: 7
{1, 2, 9}: 8
Tổng = 1 + 8 + 7 + 8 = 24

Cách đơn giản: sinh tất cả tập con, tính hiệu, cộng dồn. Không tối ưu.

Cách hiệu quả: tính tổng phần tử đầu và cuối riêng biệt dựa trên số lượng tập con bắt đầu/kết thúc bởi mỗi phần tử.

Với tập S = {s1, s2, ..., sn}:

Số tập con bắt đầu bằng si = 2^(n-i).

SumFirst = s1·2^(n-1) + s2·2^(n-2) + ... + sn·2^0

Tương tự, số tập con kết thúc bằng si = 2^(i-1).

SumLast = s1·2^0 + s2·2^1 + ... + sn·2^(n-1)

Kết quả = SumLast - SumFirst.

Ví dụ

Chương trình minh họa:

#include<iostream>
#include<math.h>
using namespace std;

int CalcSumFirst(int S[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum = sum + (S[i] * pow(2, n-i-1));
    return sum;
}

int CalcSumLast(int S[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum = sum + (S[i] * pow(2, i));
    return sum;
}

int main() {
    int S[] = {1, 4, 9, 6};
    int n = 4;
    int sumSetDiff = CalcSumLast(S, n) - CalcSumFirst(S, n);
    printf("The sum of subset differences is %d", sumSetDiff);
    return 0;
}

Đầu ra

The sum of subset differences is 45