알고리즘

Question

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

이에 변화가 나던 것은이 요소

Answer 1

기술적으로의 수를 알 수있는 algorithim이다, 그래, k <= i는 불변하지만 매우 유용한 일이다. 우리가 불변량을 사용하는 이유는 루프 이후에 상태를 증명할 수 있기 때문입니다. invariant를 사용하면 루프 이후에 k <= n이 있다는 것을 증명할 수 있습니다. 사실이지만 루프가 실제로 무엇을하는지 증명하려고하는 것은 도움이되지 않습니다.

그래서 어떤 불변량이 유용할까요? 우리는 k이 a과 b에있는 요소의 수와 동일하다는 것을 증명하고 싶습니다. a의 요소를 반복하므로 좋은 선택은 k이고 a[i]까지의 요소 수는 b입니다.

---

이제이 불변성이 있음을 증명해야합니다. 나는 그것을 좀 더 개략적으로 유지할 것이므로 이것을 공식화하는 것은 당신에게 달려있다.

초기에 우리는 k = 0이 a[1] 앞에있는 요소의 수이고 또한 b 인 것을 보여줄 필요가 있습니다. 해당 요소가 없기 때문에 k = 0이 맞습니다.

이제는 까지의 요소 수가 b이기 때문에에 대해 불변식이 성립한다는 것을 증명해야합니다. 두 가지 옵션이 있습니다. a[i+1]은 b에 있거나없는 것입니다.

• 는 b에 a[i+1] 경우 b에 a[i + 1]까지의 요소의 수는 b에 a[i] 최대 요소의 수보다 하나 더 크다. 불변 식을 사용하면 ki+1 = ki + 1을 표시해야합니다.
• a[i+1]하지 b에서 다음 b에 a[i + 1] 최대 요소의 수가 b에 a[i] 최대 요소의 수와 동일한 경우. 불변량을 사용하면 ki+1 = ki을 표시해야합니다.

나는 그 사실을 증명하기 위해 남겨 두겠습니다.