如何分析这伪

我有以下的伪代码:

sum<-0 inc<-0 for i from 1-n for j from 1 to i sum<-sum+inc inc<-inc+1

我要求找到一个封闭的公式。 该提示是使用普通求和。 不管我怎么看它,我不能写总结的形式此代码。 有人可以给我的总和会是什么样子,甚至一个递推公式的想法?

--------------解决方案-------------

假设for i from 1-n的意思是:

for i from 1 to n

对于一个封闭的公式可以通过一些数值分析得到。 让我们检查的次数通过循环的一对夫妇的值n (5和6)。

外环总是n倍,内环无论i是每次迭代,因此对于价值观n ,这里有迭代计数:

n count
= ===========================================
1 (1) = 1
2 (1),(12) = 3
3 (1),(12),(123) = 6
4 (1),(12),(123),(1234) = 10
5 (1),(12),(123),(1234),(12345) = 15
6 (1),(12),(123),(1234),(12345),(123456) = 21

这些闭合式最好说明如下:

n = 5: 5 + 4 + 3 + 2 + 1
| | | | |
| | V | |
| | 3 | | Formula is: (n+1)*((n-1)/2) + ((n+1)/2)
| +-> 6 <-+ | [outer pair sets] + [inner value]
+-----> 6 <-----+
--
15

这是所有的奇值的公式n 。 为偶数值,可以使用类似的方法:

n = 6: 6 + 5 + 4 + 3 + 2 + 1
| | | | | |
| | +-> 7 <-+ | | Formula is: (n+1)*(n/2)
| +-----> 7 <-----+ | [outer pair sets]
+---------> 7 <---------+
--
21

这告诉你的每个值的嵌套循环迭代的次数n (我们称这个x )。

的最终值的计算sum是非常相似的。 在第一次迭代中添加为零。 在第二次迭代,你添加一个。 在第三次迭代中,增加了两个。 这几乎是正是你不得不做搞清楚迭代次数同样的事情,只是现在它是基于x而非n ,它是0+1+2+...而不是1+2+3+... ,这意味着我们可以仅仅通过其申请使用完全相同的公式x-1而不是x

因此,我们可以使用:

if n is odd:
x <- (n+1) * ((n-1)/2) + ((n+1)/2)
else:
x <- (n+1) * (n/2)
x <- x - 1
if x is odd:
sum <- (x+1) * ((x-1)/2) + ((x+1)/2)
else:
sum <- (x+1) * (x/2)

选中此对算法的前几个值n

n algorithm formula
- --------- -------
0 0 0
1 0 0
2 3 3
3 15 15
4 45 45
5 105 105

所以,绝配,至少withing选择的样本空间。 其实你可以走的更远,并把它转换成一个公式的基础上n单独,而不是制定一个中间值,但我会离开,作为一个练习留给读者。



提示:AC公式,同时适用于单双号是:

x <- ((n+1) * ((n-(n%2))/2)) + ((n%2) * ((n+1)/2))

(虽然还没有测试的负值n -你应该把检查您所使用的公式化的版本之前)。

最内层的循环(我们只是叫i一个固定的号码):

inc递增i倍。
suminc添加到它i倍。 (我*(I-1)/ 2,对吧?)

如果我们假设incsum开始艺术价值为0,那么这是有效的。 如果我们假设他们开始在一些不同的价值,我们姑且称之为kl ,那么我们知道, inc将在价值最终k+i 。 我们知道, sum将在最终l+k*i + i*(i-1)/2

现在, i本身是从去1n 。 嗯...哼哼。 让我想想这多一点。

分类:数学 时间:2015-03-15 人气:0
本文关键词: 数学
分享到:

相关文章

Copyright (C) 55228885.com, All Rights Reserved.

55228885 版权所有 京ICP备15002868号

processed in 0.629 (s). 10 q(s)