Рядом с вами находятся две корзины. первая наполнена яблоками разных размеров, вторая - пустая.
шаг 1. вы берете любое яблоко из первой корзины и кладете его на стол перед собой.
шаг 2. вы достаете следующее яблоко из первой корзины и выполняете сравнение:
- если яблоко в руках больше, чем яблоко на столе, то вы опускаете яблоко, которое у вас в руках, во вторую корзину;
- если яблоко в руках меньше яблока на столе, вы кладете яблоко на стол, а яблоко которое лежало на столе, перекладываете во вторую корзину.
вы повторяете шаг 2 до тех пор , пока первая корзина не опустеет. какое яблоко окажется на столе в самом конце? попытайтесь сформулировать, что является инвариантом цикла в алгоритме сформулируйте условие с использованием терминологии, рассмотренной в этом параграфе.
1. Берем любое яблоко из первой корзины и кладем его на стол.
2. Берем следующее яблоко из первой корзины и сравниваем его с яблоком на столе:
- Если яблоко в руках больше, чем яблоко на столе, мы опускаем яблоко, которое у нас в руках, во вторую корзину.
- Если яблоко в руках меньше яблока на столе, мы кладем яблоко на стол, а яблоко, которое лежало на столе, перекладываем во вторую корзину.
Мы повторяем шаг 2 до тех пор, пока первая корзина не опустеет.
Теперь давайте определим, какое яблоко окажется на столе в самом конце.
Инвариантом цикла в данном алгоритме является то, что яблоко на столе всегда будет самым большим из всех яблок, которые мы взяли из первой корзины, но еще не опустили во вторую корзину. Это происходит благодаря тому, что мы опускаем только яблоки, которые больше яблока на столе, а кладем на стол только яблоко, которое меньше яблока на столе.
Таким образом, в самом конце на столе окажется самое большое яблоко из первой корзины.
Мы можем формализовать условие используя терминологию данного алгоритма:
Если яблоко в руках меньше яблока на столе, то выполняем:
- Кладем яблоко на стол
- Перекладываем яблоко, которое было на столе, во вторую корзину
Если яблоко в руках больше или равно яблоку на столе, то выполняем:
- Опускаем яблоко во вторую корзину
Данный алгоритм позволяет нам находить наибольшее яблоко из заданного множества и перекладывать остальные яблоки в отдельную корзину.