Sume

November 16, 2013Probleme, Subiecte Partial

Fie

$A = {A_1, A_2, \ldots A_n}$

o colecţie de

$n$

numere naturale, cu

$1 \leq n \leq 500$

şi

$1 \leq A_i \leq 1000$

,

$i=1,n$

. În colecţie pot există elemente multiple cu aceeaşi valoare. Notăm cu

$Sets(n)$

mulţimea tuturor mulţimilor formate cu întregii

$1, 2, \ldots, n$

, inclusiv mulţimea vida,

$\emptyset$

. Considerăm

$Sum(A,S)=\sum_{i \in S}{A_i}$

suma elementelor din colecţia

$A$

indexate de numerele din mulţimea

$S\in Sets(n)$

(prin convenţie

$Sum(A,\emptyset)=0$

). Fie mulţimea

$Sums(A) = \{Sum(A,S) | S \in Sets(n)\}$

a sumelor ce pot fi calculate cu elementele colecţiei

$A$

în raport cu numerele din fiecare submulţime din

$Sets(n)$

.

$Sums(A)$

este mulţimea tuturor sumelor distincte ce se pot formă cu elementele colecţiei

$A$

. Să se scrie un program C care primeşte la intrare setul de date

$n$

$A_1$

$A_2$

$\ldots$

$A_n$

şi calculează cardinalul mulţimii

$Sums(A)$

, afisiand rezultatul pe o linie nouă.

Exemplu:
3 1 1 2
5

Pentru exemplul dat

$n=3$

,

$A_1=1$

,

$A_2=1$

,

$A_3=2$

. Vom avea: }

$\begin{array}{|c|c|c|c|c|c|c|c|c|}S\in Sets(n) & \emptyset & \{1\} & \{2\} & \{3\}&\{1,2\} & \{1,3\} & \{2,3\} & \{1,2,3\} \\Sum(A,S) & 0 & A_1 & A_2 & A_3 & A_1+A_2 & A_1+A_3 & A_2+A_3 & A_1+A_2+A_3 \\& 0 & 1 & 1 & 2 & 2 & 3 & 3 & 4 \\\end{array}$

deci,

$Sums(A) = \{0, 1, 2, 3, 4\}$

şi

$card(Sums(A)) = 5$

, ceea ce înseamnă că sunt exact 5 sume distincte care se pot formă cu numerele

$1, 1, 2$

.

Indicaţie: se poate folosi următoarea schemă:

Tags: Algebră, Mulțimi, Operații pe biți