Курс «Алгоритмизация вычислений» будет вам интересен и просто необходим, если вы хотели бы изучить программирование с нуля и выйти на хороший базовый уровень, научиться составлять, понимать и анализировать алгоритмы. В результате изучения курса вы сможете: • записывать математическую постановку задачи; • применять стандартные алгоритмы для решения задач; • оценивать оптимальность алгоритмов и выбирать алгоритм, дающий лучшее решение задачи; • проверять правильность алгоритма методом трассировки; • кодировать алгоритмы с использованием технологии структурного программирования; • отлаживать и тестировать программы. Изучение данной дисциплины базируется на знании студентами основ математики, информатики и основ алгоритмизации в пределах программы средней школы, умении применять математический аппарат при выборе метода решения задачи. Для освоения учебной дисциплины, студенты должны владеть школьными знаниями, получаемыми в процессе изучения указанных выше курсов. Этот курс лежит в основе всего программирования. Можно сказать, что это фундамент, на котором будет строиться все дальнейшее обучение программированию. Мы будем решать задачи, постепенно переходя от простых к более сложным. В конечном итоге вы научитесь решать задачи обработки динамических списков, т.е. работать на хорошем базовом уровне.
Диагонали в прямоугольной матрице
Loading...
Из курса от партнера National Research University Higher School of Economics
Алгоритмизация вычислений (Algorithmic computation)
67 оценки
National Research University Higher School of Economics
67 оценки
Из урока
Алгоритмы сортировки. Обработка матриц
Пятая неделя посвящена изучению алгоритмов сортировки массив. Рассматриваются метод "установки" и метод "пузырька". Затем изучаются алгоритмы обработки матриц (двумерных массивов).
Познакомьтесь с преподавателями
Ерохина Елена АльфредовнаСтарший преподаватель
Департамент компьютерной инженерии МИЭМ Высшая Школа Экономики
[ЗВУК]
[ЗВУК] В
квадратной матрице, как мы с вами уже изучали,
существуют две диагонали: главная и побочная.
Если количество строк не равно числу столбцов,
то в этой матрице также существуют две диагонали.
Рассмотрим следующую задачу: мы должны вычислить сумму четных элементов,
которые расположены на побочной диагонали матрицы.
Существует два случая.
В первом случае у нас больше столбцов, чем строк, а во втором случае — наоборот.
Мы с вами должны устроить цикл, который перебирает все нужные нам строки матрицы.
В первом случае, когда у нас больше столбцов,
чем строк, то есть у нас с вами m больше n, мы должны устроить цикл,
который будет перебирать строки от первой до n-ной, то есть до количества строк.
Во втором случае у нас, наоборот, m меньше или равно n, то есть меньше столбцов,
чем строк, и тогда нам нужен цикл от i, равного 1, до m.
Случай квадратной матрицы у нас включен во второй вариант.
Понятно, что можно отдельно записать циклы для первого и второго случая.
Но нам бы хотелось получить более общий вариант,
то есть когда у нас одинаково считается наша сумма и в том и в другом случае.
Мы видим, что количество шагов цикла, который будет перебирать строки,
у нас с вами равно минимальному из количества строк и числа столбцов.
Введем переменную k, которая будет минимумом из n и m,
и будем устраивать цикл от i, равного 1, до k в обоих случаях.
И для элемента побочной диагонали у нас с вами используется формула A[i,
(m + 1 − i)].
Это легко проверить на примере первого случая.
Далее рассмотрим постановку задачи.
Нам даны исходные данные — это количество строк и столбцов и элементы самой матрицы.
Все эти данные имеют целый тип.
А почему, собственно говоря, они имеют целый тип?
Ведь в условии задачи этого же не было сказано.
Дело в том, что у нас с вами в условии задачи сказано,
что нам нужны четные элементы.
А четность у нас определена только для целого типа.
Следовательно, наша матрица будет целочисленной.
Результатом является наша сумма или сообщение о том,
что у нас нет четных элементов, которые расположены на этой диагонали.
Ограничения касаются размерности матрицы,
то есть числа строк и количества столбцов: они должны быть натуральными числами
и не превышать соответствующих максимальных размеров.
В данном случае эти размеры для числа строк и столбцов одинаковые,
и эта константа будет называться lmax.
Далее рассмотрим связь.
Мы должны определить минимальное из значений n и m и присвоить эту
величину переменной k.
Дальше мы считаем сумму элементов.
Наш цикл будет проходить от i, равного 1, до k,
и мы рассматриваем элемент, который расположен на побочной диагонали,
причем не каждый элемент, а только четный, то есть кратный двум.
Напоминаю, что три точки по вертикали означают понятие кратности.
Теперь рассмотрим собственно алгоритм.
Вначале мы должны ввести исходные данные, а затем определить,
до какого количества, количества строк или числа столбцов, будет цикл.
Если у нас n меньше m, то k будет равно n, поскольку
оно минимальное из этих двух значений, а в противном случае k будет присвоено m.
И теперь мы с вами должны произвести инициализацию тех переменных,
то есть присвоить начальные значения тем переменным,
которые у нас будут считать наши результаты.
И тут возникает законный вопрос.
Наша переменная сумма, она вначале равна 0.
То есть мы ее должны инициализировать нулем.
Представим себе, что наш цикл уже закончился.
Означает ли, что сумма осталась равной 0 то,
что у нас не было четных элементов на этой диагонали?
Ну конечно, нет, потому что ведь бывают еще и отрицательные числа.
То есть если у нас элементы были равны, допустим, 2 и −2,
то в сумме они дают 0, и, следовательно,
по конечному значению суммы мы не можем определить наличие наших четных элементов.
Поэтому мы производим следующие инициализации: мы берем сумму,
равную 0, и булевскую переменную flag, которая вначале имеет значение «ложь».
То есть у нас с вами сначала таких элементов нет.
Дальше мы рассматриваем все элементы от 1-го до k-го,
i у нас — это индекс строки, и проверяем наше условие.
Если наше число — четное,
то тогда мы прибавляем его к сумме и меняем flag на «истину».
Затем закрываем цикл, и дальше мы должны проверить, есть ли наш результат.
Это проверяется по переменной flag.
Если не flag, то есть flag остался равным false,
то тогда мы выводим сообщение о том, что у нас нет четных элементов.
В противном случае мы выводим полученное значение суммы,
и наш алгоритм на этом завершается.
Рассмотрим программу,
которая работает с неквадратной матрицей и определяет в ней побочную диагональ.
Напомню, что нашей задачей было найти сумму четных элементов,
которые расположены на этой диагонали.
Ввод матрицы и вывод матрицы совершенно аналогичен предыдущим заданиям,
но в данном случае матрица у нас неквадратная, поэтому мы вводим и n, и m.
Далее, в соответствии с нашим алгоритмом,
мы определяем до какого значения — до n или до m — будет идти наш цикл.
Цикл будет идти от 1 до минимального из значений n и m
— эта переменная называется k.
Затем мы будем подсчитывать сумму.
Для проверки существования суммы нам необходим флаг логический,
потому что то, что сумма в результате выполнения нашего цикла осталась
равной 0 не означает, что ее нет.
Потому что четные числа могут быть как положительными, так и отрицательными.
+2, если прибавить −2, сумма будет равна 0, но четные числа были.
И мы проверяем, выбирая наши элементы, расположенные на побочной диагонали,
выбираем из них только четные и каждый из этих элементов прибавляем к сумме и,
найдя нужный нам четный элемент, меняем flag на «истину».
По завершении цикла мы проверяем, есть ли четные числа.
При ложном флаге их нет, при истинном — они есть.
Запустим нашу программу и введем исходные данные.
Я попробую ввести матрицу, у которой число строк больше,
чем число столбцов, и наоборот.
Например, рассмотрю матрицу размера 3 на 5,
то есть 3 строки по 5 столбцов, и введу элементы.
[ЗВУК] Первую строку,
вторую и третью.
[ЗВУК] На
экране мы видим введенную матрицу,
она у нас выведена построчно,
и сумма элементов, расположенных на побочной диагонали,
тех, которые являются четными — это 10.
У нас есть элемент, равный 6, и есть элемент, равный 4.
Пятерка нечетная, поэтому она не подходит под наше условие.
Теперь давайте попробуем запустить программу заново и
рассмотреть матрицу 5 на 3.
Снова ввожу количество строк и столбцов,
затем ввожу элементы матрицы.
[ЗВУК]
[ЗВУК]
[ЗВУК] И в данном случае наша сумма равна 6,
поскольку на побочной диагонали у нас только один четный элемент.
Теперь попробуем придумать матрицу, в которой не будет результата.
Для этого нам нужно,
чтобы наша побочная диагональ не содержала ни одного четного элемента.
Например, возьму квадратную матрицу размера 2 на 2.
И введу элементы построчно.
В данном случае результатом будет сообщение о том,
что в нашей матрице нет четных элементов.
Обращаю ваше внимание, что в данном случае наша матрица
имела целый тип, и, следовательно,
при выводе мы видим целые числа, у них нет дробной части,
поэтому они отображаются просто в виде обычного целого числа.
Через равные промежутки, поскольку при выводе нашей
матрицы мы используем формат 5, то есть каждое число при выводе
занимает 5 позиций.
[ЗВУК]
[ЗВУК]
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
