请教一个关于"求和"的问题

fangxu1999

已知有一个数组X[1],X[2],...,X[n],求k个元素乘积的和，具体内容请见附件的图片"计算式"(math.PNG)，用Word做的。

1. 
   
2. double value=0;
   
3. for(int i1=1;i1<n;i1++){
   
4.         for(int i2=i1+1;i2<n;i2++){
   
5.                 for(int i3=i2+1;i3<n;i3++){
   
6.                         ......{
   
7.                                 value+=x[i1]*x[i2]*...*x[ik];
   
8.                         }
   
9.                 }
   
10.         }
    
11. }
    

复制代码

这样设计需要k个for()循环，无法硬编码实现，请各位帮帮忙吧。
在这里先谢过了！

fantix

数学变形。

double value = 1;
double sum = 0;
for (int i = n; i > 0; i--) {
    sum += a[i];
    if (i <= k)
        value *= sum;
}

我验证下。

fantix

见附件

55913153

楼主是什么意思啊???是 1 + 1*2 + 1*2*3 +1*2*3*4 +1*2*3*4*5  ......吗?????
                                            3             9               33              153
是的话,我的程序是这样的,
                double value = 1;
                double sum=0;
                for(int i=0;i<=a.length-1;i++)
                {
                    value *= a[i];
                        sum += value;
                }

精灵的程序是什么意思啊?没看懂

fantix

等式最后一行就是

fangxu1999

谢谢各位的讨论和给出解决方案。
我对于自己没有把问题说清楚表示道歉。
实际上是这样的：

给出N个数据，需要求出任意k个数据的乘积，然后求和，但是不能出现重复的啊。
就象上面给出的An*An是不应该出现的。

例如：
对于数据 1,2,3,4
k=1时 sum=1+2+3+4
k=2时 sum=1*2+1*3+1*4+2*3+2*4+3*4
k=3时 sum=1*2*3+1*2*4+1*3*4+2*3*4
k=4时 sum=1*2*3*4

但是当数据量增大时：1,2,3,4,5,6,7,8...数据项会很多的。

这个原型是概率论里面的事件并的出现概率。
例如有事件A1,A2,A3
事件P(A1 or A2 or A3)=[P(A1)+P(A2)+P(A3)] - [P(A1)P(A2)+P(A1)P(A3)+P(A2)P(A3)] +[P(A1)P(A2)P(A3)]
我为了方便处理，各项都使用了求和。因为当 k%2==1 使用 + ；当 k%2==0 使用 -
如果各位能够了解我的问题之所在，给出一些建议，不胜感激。
直接使用"+/-"交替的式子来求最好了。

fantix

P(A)=P(A)

P(A or B)=P(A)+P(B)-P(A)P(B)

P(A or B or C)=[P(A)+P(B)-P(A)P(B)]+P(C)-[P(A)+P(B)-P(A)P(B)]P(C)
=P(A)+P(B)+P(C)-[P(A)P(B)+P(A)P(C)+P(B)P(C)]+P(A)P(B)P(C)

P(A or B or C or D)=A+B+C+D-(AB+BC+AC+AD+BD+CD)+
(ABC+ABD+BCD+ACD)-ABCD

记S(n,k)为n个数中不重复的k个数的乘积的总和，则有：
P(A[1] or ... or A[N])＝S(N,1) - S(n,2) + S(n,3) - ... +/- S(n,n)

这样对了吧，我试试

fantix

蛮力来做得话，时间复杂度达到阶乘级别，重复计算巨大，考虑用空间换取时间，用动态规划。

ideawu

如果只考虑"给出N个数据，需要求出任意k个数据的乘积，然后求和，但是不能出现重复的啊。"
楼主的问题转化为: 从N个数中, 求得K个数的组合, 将每一个组合内的数求积, 并求所有组的积的和.

算法的主要问题是如何求组合. 我用C++写了一个程序, 能解决楼主的"给出N个数据，需要求出任意k个数据的乘积，然后求和，但是不能出现重复的啊。"问题.

1. 
   
2. #include <stdio.h>
   
3. 
   
4. #define NLEN 4
   
5. #define KLEN 3
   
6. 
   
7. int main(int argc, char *argv[]){
   
8.         long N[NLEN];
   
9.         for(long t=0; t<NLEN; t++){
   
10.                 //在这里初始化N个数.
    
11.                 N[t] = t+1;
    
12.         }
    
13.        
    
14.         long sum = 0;
    
15.         for(int index=0; index<=NLEN-KLEN; index++){
    
16.                 long groupsum = 1;
    
17.                 for(int i=index; i<index+KLEN; i++){
    
18.                         groupsum *= N[i];
    
19.                 }
    
20.                 sum += groupsum;
    
21.                
    
22.                 for(int j=index+1; j<index+KLEN; j++){
    
23.                         long temp = groupsum / N[j];
    
24.                         for(int k=index+KLEN; k<NLEN; k++){
    
25.                                 sum += temp * N[k];
    
26.                         }
    
27.                 }
    
28.         }
    
29.         printf("\n%d\n", sum);
    
30. }
    

复制代码

[ 本帖最后由 ideawu 于 2006-10-18 10:21 编辑 ]

fantix

嘿嘿，还是这样吧。以两个为例：
P(A or B) = 1 - P(not (A and B)) = 1 - (1-P(A))(1-P(B))
是不是这回事啊 ><  ><
P(A1 or A2 or ... An) = 1 - (1 - P(A1))(1 - P(A2))...(1 - P(An))