Question

设n为正整数。试确定下列各程序段中前置以记号@的语句频度：

(1) x=n; y=0; //n为不小于1的常数
while (x>=(y+1)*(y+1)) {
@ y++;
}

(2) i=1; j=0;
while (i+j<=n) {
@ if (i>j) j++;
else i++;
}

注：@语句指的是if…else语句，语句频度为j++和i++执行的次数之和。

Answer 1

(4)
i=1时，第二个for语句执行n次；i=2时，第二个for语句执行n-1次；i=3时，第二个for语句执行n-2次......
i=n时，第二个for语句执行1次。
所以语句频度=n+(n-1)+(n-2)+...+1=n(n+1)/2
(5)
原理与(4)类似
所以语句频度=1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=n(n+1)(2n+3)/12
(8)
分析每一次循环可以发现，当循环执行10次后x>100，y方才减1，此时x被复原为91；
如此下去，由于每执行10次循环才使y减1，所以循环体执行100*10次，也就是说if语句判断执行了1000次（但里面的y--执行了100次）。
所以语句频度=1100