ЕГЭ и ОГЭФИПИ · понять и решить
Начать подготовку
Меню

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

ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий

Открыть решение ↓ Ошибка или пожелание

Тип задачи: Анализ алгоритмов с массивами.

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

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

Значения двумерного массива размера 7×7 задаются с помощью вложенного оператора цикла в представленном фрагменте программы:

Бейсик

Паскаль

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

FOR n=1 TO 7
FOR k=1 TO 7
B(n, k)=k–n
NEXT k
NEXT n

for n:=1 to 7 do
for k:=1 to 7 do
  B[n, k]:=k–n;

нц для n от 1 до 7
нц для k от 1 до 7
  B[n, k]=k–n
кц
кц

Сколько элементов массива будут иметь положительные значения?


 1) 

49

 2) 

28

 3) 

21

 4) 

7


i
СВОЙСТВА ЗАДАНИЯ
КЭС:
2.13 Графы. Основные понятия. Виды графов. Описание графов с помощью матриц смежности, весовых матриц, списков смежности. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа)
2.14 Деревья. Бинарное дерево. Деревья поиска. Способы обхода дерева. Представление арифметических выражений в виде дерева. Использование графов и деревьев при описании объектов и процессов окружающего мира
3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность
3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат
3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве
3.11 Двумерные массивы (матрицы). Алгоритмы обработки двумерных массивов: заполнение двумерного числового массива по заданным правилам, поиск элемента в двумерном массиве, вычисление максимума (минимума) и суммы элементов двумерного массива, перестановка строк и столбцов двумерного массива
3.12 Словари (ассоциативные массивы, отображения). Хэш-таблицы. Построение алфавитно-частотного словаря для заданного текста
3.13 Стеки. Анализ правильности скобочного выражения. Вычисление арифметического выражения, записанного в постфиксной форме. Очереди. Использование очереди для временного хранения данных
3.14 Алгоритмы на графах. Построение минимального остовного дерева взвешенного связного неориентированного графа. Количество различных путей между вершинами ориентированного ациклического графа. Алгоритм Дейкстры
3.15 Деревья. Реализация дерева с помощью ссылочных структур. Двоичные (бинарные) деревья. Построение дерева для заданного арифметического выражения. Рекурсивные алгоритмы обхода дерева. Использование стека и очереди для обхода дерева
Тип ответа:Выбор ответа
Номер: 230CBE
НЕ РЕШЕНО Ответить

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

Ответ: 3

Решение.
Два вложенных цикла независимо перебирают n и k от 1 до 7 включительно. Каждой паре индексов соответствует ровно одна ячейка; всего ячеек 7 · 7 = 49.
После присваивания значение элемента равно B[n, k] = k − n. Положительное значение получается тогда и только тогда, когда k больше n. Равенство индексов даёт нуль, и такие ячейки учитывать нельзя.
Зафиксируем первый индекс n и перечислим все допустимые вторые индексы:
n = 1: k = 2, 3, 4, 5, 6, 7; количество — 6.
n = 2: k = 3, 4, 5, 6, 7; количество — 5.
n = 3: k = 4, 5, 6, 7; количество — 4.
n = 4: k = 5, 6, 7; количество — 3.
n = 5: k = 6, 7; количество — 2.
n = 6: k = 7; количество — 1.
n = 7: подходящих k нет; количество — 0.
Складываем числа ячеек по всем семи строкам:
6 + 5 + 4 + 3 + 2 + 1 + 0 = 21.
Проверка симметрией: на главной диагонали семь нулей. Остальные 49 − 7 = 42 ячейки разбиваются на пары (n, k) и (k, n). Их значения k − n и n − k противоположны, поэтому в каждой паре ровно одно значение положительное. Получаем 422 = 21, как и при подсчёте по строкам.
Нужно указать номер варианта, а не число элементов. Значение 21 находится в варианте 3.
Ответ: 3.

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

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF230CBE.

Сообщение увидит только команда сайта: на странице оно не публикуется.

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

Комментарии видны всем посетителям сайта.

Комментариев пока нет. Будьте первым.

Чтобы оставить комментарий, войдите или зарегистрируйтесь.