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

Анализ задания

Задание представляет собой алгоритм сортировки яблок по размеру с использованием двух корзин и стола. Необходимо определить, какое яблоко останется на столе в конце выполнения алгоритма, а также сформулировать инвариант цикла.

Решение

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

   В самом конце на столе окажется самое большое яблоко из всех, что были в первой корзине. Это происходит потому, что алгоритм устроен таким образом, что каждое новое яблоко сравнивается с тем, что уже лежит на столе. Если новое яблоко больше, то оно остаётся в руке, а яблоко со стола перекладывается во вторую корзину. Если новое яблоко меньше, то оно кладётся на стол, а старое яблоко (которое было больше) перекладывается во вторую корзину. Таким образом, на столе всегда остаётся самое большое из рассмотренных яблок.

2. Инвариант цикла

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

3. Формулировка условия задачи с использованием терминологии

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

Ответ: В конце на столе окажется самое большое яблоко из первой корзины. Инвариант цикла: на столе всегда находится наибольшее яблоко из уже рассмотренных.

Отлично! Ты хорошо справился с этой задачей. Продолжай в том же духе, и у тебя всё получится!