Рядом с вами находятся две корзины. Первая наполнена яблоками разных размеров, вторая - пустая.
Шаг 1. Вы берете любое яблоко из первой корзины и кладете его на стол перед собой.
Шаг 2. Вы достаете следующее яблоко из первой корзины выполняете сравнение:
- если яблоко в руках больше, чем яблоко на столе, то вы опускаете яблоко, которое у вас в руках, во вторую корзину
- если яблоко в руках меньше яблока на столе, вы кладете яблоко на стол, а яблоко, которое лежало на столе, перекладываете во вторую корзину
Вы повторяете шаг 2 до тех пор, пока первая корзина не опустеет
Какое яблоко окажется на столе в самом конце?
Сформулируйте, что является инвариантом цикла в приведённом алгоритме.

Ответ:

На столе окажется наименьшее яблоко. Инвариантом является то, что яблоко на столе всегда меньше любого яблока из второй корзины.

Объяснение:

Инвариант — это некоторое свойство или значение, которое не меняется в ходе выполнения. Вообще инвариантов может быть достаточно много, но в данном случае будет полезен, например, такой:

Яблоко на столе меньше любого яблока из второй корзины

В самом деле, это свойство можно доказать, к примеру, по индукции.

База индукции: В начальный момент (после шага 1) свойство выполнено. Во второй корзине нет яблок, меньших лежащего на столе (да и вообще нет ни одного яблока).

Переход: Пусть известно, что все лежащие во второй корзине яблоки больше данного. Докажем, что и на следующем шаге тоже будет так.

Рассмотрим два случая.

1. Новое яблоко больше лежащего на столе. Тогда оно сразу отправляется во вторую корзину, яблок, меньших лежащего на столе, во второй корзине не прибавилось.
2. Новое яблоко меньше лежащего на столе. После того, как новое яблоко положат на стол, во второй корзине будет яблоко, которое лежало на столе до этого (оно больше нового по предположению), и все яблоки, которые лежали там до этого (они больше того, что было на столе, а значит, тем более больше нового яблока).

В конечный момент времени все яблоки из первой корзины кроме одного окажутся во второй корзине, а лежащее на столе будет меньше остальных. Значит, на столе окажется наименьшее яблоко.