Description
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2 28 ) that belong respectively to A, B, C and D .Output
For each input file, your program has to write the number quadruplets whose sum is zero.Sample Input
6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77
1 #include<cstdio>
2 #include<string.h>
3 #include<algorithm>
4 #define MAXN 4400
5 using namespace std;
6 int A[MAXN],B[MAXN],C[MAXN],D[MAXN];
7 int S[MAXN*MAXN];
8 int lower_bound1(int low,int high,int num,int a[])
9 {
10 int mid;
11 while(low<high)
12 {
13 mid=low+(high-low)/2;
14 if(a[mid]>=num) high=mid;
15 else low=mid+1;
16 }
17 return low;
18 }
19 int upper_bound1(int low,int high,int num,int a[])
20 {
21 int mid;
22 while(low<high)
23 {
24 mid=low+(high-low)/2;
25 if(a[mid]<=num) low=mid+1;
26 else
27 high=mid;
28 }
29 return low;
30 }
31 int main()
32 {
33 int n,i;
34 int p;
35 int cout=0;
36 int l,r,j;
37 while(scanf("%d",&n)!=EOF)
38 {
39 cout=0;
40 for(i=0;i<n;i++)
41 scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
42 p=0;
43 for(i=0;i<n;i++)
44 for(j=0;j<n;j++)
45 S[p++]=A[i]+B[j];
46 sort(S,S+p);
47 for(i=0;i<n;i++)
48 for(j=0;j<n;j++)
49 {
50 int t=C[i]+D[j];
51 l=lower_bound1(0,p,-t,S);
52 r=upper_bound1(0,p,-t,S);
53 cout+=(r-l);
54 }
55 printf("%d\n",cout);
56 }
57 return 0;
58 }
-36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45
Sample Output
5
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).en.wikipedia.org/wiki/Expected_value
zh.wikipedia.org/...%80%BC
數學期望
Mathematical Expectation
In probability theory the expected value (or mathematical expectation, or mean) of a discrete random variable is the sum of the probability of each possible outcome of the experiment multiplied by the outcome value (or payoff). Thus, it represents the average amount one "expects" as the outcome of the random trial when identical odds are repeated many times. Note that the value itself may not be expected in the general sense - the "expected value" itself may be unlikely or even impossible.
Examples
The expected value from the roll of an ordinary six-sided die is 3.5, which is not among the possible outcomes:
A common application of expected value is to gambling. For example, an American roulette wheel has 38 places where the ball may land, all equally likely. A winning bet on a single number pays 35-to-1, meaning that the original stake is not lost, and 35 times that amount is won, so you receive 36 times what you've bet. Considering all 38 possible outcomes, the expected value of the profit resulting from a dollar bet on a single number is the sum of what you may lose times the odds of losing and what you w......余下全文>>
Adding 20 Floating Point numbers, here is a program in ANSI Standard C:
double sum, a[20];
int i;
/*
* Some code to initialize array a with legitimate
* floating point values whose sum is less than "maximum double".
*/
sum = 0.0;
for (i = 0; i < 20; i++)
sum += a[i];
printf("%e\n", sum);
sum = 0.0;
i = 20;
while (i--)
sum += a[i];
printf("%e\n", sum);
Question:
Will the 2 "printed" values:
1) always be the same? if so, explain why.
2) always be different? if so, explain why.
3) sometimes be the same and sometimes different? if so, give an example. Please be as complete as possible.
