470D96 — Анализ алгоритмов с массивами: ответ и решение

Впишите правильный ответ.

В программе используется одномерный целочисленный массив A с индексами от 0 до 11. Значения элементов массива A[i] приведены в таблице.

i	0	1	2	3	4	5	6	7	8	9	10	11
A[i]	53	17	33	12	49	8	3	20	2	19	7	22

Определите значение переменной s после выполнения следующего фрагмента этой программы (записанного ниже на пяти языках программирования).

Бейсик

s = 0

n = 2

FOR i = 1 TO 11

IF A(i - 1) \ A(i) > n THEN

s = s + A(i)

ELSE

A(i) = A(i) * i

END IF

NEXT i

Python

s = 0

n = 2

for i in range(1, 12):

if A[i - 1] // A[i] > n:

s += A[i]

else:

A[i] *= i

Алгоритмический язык

s := 0

n := 2

нц для i от 1 до 11

если div(A[i - 1], A[i]) > n то

s := s + A[i]

иначе

A[i] := A[i] * i

все

кц

Паскаль

s := 0;

n := 2;

for i := 1 to 11 do

if A[i - 1] div A[i] > n then

s := s + A[i]

else

A[i] := A[i] * i;

С++

s = 0;

n = 2;

for (int i = 1; i < 12; i++)

{

if (A[i - 1] / A[i] > n)

s += A[i];

else

A[i] *= i;

}

СВОЙСТВА ЗАДАНИЯ

КЭС:

2.13 Графы. Основные понятия. Виды графов. Описание графов с помощью матриц смежности, весовых матриц, списков смежности. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа)

2.14 Деревья. Бинарное дерево. Деревья поиска. Способы обхода дерева. Представление арифметических выражений в виде дерева. Использование графов и деревьев при описании объектов и процессов окружающего мира

3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность

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

3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве

3.11 Двумерные массивы (матрицы). Алгоритмы обработки двумерных массивов: заполнение двумерного числового массива по заданным правилам, поиск элемента в двумерном массиве, вычисление максимума (минимума) и суммы элементов двумерного массива, перестановка строк и столбцов двумерного массива

3.12 Словари (ассоциативные массивы, отображения). Хэш-таблицы. Построение алфавитно-частотного словаря для заданного текста

3.13 Стеки. Анализ правильности скобочного выражения. Вычисление арифметического выражения, записанного в постфиксной форме. Очереди. Использование очереди для временного хранения данных

3.14 Алгоритмы на графах. Построение минимального остовного дерева взвешенного связного неориентированного графа. Количество различных путей между вершинами ориентированного ациклического графа. Алгоритм Дейкстры

3.15 Деревья. Реализация дерева с помощью ссылочных структур. Двоичные (бинарные) деревья. Построение дерева для заданного арифметического выражения. Рекурсивные алгоритмы обхода дерева. Использование стека и очереди для обхода дерева

Тип ответа:

Краткий ответ

Номер: 470D96

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINF470D96

Ответ: 46

Решение.
Индексы массива идут от 0 до 11. Начальное состояние:
A = [53; 17; 33; 12; 49; 8; 3; 20; 2; 19; 7; 22].
Нужно найти итоговое значение переменной s. Читаем команды в указанном порядке: каждое следующее действие использует уже изменённые значения. Правая часть присваивания вычисляется до записи результата; знак ← ниже обозначает присваивание.
Начальная команда: s ← 0.
Начальная команда: n ← 2.
Скобки ⌊ ⌋ обозначают целую часть частного. Все делимые и делители в этой задаче положительны, поэтому целочисленное деление отбрасывает дробную часть. В следующем проходе делимое может быть уже изменено предыдущей командой.
Цикл перебирает i от 1 до 11 включительно; число проходов — 11.
Проверяем условие: ⌊A[i − 1]A[i]⌋ больше n. Если оно верно, выполняем по порядку:
s ← s + A[i].
Если условие неверно, выполняем:
A[i] ← A[i] · i.
Полная трассировка. Для каждой проверки берём значения из текущего массива:
i = 1: ⌊A[i − 1]A[i]⌋ = ⌊5317⌋ = 3; n = 2.
Условие 3 больше 2 — верно.
s = 0 + 17 = 17.
Текущий массив: [53; 17; 33; 12; 49; 8; 3; 20; 2; 19; 7; 22].
i = 2: ⌊A[i − 1]A[i]⌋ = ⌊1733⌋ = 0; n = 2.
Условие 0 больше 2 — неверно.
s = 17 + 0 = 17.
Текущий массив: [53; 17; 66; 12; 49; 8; 3; 20; 2; 19; 7; 22].
i = 3: ⌊A[i − 1]A[i]⌋ = ⌊6612⌋ = 5; n = 2.
Условие 5 больше 2 — верно.
s = 17 + 12 = 29.
Текущий массив: [53; 17; 66; 12; 49; 8; 3; 20; 2; 19; 7; 22].
i = 4: ⌊A[i − 1]A[i]⌋ = ⌊1249⌋ = 0; n = 2.
Условие 0 больше 2 — неверно.
s = 29 + 0 = 29.
Текущий массив: [53; 17; 66; 12; 196; 8; 3; 20; 2; 19; 7; 22].
i = 5: ⌊A[i − 1]A[i]⌋ = ⌊1968⌋ = 24; n = 2.
Условие 24 больше 2 — верно.
s = 29 + 8 = 37.
Текущий массив: [53; 17; 66; 12; 196; 8; 3; 20; 2; 19; 7; 22].
i = 6: ⌊A[i − 1]A[i]⌋ = ⌊83⌋ = 2; n = 2.
Условие 2 больше 2 — неверно.
s = 37 + 0 = 37.
Текущий массив: [53; 17; 66; 12; 196; 8; 18; 20; 2; 19; 7; 22].
i = 7: ⌊A[i − 1]A[i]⌋ = ⌊1820⌋ = 0; n = 2.
Условие 0 больше 2 — неверно.
s = 37 + 0 = 37.
Текущий массив: [53; 17; 66; 12; 196; 8; 18; 140; 2; 19; 7; 22].
i = 8: ⌊A[i − 1]A[i]⌋ = ⌊1402⌋ = 70; n = 2.
Условие 70 больше 2 — верно.
s = 37 + 2 = 39.
Текущий массив: [53; 17; 66; 12; 196; 8; 18; 140; 2; 19; 7; 22].
i = 9: ⌊A[i − 1]A[i]⌋ = ⌊219⌋ = 0; n = 2.
Условие 0 больше 2 — неверно.
s = 39 + 0 = 39.
Текущий массив: [53; 17; 66; 12; 196; 8; 18; 140; 2; 171; 7; 22].
i = 10: ⌊A[i − 1]A[i]⌋ = ⌊1717⌋ = 24; n = 2.
Условие 24 больше 2 — верно.
s = 39 + 7 = 46.
Текущий массив: [53; 17; 66; 12; 196; 8; 18; 140; 2; 171; 7; 22].
i = 11: ⌊A[i − 1]A[i]⌋ = ⌊722⌋ = 0; n = 2.
Условие 0 больше 2 — неверно.
s = 46 + 0 = 46.
Текущий массив: [53; 17; 66; 12; 196; 8; 18; 140; 2; 171; 7; 242].
Проверка: условие выполнено при i = 1, 3, 5, 8, 10.
Сумма всех приращений s: 17 + 0 + 12 + 0 + 8 + 0 + 0 + 2 + 0 + 7 + 0 = 46.
Ветвь иначе может изменять само значение элемента массива. Поэтому здесь нельзя считать элементы постоянными; их окончательные значения получены последовательными присваиваниями, приведёнными выше.
Все 11 допустимых значений индекса рассмотрены по одному разу. После последнего прохода команд, изменяющих s, больше нет.
Ответ: 46.

Задание EGEINF470D96: Анализ алгоритмов с массивами

Решение задания EGEINF470D96

Помочь улучшить сайт

Комментарии к решению