Variante de loop por um loop while que ocasionalmente não diminui?

Estou trabalhando em problemas práticos para um teste que tenho e todos os exemplos de variantes de loop diminuíram a cada iteração do loop. Nesse, os valores permanecem os mesmos quando a <b. Minhas tentativas também me deram uma variante de loop que tem uma chance de ser negativa, uma vez que ocasionalmente a se torna maior que be vice-versa. Algum conselho sobre como tentar encontrar e provar a variante de loop para esta pergunta?

def mystery(a,b):
# Precondition: a >= 0 and b >= 0
while a >= 0 and b >= 0:
    if a < b:
        a, b = b, a
    else:
        a = a - 1
return a

Edição: Para quem está interessado nesta pergunta, minha melhor solução é a seguinte.

f_{1} = a + 2 b + 1

$f_{1} = a + 2b + 1$

algorithms loops loop-invariants Andrew Raleigh
fonte

Muito agradável! Eu acho que você deveria fazer disso uma resposta (ou mesmo a resposta).

Anton Trunov

Respostas:

Apenas uma dica por enquanto, já que este é um problema prático: considere uma combinação lexicográfica de pedidos.

Em mais alguns detalhes: Suponha que você tenha dois mapas e de seu programa afirma em domínios ordenados bem fundamentadas e . A combinação lexicográfica de e é a ordem em dada por se ou . Também é bem fundamentado. $f_1:S\to D_1$ $f_2:S\to D_2$ $S$ $(D_1,\le_1)$ $(D_2,\le_2)$ $\le_1$ $\le_2$ $\le$ $D_1\times D_2$ $(x_1,y_1)\le(x_2,y_2)$ $x_1\le_1x_2$ $x_1=x_2,y_1\le_2y_2$

Portanto, se são tais que $f_1,f_2$

$f_1$ nunca aumenta e
sempre que não diminui, diminui , $f_1$ $f_2$

então o mapa é uma variante que comprova a terminação. $(f_1,f_2):S\to D_1\times D_2$

Klaus Draeger
fonte

Obrigado pela dica! Ainda não fizemos combinações lexicográficas, analisarei agora. Você poderia explicar como isso permitiria diminuir em todos os casos?

Andrew Raleigh

@AndrewRaleigh Adicionei alguns detalhes

Klaus Draeger

Isso faz muito sentido, nunca pensei nisso dessa maneira. Neste caso, seria e ? Embora ocasionalmente permaneça o mesmo, e os slides das palestras não dizem nada sobre isso ser permitido ou não.

f_{1} = a

$f_{1} = a$

f_{2} = b - a

$f_{2} = b - a$

Andrew Raleigh

O problema com é que ele pode aumentar (quando são trocados). Tente encontrar uma expressão que permaneça a mesma neste caso e diminua na outra (quando é decrementado).

f_{1} = a

$f_1=a$

a, b

$a,b$

a

$a$

Klaus Draeger

Aqui está uma abordagem envolvendo apenas um mapeamento: A análise de caso simples pode mostrar que sempre diminui à medida que você percorre o loop.

f = (a + 1) \cdot (b + 1) + (b - a)

$f = (a+1) \cdot (b+1) + (b - a)$

f

$f$

Anton Trunov
fonte