Курс «Алгоритмизация вычислений» будет вам интересен и просто необходим, если вы хотели бы изучить программирование с нуля и выйти на хороший базовый уровень, научиться составлять, понимать и анализировать алгоритмы. В результате изучения курса вы сможете: • записывать математическую постановку задачи; • применять стандартные алгоритмы для решения задач; • оценивать оптимальность алгоритмов и выбирать алгоритм, дающий лучшее решение задачи; • проверять правильность алгоритма методом трассировки; • кодировать алгоритмы с использованием технологии структурного программирования; • отлаживать и тестировать программы. Изучение данной дисциплины базируется на знании студентами основ математики, информатики и основ алгоритмизации в пределах программы средней школы, умении применять математический аппарат при выборе метода решения задачи. Для освоения учебной дисциплины, студенты должны владеть школьными знаниями, получаемыми в процессе изучения указанных выше курсов. Этот курс лежит в основе всего программирования. Можно сказать, что это фундамент, на котором будет строиться все дальнейшее обучение программированию. Мы будем решать задачи, постепенно переходя от простых к более сложным. В конечном итоге вы научитесь решать задачи обработки динамических списков, т.е. работать на хорошем базовом уровне.
Использование методов сортировки при обработке матриц
Loading...
來自 National Research University Higher School of Economics 的課程
Алгоритмизация вычислений (Algorithmic computation)
67 個評分
National Research University Higher School of Economics
67 個評分
從本節課中
Алгоритмы сортировки. Обработка матриц
Пятая неделя посвящена изучению алгоритмов сортировки массив. Рассматриваются метод "установки" и метод "пузырька". Затем изучаются алгоритмы обработки матриц (двумерных массивов).
與講師見面
Ерохина Елена АльфредовнаСтарший преподаватель
Департамент компьютерной инженерии МИЭМ Высшая Школа Экономики
[МУЗЫКА]
[МУЗЫКА] Рассмотрим,
как можно использовать методы сортировки для обработки матриц.
Условие нашей задачи таково: нам дана целочисленная матрица a, не квадратная
и нам нужно упорядочить элементы каждой строки по возрастанию, а затем
в полученной матрице нужно расположить все строки по убыванию сумм элементов.
Для наглядности, массив сумм элементов строк у нас также изображен отдельно.
Например, у нас есть вот такая исходная матрица.
Первая сортировка расположит элементы в каждой строке по возрастанию,
то есть самым первым будет самый маленький элемент, а дальше они будут возрастать.
Для первой строки мы получим последовательность −3 0 1 1 и 9.
Затем, если мы возьмем вторую строку,
то результатом будет следующая последовательность: −4 0 2 3 и 6.
И для последней строки мы получим вот такой порядок элементов.
Теперь мы для удобства проведения второй сортировки посчитаем,
какова сумма элементов каждой строки.
Для первой строки эта сумма равна 8.
Для второй строки мы получим значение, равное 7.
И для последней строки наша сумма будет равна 17.
Теперь нам нужно расположить все наши строки по убыванию сумм элементов.
Иными словами говоря, первая строка,
которая будет в полученной матрице, должна иметь максимальную сумму элементов.
Мы будем одновременно переставлять элемент массива сумм и соответствующую строку.
Итак, первая строка будет у нас иметь после второй сортировки максимальную
сумму элементов, а дальше остальные расположатся в порядке убывания сумм.
То есть дальше будет у нас строка, которая была первой, а затем строка,
сумма элементов которой равна 7.
Мы с вами рассмотрим программу, которая будет решать соответствующую задачу.
При этом в качестве первого метода сортировки я выберу установку,
а вторая сортировка у нас будет производиться методом «пузырька».
Итак, программа.
Первым делом я объявляю две константы: максимальное
количество строк и число столбцов.
Затем для матрицы я задаю тип и также я задаю тип для массива сумм.
Теперь объявляю переменные.
Матрица у меня – a, массив сумм называется sum,
далее у меня есть счетчики, при помощи которых я буду организовывать циклы,
а также количество строк и столбцов матрицы, и кроме того,
b — это переменная, которая будет использоваться для перестановки.
Эти все данные имеют целый тип.
И кроме того, поскольку я собираюсь использовать метод «пузырька»,
мне потребуется булевская переменная flag, которая будет показывать,
закончилась ли уже наша сортировка.
Первым делом я должна ввести исходные данные.
Для матрицы я сначала ввожу количество строк и столбцов и проверяю,
что эти данные верные, корректные, то есть они находятся в границе
от 1 до nmax – число строк и от 1 до mmax – количество столбцов, соответственно.
Теперь мне нужно прочитать элементы матрицы.
Я устраиваю два цикла – по строкам и по столбцам,
и читаю их построчно.
Далее я должна сделать сортировку
строк матрицы по возрастанию элементов методом установки.
Здесь у меня получается три цикла.
Первый цикл по i от 1 до n будет выбирать номер строки, которую я сейчас сортирую.
И внутри этого цикла еще два цикла, которые у нас реализуют метод установки.
Первый цикл по j от 1 до n − 1 выбирает,
какой элемент я сейчас буду сравнивать с последующими, а второй выбирает,
с каким элементом я буду сравнивать элемент из j-того столбца.
И дальше у меня сортировка по возрастанию.
Если у меня в одной и той же строке на j-том месте стоит больший элемент,
чем на k-том, то есть больший элемент стоит раньше,
то я должна поменять эти значения местами через третью переменную.
По кругу этот алгоритм мы с вами уже хорошо знаем.
Затем я закрываю свое условие, поскольку у меня составной
оператор был только в условии, то при этом закроются и все наши циклы.
Для того чтобы было нагляднее, я выведу промежуточный результат,
то есть выведу на экран матрицу, которая получится у меня после первой сортировки.
Здесь у меня два цикла по строкам и по столбцам, я вывожу матрицу построчно.
Выбрав строку, я вывожу элементы всех столбцов этой строки и
затем перехожу к следующей строке.
Теперь рассмотрим вторую сортировку.
Для того чтобы удобнее было производить вторую сортировку,
я вычислю сумму элементов каждой строки и помещу эти значения в отдельный массив.
Потому что таким образом я экономлю время,
которое затрачивается у меня на выполнение нашего алгоритма.
Я не каждый раз считаю сумму двух соседних строк заново,
а просто завожу дополнительный массив.
Это требует некоторого количества дополнительной памяти,
но ускоряет выполнение нашего алгоритма.
И теперь я должна для каждой строки посчитать сумму элементов.
Я первый цикл должна устроить по номерам строк: for i от 1 до n.
Теперь я на каждом шаге этого цикла должна посчитать суммы элементов текущей строки.
Текущей строке, i-той,
у меня будет соответствовать элемент массива sum с таким же индексом.
sum [i] я присваиваю начальное значение 0.
Теперь я перебираю все столбцы, которые у меня располагаются в этой строке,
и на каждом шаге я к текущему значению sum [i] прибавляю элемент матрицы.
И затем закрываю составной оператор, при этом у меня закрывается первый цикл for.
Теперь я должна продолжать действие,
то есть должна устроить вторую сортировку.
Для второй сортировки мне нужно будет использовать и массив sum и саму матрицу.
При этом, если я переставляю элементы массива sum,
то у меня соответствующие строки матрицы также меняются местами.
Мы можем даже на секунду забыть о том, что у нас была матрица и начать с того,
что устроить сортировку массива sum по убыванию методом «пузырька».
Итак, в методе «пузырька» у нас с вами были два цикла.
Первый цикл был с постусловием, и он проверял,
закончились ли уже все перестановки.
И внутри был цикл, который сравнивал пары соседних элементов.
Первый цикл у нас уже открыт, repeat, flag присваивается значение true,
и дальше я в массиве sum перебираю все номера элементов от 1 до предпоследнего.
Напомню, что до предпоследнего, а не до последнего,
потому что мы сравниваем пару соседних элементов, текущий и следующий за ним.
Чтобы в этом месте у нас не было выхода за границу массива нам нужно сделать
цикл не до конца массива, а до предпоследнего элемента.
Теперь я сравниваю два соседних элемента массива sum.
Если у меня на i-том месте стоит элемент меньший, чем на следующем,
то есть эта пара элементов расположена неправильно, то я должна поменять
эти элементы местами через третью переменную,
а затем еще запомнить, что на данном шаге перестановка была,
то есть поменять значение переменной flag.
Теперь я вспомню, что у меня есть еще и матрица.
Если я поменяла местами два элемента массива sum,
то и две соответствующих соседних строки должны также поменяться местами.
Это нужно сделать поэлементно.
То есть я возьму цикл по столбцам и на каждом шаге я поменяю местами
через третью переменную – переменную я использую ту же,
что в первый раз для обмена – я поменяю местами элементы
текущей строки и строки, следующей за ней.
Затем у меня закрывается условие, которое показывало,
что нужна перестановка, и я буду продолжать свои действия до тех пор,
пока у меня flag не сохранит начальное значение «истина».
То есть до тех пор, пока у меня есть хотя бы одна перестановка.
Далее я должна вывести матрицу после второй сортировки.
С вашего позволения я не буду повторять этот фрагмент,
потому что два цикла, которые я здесь использую,
совершенно аналогичны выводу матрицы после первой сортировки.
Поэтому я ограничилась комментарием «см.
выше».
Можно Посмотреть на предыдущих слайдах, как выглядел наш вывод.
И на этом наша программа заканчивается end с точкой.
Рассмотрим программу, в которой происходит сортировка матрицы.
И сначала элементы каждой строки матрицы упорядочиваются по возрастанию.
А затем в полученной матрице все строки переставляются по убыванию сумм элементов.
В этой программе сначала
происходит ввод матрицы — действие совершенно обычное,
поэтому на этом мы подробно останавливаться не будем.
Далее, происходит первая сортировка.
Первая сортировка у нас — сортировка по возрастанию методом установки.
Затем выводятся элементы матрицы так,
как они будут расположены после первой сортировки.
Потом происходит
вычисление сумм элементов каждой строки.
И далее происходит сортировка массива сумм и одновременная
перестановка строк матрицы.
После чего
выводится матрица после второй сортировки.
Итак, запустим нашу программу.
[ЗВУК] И введем те исходные данные,
которые у нас с вами использовались при разборе условия этой задачи.
Наша матрица имела размер 3 на 5,
и я ввожу элементы матрицы построчно.
[ЗВУК]
[ЗВУК]
[ЗВУК] Матрица
после первой сортировки
выглядит именно так, как в нашем примере.
То есть каждая строка у нас упорядочена по возрастанию элементов.
При этом порядок строк остается таким же, как был у нас в исходной матрице.
Далее происходит вторая сортировка.
Здесь у нас в каждой строке порядок элементов не изменяется,
но зато меняются местами сами строки.
Первая строка имеет максимальную сумму элементов.
Во второй строке сумма элементов меньше, и в последней строке она самая маленькая.
Попробуем ввести какую-нибудь другую матрицу.
Снова запустим программу и рассмотрим матрицу,
ну например, 4 на 5.
Я ввожу элементы так, чтобы они не были изначально упорядочены.
[ЗВУК]
Первую строку.
Вторую строку.
Третью строку.
И последнюю, четвертую, строку.
[ЗВУК] Вначале
элементы каждой строки у нас упорядочились по возрастанию.
То есть самым маленьким элементом является элемент первого столбца,
и чем дальше к концу строки, тем элемент больше.
Все эти действия проделаны у нас для каждой из строк.
И затем у нас наши строки
переставлены так, чтобы их суммы убывали.
Первой становится строка, в которой сумма элементов самая большая,
а на последнем месте расположена строка, в которой сумма элементов самая маленькая.
То есть наш алгоритм сортировки и в том, и в другом случае
работает верно.
[МУЗЫКА]
[МУЗЫКА]
