algorithm - 终止函数定义（算法）

Answer 1

对于进入循环的状态，终止函数μ必须为正，并且每次迭代都严格递减。再加上自然数的有序性，可确保您的循环始终终止。（请注意，对于退出循环的s ，不要求μ(s) = 1，只是每次迭代它总是减小。）

选择μ(r,n) = n + r的问题在于，对于n = 2，我们有

• 偶数_
• n > 1

所以过渡[r, n] -> [r + 1, n / 2]是有效的。但是，在这种情况下，我们会有

μ(r',n') =         Definition of r' and n'
μ(r+1,n/2) =       Definition of μ
r + 1 + n/2 =      Rearrange via n = 2
r + 2 = 
r + n =            Definition of μ
μ(r, n)

所以μ不会严格减少。