Курс «Алгоритмизация вычислений» будет вам интересен и просто необходим, если вы хотели бы изучить программирование с нуля и выйти на хороший базовый уровень, научиться составлять, понимать и анализировать алгоритмы. В результате изучения курса вы сможете: • записывать математическую постановку задачи; • применять стандартные алгоритмы для решения задач; • оценивать оптимальность алгоритмов и выбирать алгоритм, дающий лучшее решение задачи; • проверять правильность алгоритма методом трассировки; • кодировать алгоритмы с использованием технологии структурного программирования; • отлаживать и тестировать программы. Изучение данной дисциплины базируется на знании студентами основ математики, информатики и основ алгоритмизации в пределах программы средней школы, умении применять математический аппарат при выборе метода решения задачи. Для освоения учебной дисциплины, студенты должны владеть школьными знаниями, получаемыми в процессе изучения указанных выше курсов. Этот курс лежит в основе всего программирования. Можно сказать, что это фундамент, на котором будет строиться все дальнейшее обучение программированию. Мы будем решать задачи, постепенно переходя от простых к более сложным. В конечном итоге вы научитесь решать задачи обработки динамических списков, т.е. работать на хорошем базовом уровне.
Программа с использованием подпрограммы для вычисления одномерного массива, содержащего заданное число наименьших элементов среди элементов квадратной целочисленной матрицы, расположенных ниже главной диагонали
Loading...
来自 国立高等经济大学 的课程
Алгоритмизация вычислений (Algorithmic computation)
65 评分
从本节课中
Решение задач с использованием процедур и функций
Восьмая неделя посвящена решению задач с использованием процедур и функций. Вы знакомитесь с понятием рекурсии. Также рассматривается пример разработки программы с использованием нисходящего проектирования.
与讲师见面
Ерохина Елена АльфредовнаСтарший преподаватель
Департамент компьютерной инженерии МИЭМ Высшая Школа Экономики
[ЗВУК]
[ЗВУК] Напишем
программу с использованием подпрограммы,
которая решает задачу вычисления k наименьших элементов среди элементов
квадратной целочисленной матрицы, расположенных ниже главной диагонали.
В данном случае нам дана матрица, дана ее размерность и указано,
сколько элементов нам нужно найти.
Например, пусть у нас с вами количество элементов равно 3, а матрица — 4 x 4.
Для наглядности главная диагональ выделена цветом.
Мы рассматриваем только элементы, расположенные ниже этой диагонали.
Алгоритм чем-то будет напоминать вычисление минимального или максимального
элемента в случае, когда у нас имеются дополнительные условия.
Мы с вами возьмем массив B, количество элементов которого равно k,
и вначале в каждую ячейку этого массива положим
maxint — константу, максимальное возможное значение для данных целого типа.
И теперь мы с вами будем последовательно рассматривать элементы матрицы,
расположенные ниже главной диагонали.
Первое значение у нас равно 0, и мы видим, что оно меньше,
чем максимальное значение в нашем массиве B — на первом шаге это первый элемент.
Тогда мы заменим этот первый элемент, максимальное значение в нашем массиве,
на текущий элемент матрицы.
Далее продолжим рассматривать элементы матрицы,
расположенные ниже главной диагонали.
Теперь у нас максимальное значение в массиве B находится на втором месте,
и текущий элемент матрицы у нас равен 2, и это меньше, чем maxint.
Заменим наш maxint, расположенный на втором месте, на двойку.
В этом массиве максимальное значение снова равно maxint,
но оно теперь расположено на третьем месте.
Наш элемент матрицы равен 3, и это меньше, чем maxint.
Заменяем maxint на 3.
Теперь в нашем массиве B расположены только элементы матрицы,
самый большой из них равен 3.
Очередной элемент матрицы у нас равен 1.
Это меньше, чем 3, и тогда мы заменяем 3 на 1.
Далее у нас элемент, равный 2, и максимальное значение
также у нас равно 2, значит, мы ничего заменять не станем.
Далее у нас элемент, равный 5, он также больше, чем 2,
следовательно, здесь замены также не произойдет.
И теперь мы с вами будем писать программу, которая будет решать данную задачу.
Мы будем использовать подпрограмму для вычислений, и давайте придумаем,
какая подпрограмма здесь уместна: процедура или функция?
Ну разумеется, поскольку у нас с вами на выходе много значений,
у нас есть массив, то уместно сделать процедуру.
Мы должны передать в нашу процедуру матрицу, размерность матрицы,
а также длину нашего массива B и получить на выходе элементы этого массива.
Тут, конечно, возникает законный вопрос.
Если у нас есть матрица размером n x n, то какое максимальное k мы можем задать?
То есть сколько максимально элементов мы можем найти для матрицы заданного размера.
Давайте подсчитаем.
Общее количество элементов в матрице — это n².
Мы с вами не рассматриваем элементы главной диагонали,
значит, у нас остается n² − n элементов.
И из этих элементов мы рассматриваем ровно половину.
То есть мы можем с вами рассмотреть не более чем n²
− n и все это деленное пополам элементов.
Теперь давайте посмотрим, как будет выглядеть наша программа.
Константа lmax — это максимальное количество строк и столбцов матрицы.
Мы с вами задаем тип для матрицы, как массив из целых чисел,
и нумерация столбцов и строк — от 1 до lmax включительно.
Тип для массива у нас с вами объявляет массив,
максимальная длина которого как раз равна n² − n пополам.
Теперь объявляю глобальные переменные.
Это у меня матрица A, массив B,
n и k — количество строк и столбцов в матрице и размерность массива.
Далее я записываю процедуру для ввода матрицы.
В принципе, она нам знакома, но никогда не вредно напомнить.
Результатами выполнения этой процедуры являются количество строк и
столбцов и сама матрица.
i и j — это локальные переменные.
Далее я ввожу n, проверяя, что оно в границах от 1 до lmax включительно.
После этого я ввожу элементы матрицы,
то есть устраиваю цикл по строкам, а внутри него — цикл по столбцам,
и последовательно читаю элементы матрицы, подсказывая пользователю,
какой именно номер строки и номер столбца сейчас рассматривается.
И затем наша процедура завершается.
Теперь рассмотрим процедуру вычисления нового массива.
Здесь у нас a является параметром-переменной в целях экономии
памяти, несмотря на то, что матрица от наших действий не будет меняться.
Далее у меня есть массив B, он является выходным параметром,
значит, это должен быть обязательно параметр-переменная,
n и k — параметры-значения, потому что они не меняются в процессе наших вычислений.
Далее объявляются локальные переменные.
Это i, j, номер максимального элемента в массиве и еще переменная L.
Посмотрим, как будут происходить наши действия.
Вначале мы с вами должны инициализировать все элементы массива B величиной maxint.
Это производится в отдельном цикле.
Далее мы должны искать на каждом шаге максимальный элемент.
Вначале номер максимума равен 1, и для обращения к
максимальному элементу нашего массива нам достаточно знать его номер,
то есть отдельную переменную для максимума можно не заводить.
Далее мы должны рассмотреть элементы матрицы,
расположенные ниже главной диагонали.
Строки у нас будут от второй до последней,
в каждой строке мы будем рассматривать столбцы от первого до (i − 1)-го,
то есть только те, которые расположены ниже главной диагонали.
Далее мы с вами должны сравнить значение текущего элемента
матрицы и значение максимального элемента массива.
Если текущий элемент матрицы меньше, чем максимальный элемент массива,
то мы проделываем следующие действия.
Действий у нас несколько, поэтому используем составной оператор.
Мы, во-первых, b[nmax] присваиваем текущий элемент матрицы,
то есть заменяем максимальный элемент массива на очередной элемент матрицы.
И теперь мы с вами снова должны найти,
какой элемент является максимальным в нашем массиве.
Обратите внимание,
здесь сразу начинается цикл for, который будет искать этот элемент.
Как вы думаете, а почему мы не инициализируем nmax перед этим циклом?
Здесь мы можем обойтись без этого,
потому что nmax сохраняет некоторое значение от предыдущего шага цикла,
и мы можем сравнивать на первом шаге элемент матрицы с этим элементом.
Цикл наш идет for L от 1 до k, то есть по всем номерам элементов массива B.
Мы сравниваем b[L] с b максимальным, и если оно больше,
то b[L] становится максимумом.
Обращаю ваше внимание, что поиск максимума у нас идет только тогда,
когда мы заменяли элемент массива на элемент матрицы.
Далее у нас наша процедура заканчивается, и процедуру вывода массива мы
с вами рассматривали в предыдущей задаче, поэтому здесь мы ее приводить не будем.
Далее у нас должна быть главная функция.
Мы сначала выводим сообщение о том, что у нас матрица A,
затем вызываем процедуру ввода матрицы, затем мы запрашиваем у пользователя,
сколько минимальных элементов мы должны найти, при этом мы проверяем, что это
значение k не превышает максимально возможного числа для данного n.
И после этого мы вызываем процедуру count_array,
параметры у нее — матрица, массив, количество строк и
столбцов в матрице и длина массива, и затем мы выводим сообщение о том,
что мы получили минимумы и вызываем процедуру print_array,
которая выведет на экран k элементов массива B,
Завершается наша программа end'ом с точкой.
Рассмотрим программу,
которая вычисляет заданное количество минимальных элементов среди элементов,
расположенных ниже главной диагонали квадратной целочисленной матрицы.
Здесь у нас также используются процедуры и функции.
Процедура ввода матрицы у нас с
вами вводит значения всех элементов матрицы, а также размер.
Матрица в данном случае квадратная,
то есть количество строк равно числу столбцов.
Процедура count_array, собственно, решает задачу.
Напомню, что здесь делается.
Сначала каждому элементу массива B присваивается значение,
равное maxint, то есть самое большое целое число.
Вначале номер максимального элемента равен 1.
Дальше мы последовательно перебираем все элементы,
которые расположены ниже главной диагонали нашей матрицы,
и сравниваем текущий элемент матрицы и максимальный элемент массива.
Если текущий элемент матрицы окажется меньше, чем максимальный элемент массива,
то тогда мы заменяем элемент массива на этом месте элементом матрицы,
и снова ищем максимальный элемент в одномерном массиве.
Обращаю ваше внимание, что поиск максимального элемента происходит только в
том случае, когда мы меняли какой-нибудь элемент массива B.
И у этого алгоритма есть еще одна интересная особенность.
Начальное значение nmax не присваивается перед началом цикла for, потому что у этой
переменной уже было некоторое значение, сохранившееся с предыдущего шага.
Мы используем его в качестве начального значения.
Дальше — процедура print_array, которая выводит элементы массива на экран,
и вот наша главная программа.
Здесь у нас сначала вводится матрица A при помощи соответствующей процедуры,
далее вводится количество элементов одномерного массива, причем проверяется,
что оно положительное и не превышает n² − n, деленного пополам,
потому что большее количество элементов для данной матрицы посчитать нельзя.
Дальше вызывается процедура count_array, и выводятся значения минимумов.
Давайте запустим нашу программу и попробуем задать в качестве
исходных данных ту матрицу, которую мы рассматривали в качестве примера.
У нашей матрицы было 4 строки и 4 столбца,
и дальше мы вводим матрицу поэлементно: сначала первый элемент первой строки,
потом второй и так далее.
То есть 1, 2, 3, 5,
0, 4, 7,
−9, затем 2,
3, 4 и 1, и последняя строка: 1,
2, 5 и 3.
Далее мы вводим количество элементов.
Мы с вами в примере искали 3 элемента, и вот они перед нами, наши минимумы.
Обращаю ваше внимание, что если, например,
для матрицы 3 x 3,
введу элементы произвольно,
задать количество отрицательное,
будет повторный ввод, превышающее максимальное заданное количество.
Также будет повторный ввод.
Ну и если я задам допустимое значение,
то тогда получу значения двух минимальных элементов.
То есть здесь исходные данные проверяются на допустимость,
и существование результата не проверяется,
поскольку при правильном значении k результат будет получен в любом случае.
Мы проверили работу нашей программы, и она работает правильно.
[ЗВУК]
[ЗВУК]
