解释离散数学的这种算法及其应用

Question

描述一个算法，该算法将一个整数x插入到升序整数的列表a_1，a_2，...，a_n中的适当位置。

一个。

procedure insert(x,a_1,a_2,...,a_n :integers)
{the list is in order: a_1<=a_2<=...<=a_n}
a_(n+1) := x+1
i :=1
while x>a_i
i :=i+1
for j:=0 to n-i
a_(n-j+1) := a_(n-j)
a_i=x
{x has been inserted into correct position}

我的问题。为什么是a_(n+1) := x+1？如果初始值是i=n，然后是j=0 to -1？我要排除j=-1吗？很抱歉说得不好，请解释一下这个算法

Answer 1

为什么选择a_(n+1) := x+1？

这就是sentinel node方法。

使用此stop元素，可以使用相同的方法将x插入到列表的任何位置。否则，必须查看list是否已完成，并在末尾附加x并添加特殊的代码段

如果初始值为i=n，则j=0为-1？

这意味着for j:=0 to -1的运算符不会被执行(一些语言有特殊类型的反向for循环，如Pascal中的for ..downto或其他语言中的step参数)