ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Анализ алгоритмов с массивами.
| КЭС: | 3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность 3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат 3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена» 3.5 Многоразрядные целые числа, задачи длинной арифметики |
| Тип ответа: | Краткий ответ |
Ответ: 4
Решение.
Индексы массива идут от 0 до 9. Начальное состояние:
A = [2; 6; 4; 7; 8; 1; 0; 2; 9; 3].
Нужно найти итоговое значение переменной c. Читаем команды в указанном порядке: каждое следующее действие использует уже изменённые значения. Правая часть присваивания вычисляется до записи результата; знак ← ниже обозначает присваивание.
Начальная команда: c ← 0.
Цикл перебирает i от 0 до 8 включительно; число проходов — 9.
Проверяем условие: A[i] больше A[9]. Если оно верно, выполняем по порядку:
c ← c + 1.
t ← A[i].
A[i] ← A[9].
A[9] ← t.
Если условие неверно, тело ветвления пропускается: массив и накопитель на этом проходе не меняются.
Полная трассировка. Для каждой проверки берём значения из текущего массива:
i = 0: A[i] = 2; A[9] = 3.
Условие 2 больше 3 — неверно.
c = 0 + 0 = 0.
Текущий массив: [2; 6; 4; 7; 8; 1; 0; 2; 9; 3].
i = 1: A[i] = 6; A[9] = 3.
Условие 6 больше 3 — верно.
c = 0 + 1 = 1.
Текущий массив: [2; 3; 4; 7; 8; 1; 0; 2; 9; 6].
i = 2: A[i] = 4; A[9] = 6.
Условие 4 больше 6 — неверно.
c = 1 + 0 = 1.
Текущий массив: [2; 3; 4; 7; 8; 1; 0; 2; 9; 6].
i = 3: A[i] = 7; A[9] = 6.
Условие 7 больше 6 — верно.
c = 1 + 1 = 2.
Текущий массив: [2; 3; 4; 6; 8; 1; 0; 2; 9; 7].
i = 4: A[i] = 8; A[9] = 7.
Условие 8 больше 7 — верно.
c = 2 + 1 = 3.
Текущий массив: [2; 3; 4; 6; 7; 1; 0; 2; 9; 8].
i = 5: A[i] = 1; A[9] = 8.
Условие 1 больше 8 — неверно.
c = 3 + 0 = 3.
Текущий массив: [2; 3; 4; 6; 7; 1; 0; 2; 9; 8].
i = 6: A[i] = 0; A[9] = 8.
Условие 0 больше 8 — неверно.
c = 3 + 0 = 3.
Текущий массив: [2; 3; 4; 6; 7; 1; 0; 2; 9; 8].
i = 7: A[i] = 2; A[9] = 8.
Условие 2 больше 8 — неверно.
c = 3 + 0 = 3.
Текущий массив: [2; 3; 4; 6; 7; 1; 0; 2; 9; 8].
i = 8: A[i] = 9; A[9] = 8.
Условие 9 больше 8 — верно.
c = 3 + 1 = 4.
Текущий массив: [2; 3; 4; 6; 7; 1; 0; 2; 8; 9].
Проверка: условие выполнено при i = 1, 3, 4, 8.
Сумма всех приращений c: 0 + 1 + 0 + 1 + 1 + 0 + 0 + 0 + 1 = 4.
На каждом проходе происходил только обмен двух значений либо пропуск. Набор чисел и их количества в конечном массиве совпадают с исходными; обмен равных значений тоже выполняется, если условие истинно.
Все 9 допустимых значений индекса рассмотрены по одному разу. После последнего прохода команд, изменяющих c, больше нет.
Ответ: 4.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF514F27.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.