Рядом с вами находятся две корзины. Первая наполнена яблоками разных размеров, вторая — пустая

Рядом с вами находятся две корзины. Первая наполнена яблоками разных размеров, вторая — пустая.

Шаг 1. Вы берете любое яблоко из первой корзины и кладете его на стол перед собой.

Шаг 2. Вы достаете следующее яблоко из первой корзины и выполняете сравнение:

— если яблоко в руках больше, чем яблоко на столе, то вы опускаете яблоко, которое у вас в руках, во вторую корзину;

— если яблоко в руках меньше яблока на столе, вы кладёте яблоко на стол, а яблоко, которое лежало на столе, перекладываете во вторую корзину.

Вы повторяете шаг 2 до тех пор, пока первая корзина не опустеет.

Какое яблоко окажется на столе в самом конце?

Попытайтесь сформулировать, что является инвариантом цикла в приведенном алгоритме. Сформулируйте условие задачи.

Ответ

После выполнения шага 1 на столе лежит яблоко, которое достали из корзины первым, а вторая корзина пуста. После каждого выполнения шага 2 большее яблоко перемещается в корзину, а меньшее остается на столе. В результате на столе окажется самое маленькое яблоко.

При обосновании корректности циклических алгоритмов полезно использовать понятие инварианта цикла. В случае приведенного алгоритма инвариантом цикла является такое условие «лежащее на столе яблоко — самое маленькое из всех взятых до сих пор». В начале алгоритма условие очевидно выполняется (любое яблоко удовлетворяет этому условию). Условие остается истинным на каждом шаге в соответствии с приведенными правилами. Таким образом, в конце алгоритма, когда все яблоки взяты, получим самое маленькое яблоко из всех.

Опубликовано: 15.11.2019 Обновлено: 15.11.2019
Поделись с друзьями

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

5 × четыре =