Курс «Алгоритмизация вычислений» будет вам интересен и просто необходим, если вы хотели бы изучить программирование с нуля и выйти на хороший базовый уровень, научиться составлять, понимать и анализировать алгоритмы. В результате изучения курса вы сможете: • записывать математическую постановку задачи; • применять стандартные алгоритмы для решения задач; • оценивать оптимальность алгоритмов и выбирать алгоритм, дающий лучшее решение задачи; • проверять правильность алгоритма методом трассировки; • кодировать алгоритмы с использованием технологии структурного программирования; • отлаживать и тестировать программы. Изучение данной дисциплины базируется на знании студентами основ математики, информатики и основ алгоритмизации в пределах программы средней школы, умении применять математический аппарат при выборе метода решения задачи. Для освоения учебной дисциплины, студенты должны владеть школьными знаниями, получаемыми в процессе изучения указанных выше курсов. Этот курс лежит в основе всего программирования. Можно сказать, что это фундамент, на котором будет строиться все дальнейшее обучение программированию. Мы будем решать задачи, постепенно переходя от простых к более сложным. В конечном итоге вы научитесь решать задачи обработки динамических списков, т.е. работать на хорошем базовом уровне.
Определение индексов элементов матрицы, расположенных на, над и под главной и побочной диагональю
Loading...
En provenance du cours de Université nationale de recherche, École des hautes études en sciences économiques
Алгоритмизация вычислений (Algorithmic computation)
65 notes
Université nationale de recherche, École des hautes études en sciences économiques
65 notes
À partir de la leçon
Алгоритмы сортировки. Обработка матриц
Пятая неделя посвящена изучению алгоритмов сортировки массив. Рассматриваются метод "установки" и метод "пузырька". Затем изучаются алгоритмы обработки матриц (двумерных массивов).
Rencontrer les enseignants
Ерохина Елена АльфредовнаСтарший преподаватель
Департамент компьютерной инженерии МИЭМ Высшая Школа Экономики
[МУЗЫКА]
[МУЗЫКА] Перейдем
к изучению алгоритмов обработки матриц.
Научимся определять индексы элементов матрицы, которые расположены на,
над и под главной и побочной диагональю.
Главная диагональ – на рисунке она закрашена серым
цветом – проходит из верхнего левого угла матрицы в нижний правый.
На этой диагонали все индексы элементов обладают некоторым свойством.
Давайте, его обнаружим.
На этой диагонали располагаются элементы с индексом 1-1,
2-2, 3-3, ну и последний элемент имеет индекс n-n.
Иными словами говоря, номер строки и номер столбца одинаковые.
И для того чтобы перебрать все элементы матрицы,
расположенные на главной диагонали, нам будет достаточно ровно одного цикла.
Мы будем выбирать номер строки,
а номер столбца будет определяться равным номеру строки.
То есть на каждом шаге цикла мы будем выводить a[i,i] Теперь
рассмотрим элементы матрицы, расположенные над главной диагональю.
На рисунке они закрашены красным цветом.
Мы видим, что здесь мы должны перебирать строки от первой до предпоследней,
а в столбце должны рассматриваться только те элементы,
которые расположены выше главной диагонали.
То есть номер столбца у нас будет начинаться сразу за тем столбцом,
где был элемент главной диагонали.
То есть первый цикл будет от i = 1 до n − 1, а второй
цикл будет от j = i + 1 и до конечного последнего столбца.
И выводиться будет элемент a[i,j].
Теперь рассмотрим элементы, которые расположены под диагональю.
На рисунке они изображены зеленым цветом.
Здесь мы должны рассматривать все строки от второй до последней,
а столбцы мы начинаем рассматривать с первого и заканчиваем рассмотрение,
не достигнув на единицу элемента главной диагонали.
То есть первый цикл будет от i = 2 и до конца, до n,
а второй цикл будет от j = 1 до i − 1.
И мы выводим элемент a[i,j].
Теперь перейдем к рассмотрению побочной диагонали.
Для квадратной матрицы, которая изображена на нашем рисунке,
здесь диагональ снова выделена серым цветом,
мы тоже можем установить свойства, которым обладают элементы этой диагонали.
Для того чтобы его установить, опять переберем несколько таких элементов.
Элемент первой строки находится в последнем, в n столбце,
элемент второй строки находится в предпоследнем n − 1 столбце и так далее.
Если мы вычислим сумму индексов строки и столбца,
то у нас получается все время постоянная сумма для этой диагонали, она равна n + 1.
Отсюда не сложно выразить j.
Для побочной диагонали у нас получится, что j вычисляется по формуле n + 1 − i.
И теперь снова рассмотрим циклы, которые будут перебирать элементы,
расположенные на, над и под этой диагональю.
На диагонали цикл ровно один.
Мы выбираем номер строки, а номер столбца вычисляем по формуле,
которую мы с вами только что вывели, то есть будет a[i, n + 1 − i].
Теперь рассмотрим элементы, расположенные над диагональю.
Они помечены красным цветом.
Какие строки мы рассматриваем?
От первой до предпоследней.
А вот что касается номера столбца, то мы должны остановить цикл по
столбцам на единицу раньше, чем у нас будет элемент побочной диагонали.
Если мы из нашей формулы элемента побочной диагонали вычтем 1,
то получим n − i, то есть первый цикл у нас будет
от 1 до n − 1, а второй – от 1 до n − i.
И мы будем выводить очередной элемент a[i,j].
Теперь рассмотрим элементы, расположенные под диагональю.
На нашем рисунке они выделены зеленым цветом.
Мы рассматриваем строки от второй и до последней.
И цикл по столбцам должен доходить до последнего столбца,
а что касается его начала, то он должен начаться на единицу позже,
чем был элемент побочной диагонали.
То есть к нашей формуле мы прибавляем 1 и получаем n + 2 − i.
Первый цикл – от 2 до n.
Второй цикл по столбцам – от n + 2 − i до n, и снова мы выводим a[i,j].
Таким образом, мы с вами научились точно определять индексы элементов,
которые расположены на, над и под главной и побочной диагональю.
То есть мы указываем точные границы циклов, которые переберут эти элементы.
Мы с вами рассмотрели, как определяются индексы элементов расположенных на,
над и под главной и побочной диагональю для квадратной матрицы.
Теперь давайте посмотрим,
как рассмотренный нами алгоритм реализуется в виде программы.
У нас с вами есть тип для
матрицы — это массив, состоящий из вещественных чисел.
В данном случае матрица у нас квадратная, поэтому при вводе данных мы
с вами указываем n, которое будет как числом строк, так и количеством столбцов.
Далее, аналогично предыдущему алгоритму,
мы с вами вводим элементы матрицы и при этом у нас и n, и m,
имеют одинаковые значения, то есть матрица квадратная,
цикл по строкам идет от 1 до n, и точно так же у нас идет цикл по столбцам.
Далее в виде программы закодированы те алгоритмы, которые у
нас с вами были изображены в коротком виде там, где были картинки с диагоналями.
Итак, здесь у нас с вами происходит сначала вывод матрицы,
чтобы было проще рассматривать наши результаты,
и затем мы начинаем с того, что рассматриваем главную диагональ.
На главной диагонали у нас с вами один цикл,
и перебираются номера строк от первой до n-й.
Выводится элемент a[i, i].
Далее мы переходим на следующую строчку и рассматриваем элементы,
расположенные выше главной диагонали.
Здесь строки у нас от первой до предпоследней,
а столбцы от следующего за текущей строкой до конца.
Под главной диагональю так же два цикла,
строки от второй до последней, а столбцы от первого до i − 1.
Далее то же самое мы проделываем для побочной диагонали.
Для элементов, расположенных на побочной диагонали, у нас один цикл,
индекс элемента побочной диагонали — это a[i, n − i + 1].
Затем над побочной диагональю мы используем два цикла,
по строкам от первой до предпоследней и по столбца от первого до n − i, то
есть останавливаем цикл на единицу раньше, чем будет достигнута побочная диагональ.
И наконец, под побочной диагональю также два цикла.
Строки от второй до последней, а столбцы начинаются от элемента,
расположенного сразу за элементом побочной диагонали, и доходят до конца.
Наши элементы, расположенные в определенных местах,
будут выводиться следующим образом.
Будет выводиться первая строка, в которой
есть такие элементы, а затем будет происходить переход к следующей строке.
Запустим нашу программу и возьмем матрицу 4 x 4.
Я ввожу, напоминаю, только количество строк,
количество столбцов равно количеству строк.
Теперь я ввожу элементы матрицы… [БЕЗ
ЗВУКА] [БЕЗ
ЗВУКА] Я ввожу их
построчно… [БЕЗ
ЗВУКА] И далее
у меня получается следующий результат.
Чтобы результат был лучше виден, мы можем увеличить размеры
окна вывода и теперь посмотрим, что у нас получилось.
Вначале выводится введенная матрица…
Поскольку элементы были вещественными,
то выводятся они с показом дробной части.
И формат у нас был по-прежнему 10-5, то есть вот так вот выглядит у нас матрица.
Она выведена построчно и между элементами у нас одинаковые промежутки.
Далее выведены элементы, расположенные на главной диагонали:
0 3 5 и 7.
Затем мы рассматриваем элементы, расположенные над главной диагональю,
они выводятся построчно: −2 3 −7.
Сначала первая строка, затем вторая строка 0 и −1,
и наконец, последняя строка 6.
Далее мы рассматриваем элементы под главной диагональю.
Они также выводятся построчно: это 4 3
еще одна 4 0 −4 −5.
Далее мы переходим к побочной диагонали.
Побочная диагональ у нас идет перпендикулярно главной,
то есть она начинается от правого верхнего угла и приходит в нижний левый.
Элементы на побочной диагонали — это −7 0 4 и еще один 0.
Далее мы рассматриваем элементы, расположенные над побочной
диагональю — это у нас 0 −2 и 3.
Кроме того, во второй строке – 4 и 3… 4 и
3… и еще одна 3.
Ну и также мы рассматриваем элементы, расположенные под побочной диагональю.
Таким образом, мы видим, что наши циклы работают совершенно корректно и,
указывая точные границы цикла, мы с вами можем получить любой из
перечисленных наборов элементов.
[МУЗЫКА]
[МУЗЫКА]
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
