一个数据结构中的数学求和问题求教 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

一个数据结构中的数学求和问题求教 (转载)

一个数据结构中的数学求和问题求教 (转载)# Programming - 葵花宝典

t*s2007-01-11 08:01

1 楼

【以下文字转载自 Mathematics 讨论区】
发信人: tennisalways (tennisforever), 信区: Mathematics
标题: 一个数据结构中的数学求和问题求教
发信站: BBS 未名空间站 (Thu Jan 11 14:54:18 2007)
原题是这样的：
procedure mystery (n:integer);
var
i,j,k:integer;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
for k:=1 to j do
{some statement requiring O(1) time}
end
最后如何求：
(2+3+4+5+...+n)+(3+4+5+...+n)+(4+5+...+n)+...+((n-1)+n)+n
这个求和可以归纳成什么等式那？
谢谢

S*n2007-01-11 08:01

2 楼

找个n的多项式，例如f(n) = a*n^4 + b*n^3 + c*n^2 + d*n + e
自己带入n=1,2,3,4,5的值，解方程组。

【在 t**********s 的大作中提到】

: 【以下文字转载自 Mathematics 讨论区】
: 发信人: tennisalways (tennisforever), 信区: Mathematics
: 标题: 一个数据结构中的数学求和问题求教
: 发信站: BBS 未名空间站 (Thu Jan 11 14:54:18 2007)
: 原题是这样的：
: procedure mystery (n:integer);
: var
: i,j,k:integer;
: begin
: for i:=1 to n-1 do

t*s2007-01-11 08:01

3 楼

解出又如何呢？没懂。

【在 S*****n 的大作中提到】

: 找个n的多项式，例如f(n) = a*n^4 + b*n^3 + c*n^2 + d*n + e
: 自己带入n=1,2,3,4,5的值，解方程组。

S*n2007-01-11 08:01

4 楼

解出了abcde那f(n)就是你要的求和公式啊。

【在 t**********s 的大作中提到】

: 解出又如何呢？没懂。

t*s2007-01-11 08:01

5 楼

你怎么知道最高次幂一定是4呢？

【在 S*****n 的大作中提到】

: 解出了abcde那f(n)就是你要的求和公式啊。

S*n2007-01-11 08:01

6 楼

那你不妨试试最高次幂是10的情形，解解看就知道是不是了。
不过就是5元一次方程组和11元一次方程组的区别了。。

【在 t**********s 的大作中提到】

: 你怎么知道最高次幂一定是4呢？

t*t2007-01-11 08:01

7 楼

当然不是4,而是3
随便数数就知道了啊, 小学数学
(1+2^2+3^2+...+n^2)-(1+2+3+...+n)

【在 t**********s 的大作中提到】

: 你怎么知道最高次幂一定是4呢？

t*s2007-01-11 08:01

8 楼

我估计是3，但我不知道怎么随便数数就能知道。
还是的设 n=2,3,4,5
然后求 f(n) = a*n^3 + b*n^2 + c*n + d
n=2 时多项式值为2
3 8
4 20
5 40
所得方程：
8a+4b+2c+d=2
27a+9b+3c+d=8
64a+16b+4c+d=20
125a+25b+5c+d=40
这个方程可够复杂的，怎么解，有什么更好的办法求系数？

【在 t****t 的大作中提到】

: 当然不是4,而是3
: 随便数数就知道了啊, 小学数学
: (1+2^2+3^2+...+n^2)-(1+2+3+...+n)

t*t2007-01-11 08:01

9 楼

四元一次方程组不会解?

【在 t**********s 的大作中提到】

: 我估计是3，但我不知道怎么随便数数就能知道。
: 还是的设 n=2,3,4,5
: 然后求 f(n) = a*n^3 + b*n^2 + c*n + d
: n=2 时多项式值为2
: 3 8
: 4 20
: 5 40
: 所得方程：
: 8a+4b+2c+d=2
: 27a+9b+3c+d=8

t*t2007-01-11 08:01

10 楼

至于随便数数的问题,
原式
【在 t**********s 的大作中提到】

t*s2007-01-11 08:01

11 楼

n*(n-1)*(n+1)/3
kukutf (五脚蟹★酷酷豆腐)同学给的答案，是斑竹吧？：）

【在 t****t 的大作中提到】

: 至于随便数数的问题,
: 原式

S*n2007-01-11 08:01

12 楼

好一点的方法是把f(n)设的方便一点。
let f(n) = a*n(n-1)(n-2) + b*n(n-1) + c*n + d
求出abcd后再展开那些乘项，把式子写成常见形式。
这样求出来a=1/3,b=1,c=d=0,展开后就是(n+1)n(n-1)/3
本质一样。
另外，用n=0,1,2,3来解; 用2，3，4，5是自找麻烦。

【在 t**********s 的大作中提到】

t*s2007-01-11 08:01

13 楼

但原程序n最小只能是2吧？
因为 for i:=1 to n-1 do
...

【在 S*****n 的大作中提到】

: 好一点的方法是把f(n)设的方便一点。
: let f(n) = a*n(n-1)(n-2) + b*n(n-1) + c*n + d
: 求出abcd后再展开那些乘项，把式子写成常见形式。
: 这样求出来a=1/3,b=1,c=d=0,展开后就是(n+1)n(n-1)/3
: 本质一样。
: 另外，用n=0,1,2,3来解; 用2，3，4，5是自找麻烦。

S*n2007-01-11 08:01

14 楼

那也容易。let f(n) = a*(n-2)(n-3)(n-4)+b*(n-2)(n-3)+c*(n-2)+d
来求。最后展开的时候麻烦一些而已。

最后结果反正都一样。

【在 t**********s 的大作中提到】

: 但原程序n最小只能是2吧？
: 因为 for i:=1 to n-1 do
: ...