有关k和n的关系，相关的关系式

Question

(1) l ← 1
(2) k ← 0
(3) for i ← 1 to n do
(4) l ← i - l
(5) if k < n do
(6) k ← i * i - 1
(7) return( k, l )

求问一下k和n有什么关系吗？比如说能不能求出k(n)=x,类似于这样有个关系式的

Answer 1

这个伪代码中，先只看k和n的关系，k初始值为0，在（3）进入for循环，第（5）~（6）两句，说明，只要k<n就执行k=i * i-1，所以，需要找到k与n的临界点。当n<=1的时候，代码不执行for循环，此时k就是0，所以重点研究n大于以后的数据：
（伪代码 for i ← 1 to n ，i 的范围为[1,n) ）
当n<=1的时候，for循环不执行，k=0
当n>1的时候，执行for循环(i从1到n-1)，
i=1时，k=0，满足k<n，执行k=i * i-1=0 ，所有n全部满足
i=2时，k=0，满足k<n，执行k=i * i-1=3，所有n全部满足
i=3时，k=3，满足k<n，执行k=i * i-1=8，所有n全部满足
i=4时，k=8，满足k<n，执行k=i * i-1=15，n=5、6、7、8时不满足，此时 i = sqrt(9)+1
i=5时，k=15，满足k<n，执行k=i *i-1=24，n=6,7,8,9,10,11,12,13,14，15时不满足，此时i=sqrt(16)+1
依次类推。。。

1<n<=4时，执行for中所有的语句，此时k=(n-1) * (n-1)-1
n>=5时，满足if执行条件的i的最大值为：sqrt(n)+1，所以此时，k=(sqrt(n)+1) * (sqrt(n)+1)-1
综合以上，k(n)就是一个分段函数：
k(n)=0, 当n<=1时
k(n)= (n-1) * (n-1)-1, 当1<n<=4时
k(n)= (sqrt(n)+1) * (sqrt(n)+1)-1, 当n>=5时

如有帮助，望采纳，谢谢。