t**********s
发帖数: 930 | 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*****n
发帖数: 227 | 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**********s
发帖数: 930 | 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*****n
发帖数: 227 | 4 解出了abcde那f(n)就是你要的求和公式啊。
【在 t**********s 的大作中提到】
: 解出又如何呢？没懂。
| t**********s
发帖数: 930 | 5 你怎么知道最高次幂一定是4呢？
【在 S*****n 的大作中提到】
: 解出了abcde那f(n)就是你要的求和公式啊。
| S*****n
发帖数: 227 | 6 那你不妨试试最高次幂是10的情形，解解看就知道是不是了。
不过就是5元一次方程组和11元一次方程组的区别了。。
【在 t**********s 的大作中提到】
: 你怎么知道最高次幂一定是4呢？
| t****t
发帖数: 6806 | 7 当然不是4,而是3
随便数数就知道了啊, 小学数学
(1+2^2+3^2+...+n^2)-(1+2+3+...+n)
【在 t**********s 的大作中提到】
: 你怎么知道最高次幂一定是4呢？
| t**********s
发帖数: 930 | 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****t
发帖数: 6806 | 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****t
发帖数: 6806 | 10 至于随便数数的问题,
原式<(1+2+3+...+n)*n<(n+n+n+...+n)*n=n^3
【在 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**********s
发帖数: 930 | 11 n*(n-1)*(n+1)/3
kukutf (五脚蟹★酷酷豆腐)同学给的答案，是斑竹吧？：）
【在 t****t 的大作中提到】
: 至于随便数数的问题,
: 原式<(1+2+3+...+n)*n<(n+n+n+...+n)*n=n^3
| S*****n
发帖数: 227 | 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 的大作中提到】
: 我估计是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**********s
发帖数: 930 | 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*****n
发帖数: 227 | 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
: ...
|
|
