PUZZLEUP 2015

newkid · 发表于 2015-10-10 21:05

solomon_007 发表于 2015-10-10 17:00
这样考虑就比较复杂了...

你这只是模拟，公式也不难吗？
昨天给你转了个马上有钱。

solomon_007 · 发表于 2015-10-10 21:16

本帖最后由 solomon_007 于 2015-10-10 21:50 编辑

newkid 发表于 2015-10-10 21:03
我和OO一样，分子是100*C(99,4)+99*C(98,4)+...+5*C(4,4)
分母是那些组合数之和。为了展开求和就得知道那 ...

你写成这样的公式我才看明白了
SQL> declare
  2 a number :=0;
  3 b number :=0;
  4 m number :=0;
  5  begin
  6 for i in 5..100 loop
  7
  8    select ((i-1)*(i-2)*(i-3)*(i-4))/(1*2*3*4) into m from dual;
  9    a := a + i*m;
10    b := b + m;
11 end loop;
12
13 dbms_output.put_line(a);
14 dbms_output.put_line(b);
15 dbms_output.put_line(a/b);
16  end;
17  /
6336699600
75287520
84.16666666666666666666666666666666666667
PL/SQL procedure successfully completed

solomon_007 · 发表于 2015-10-10 21:20

newkid 发表于 2015-10-10 21:05
你这只是模拟，公式也不难吗？
昨天给你转了个马上有钱。

是的, 这只是模拟, 但这个样本已经很高了,所以应该可以估计出那个值.

章, 多谢!

newkid · 发表于 2015-10-10 22:58

solomon_007 发表于 2015-10-10 21:20
是的, 这只是模拟, 但这个样本已经很高了,所以应该可以估计出那个值.

章, 多谢!

你把通项公式推导一下就给你发章。就是说只要输入N不需要循环马上能得到答案。

solomon_007 · 发表于 2015-10-11 02:50

newkid 发表于 2015-10-10 22:58
你把通项公式推导一下就给你发章。就是说只要输入N不需要循环马上能得到答案。

100*C(99,4)+99*C(98,4)+...+5*C(4,4)

f(n) = a(n)/b(n)
a(n) = n*(n-1)*(n-2)*(n-3)*(n-4)/24 +...+ 5*4*3*2*1/24 = 1/24 * (1*2*3*4*5 + ... + (n-4)*(n-3)*(n-2)(n-1)*n )
b(n) = (n-1)*(n-2)*(n-3)*(n-4)/24 +...+ 4*3*2*1/24 = 1/24 * (1*2*3*4 + ... + (n-4)*(n-3)*(n-2)(n-1) )

1 + 2 + ... + n = n(n+1)/2
1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6
1^3 + 2^3 + ... + n^3 = n^2(n+1)^2/4
1^4 + 2^4 + ... + n^4 = n(n+1)(2n+1)(3n^2+3n-1)/30
1^5 + 2^5 + ... + n^5 = n^3(n+1)^3/6 - n^2(n+1)^2/12       (1^3+2^3+...+n^3+3(1^5+2^5+...+n^5)=n^3(n+1)^3/2)

(n-4)*(n-3)*(n-2)(n-1)*n = (n^2-n)(n-2)(n-3)(n-4)=(n^3-3n^2+2n)(n-3)(n-4)=(n^4-6n^3+11n^2 - 6n)(n-4)
                                                                     =n^5-6n^4+11n^3 - 6n^2 -4n^4 + 24n^3 - 44n^2 + 24n
                                                                     =n^5-10n^4+35n^3 -50n^2 +24n
(n-4)*(n-3)*(n-2)(n-1) = n^4 -10n^3 +35n^2 -50n +24

            1*2*3*4*5 + ... + (n-4)*(n-3)*(n-2)(n-1)*n
f(n)=a(n)/b(n)= -------------------------------------------
            1*2*3*4 + ... + (n-4)*(n-3)*(n-2)(n-1)

西格玛(n-4)*(n-3)*(n-2)(n-1)*n
=(n^3(n+1)^3/6 - n^2(n+1)^2/12)-10(n(n+1)(2n+1)(3n^2+3n-1)/30) +35(n^2(n+1)^2/4) -50(n(n+1)(2n+1)/6) +24(n(n+1)/2)
= n*(n+1)[ (n^2(n+1)^2/6 - n(n+1)/12) - (2n+1)(3n^2+3n-1)/3 + 35(n(n+1)/4) - 25(2n+1)/3 + 12 ]
= n*(n+1)[ (n^4+2n^3+n^2)/6 -(n^2+n)/12 - ( 6n^3 +6n^2 -2n + 3n^2 + 3n -1)/3 + 35(n^2+n)/4  - 25(2n+1)/3 + 12 ]
= n*(n+1)[ (n^4+2n^3+n^2)/6 -(n^2+n)/12 - ( 6n^3 +9n^2 + n -1)/3 + 35(n^2+n)/4  - 25(2n+1)/3 + 12 ]
= n*(n+1)[ n^4/6 + n^3/3 + n^2/6 - n^2/12 - n/12 -2n^3 - 3n^2 -n/3 + 1/3 + 35n^2/4 + 35n/4 - 50n/3 - 25/3 + 12 ]
= n*(n+1)[ n^4/6 - 5n^3/3 + 35n^2/6 - 25n/3 + 4 ]
= 1/6 * n*(n+1)(n^4-10n^3+35n^2-50n+24)

西格玛(n-4)*(n-3)*(n-2)(n-1)
= n(n+1)(2n+1)(3n^2+3n-1)/30 -10(n^2(n+1)^2/4) +35(n(n+1)(2n+1)/6) -50(n(n+1)/2) + 24n
= n(n+1) [ (2n+1)(3n^2+3n-1)/30 - 5n(n+1)/2 + 35(2n+1)/6 - 25 ]  + 24
= n(n+1) [ ( 6n^3 +6n^2 -2n + 3n^2 + 3n -1)/30 - 5n(n+1)/2 + 35(2n+1)/6 - 25 ]  + 24n
= n(n+1) [ (6n^3 +9n^2 + n -1)/30 - 5(n^2 +n)/2 + 35(2n+1)/6 - 25 ]  + 24n
= n(n+1) [ n^3/5 + 3n^2/10 + n/30 - 1/30 - 5n^2/2 - 5n/2 + 35n/3 + 35/6 - 25 ] + 24n
= n(n+1) [ n^3/5 - 22n^2/10 + 92n/10  - 192/10 ] + 24n
= 1/10 * n*[(n+1)(2n^3-22n^2+92n-192) + 240]
= 1/10 * n* ( 2n^4 -22n^3 +92n^2 -192n + 2n^3-22n^2+92n-192 + 240 )
= 1/10 * n* ( 2n^4 -20n^3 +70n^2 -100n + 48 )
= 1/5 *n(n^4 -10n^3 +35n^2 - 50n +24)

所以通项公式为:
f(n) = a(n)/b(n) = ((n+1)/6) /(n/5) = 5(n+1)/6 (n>=5)


n=100
select 5*(100+1)/6 from dual
----------------
84.1666666666667