向大家请教一个计算循环次数的问题

langue

====

请教楼上，这个等式是用数学归纳法证明的吗？

====

tyc611

原帖由 langue 于 2007-1-18 19:43 发表
====

请教楼上，这个等式是用数学归纳法证明的吗？

====

为什么要用数学归纳法证呢？
本来就可以直接计算嘛

迭代计算，呵呵
(1)对于两层循环：

1. 
   
2. for (int i = 1; i <= n; ++i)
   
3.    for (int j = 1; j <= i; ++j)
   
4.           A; // do something here
   

复制代码

有：A计算次数有为P(2， n) = (1+2+...+n) = n(1+n)/2

(2)对于k层循环(k>=2)，假设其计算次数为：P(k，m) ，则
对于k+1层循环，有：

[ 本帖最后由 tyc611 于 2007-1-18 20:02 编辑 ]

Edengundam

原帖由 tyc611 于 2007-1-18 19:57 发表

为什么要用数学归纳法证呢？
本来就可以直接计算嘛

迭代计算，呵呵
(1)对于两层循环：
[code]
for (int i = 1; i <= n; ++i)
   for (int j = 1; j <= i; ++j)
          A; // do someth ...

... 数学公式编辑器都有...工具好全哈哈...

tyc611

总算把“=”填上去了

tyc611

原帖由 Edengundam 于 2007-1-18 19:59 发表



... 数学公式编辑器都有...工具好全哈哈...

没办法，不好编辑，只能用Word了

langue

为什么要用数学归纳法证呢？
本来就可以直接计算嘛

迭代计算，呵呵
(1)对于两层循环：

1. 
   
2. for (int i = 1; i <= n; ++i)
   
3.    for (int j = 1; j <= i; ++j)
   
4.           A; // do something here
   

复制代码

有：A计算次数有为P(2， n) = (1+2+...+n) = n(1+n)/2

(2)对于k层循环(k>=2)，假设其计算次数为：P(k，m) ，则
对于k+1层循环，有：

....

嗯，数归，就是它了。

谢谢 eden 和 tyc

tyc611

原帖由 langue 于 2007-1-18 20:03 发表


嗯，数归，就是它了。

谢谢 eden 和 tyc

呵呵，一块学习，一块进步

Edengundam

原帖由 langue 于 2007-1-18 20:03 发表


嗯，数归，就是它了。

谢谢 eden 和 tyc

呵呵...数学归纳用于证明.

组合数学里面有生成函数的介绍...能解很多复杂的递归问题. (可惜我数学太差了...)