То, что не меняется в алгоритме

Question

k :=0
for i ←1 to n
     c←a[i]
           k←k+1

это алгоритм, чтобы узнать количество элементов

Answer 1

Технически, да, k <= i является инвариантом, но не очень полезным. Причина, по которой мы используем инварианты, заключается в том, что мы можем использовать их для проверки состояния после цикла. С вашим инвариантом вы можете доказать, что k <= n держит после цикла. Хотя это очень верно, это не поможет вам попытаться доказать, что на самом деле делает цикл.

Так какой вид инварианта будет полезен? Мы хотим доказать это k равно количеству элементов, которые оба в a а также b, Так как мы перебираем элементы в aхорошим выбором будет: k равно количеству элементов до a[i] которые также находятся в b,

---

Теперь нам нужно доказать, что этот инвариант имеет место. Я сделаю это немного отрывочно, так что вы все еще можете оформить это.

Сначала нам нужно показать, что k = 0 количество элементов перед a[1] которые также находятся в b, Там нет таких элементов, поэтому k = 0 верно.

Теперь, учитывая, что ki это количество элементов до a[i] которые также находятся в bнам нужно доказать, что инвариант выполняется для i+1, Есть два варианта: либо a[i+1] в b, или нет.

• Если a[i+1] в b, то количество элементов до a[i + 1] которые находятся в b на единицу больше, чем количество элементов до a[i] которые находятся в b, Используя наш инвариант, мы должны показать, что ki+1 = ki + 1,
• Если a[i+1] не в b, то количество элементов до a[i + 1] которые находятся в b равно количеству элементов до a[i] которые находятся в b, Используя наш инвариант, мы должны показать, что ki+1 = ki,

Я оставлю это на ваше усмотрение, чтобы доказать это.