[算法] 最优算法

hniu

看谁算法和实现最好

计算： １×２×３×４＋２×３×４×５＋３×４×５×６＋…＋１００００００００１×１００００００００２×１００００００００３×１００００００００４

稍后公布答案

wingforce

原式 = sigma[n = 1 -> m] n (n + 1) (n + 2) (n + 3)
       = sigma[n = 1 -> m] n^4 + 6n^3 + 11n^2 + 6n
       = sigma[n = 1 -> m] n^4 + 6 sigma[n = 1 -> m] +
                11 sigma[n = 1 -> m]n^2 + 6 sigma[n = 1 -> m] n

然后分别对每一项使用自然数4次方和，3次方和，2次方和，自然数和的公式
常数时间得到答案

hniu

原式 = sigma[n = 1 -> m] n (n + 1) (n + 2) (n + 3)
       = sigma[n = 1 -> m] n^4 + 6n^3 + 11n^2 +  ...
wingforce 发表于 2011-09-19 07:42

    不错！！

   但是还可以更简单。

   思考一下

1*2*3*4=1/5(1*2*3*4*5 - 0*1*2*3*4)
2*3*4*5=1/5(2*3*4*5*6 - 1*2*3*4*5)
.....


可以推导出更简单的形式

davelv

楼主骗人来着，这明明是高中数学题。。。

hniu

楼主骗人来着，这明明是高中数学题。。。
davelv 发表于 2011-09-19 09:00

    胡扯，这个明明是2010年中山市的中考试题，是初中的范畴。

毛xx总理

是初中的吧。

bruceteen

1*2*3*4=1/5(1*2*3*4*5 - 0*1*2*3*4)
2*3*4*5=1/5(2*3*4*5*6 - 1*2*3*4*5)
hniu 发表于 2011-09-19 08:57

    呜呜呜，俺初中没毕业

x5miao

回复 3# hniu


    对1楼的公式计算结果再分解因式会得到一摸一样的结果，而且方法更通用。

wingforce

这类问题，其本质是二项定理的应用，那种所谓的观察法并不是系统的方法，而是想寻找捷径，不是所有情况都可以找到这样的解。高等数学之所以区别于初等数学的原因之一就是它的目的是旨在寻找一类问题的通用解，而不是解决其中的一个特例。