Курс «Алгоритмизация вычислений» будет вам интересен и просто необходим, если вы хотели бы изучить программирование с нуля и выйти на хороший базовый уровень, научиться составлять, понимать и анализировать алгоритмы. В результате изучения курса вы сможете: • записывать математическую постановку задачи; • применять стандартные алгоритмы для решения задач; • оценивать оптимальность алгоритмов и выбирать алгоритм, дающий лучшее решение задачи; • проверять правильность алгоритма методом трассировки; • кодировать алгоритмы с использованием технологии структурного программирования; • отлаживать и тестировать программы. Изучение данной дисциплины базируется на знании студентами основ математики, информатики и основ алгоритмизации в пределах программы средней школы, умении применять математический аппарат при выборе метода решения задачи. Для освоения учебной дисциплины, студенты должны владеть школьными знаниями, получаемыми в процессе изучения указанных выше курсов. Этот курс лежит в основе всего программирования. Можно сказать, что это фундамент, на котором будет строиться все дальнейшее обучение программированию. Мы будем решать задачи, постепенно переходя от простых к более сложным. В конечном итоге вы научитесь решать задачи обработки динамических списков, т.е. работать на хорошем базовом уровне.
Формирование массива, содержащего все повторяющиеся элементы исходного массива. Проверка того, что элемент не повторяется в массиве
Loading...
En provenance du cours de National Research University Higher School of Economics
Алгоритмизация вычислений (Algorithmic computation)
67 notes
National Research University Higher School of Economics
67 notes
À partir de la leçon
Алгоритмы с досрочным выходом из цикла
Шестая неделя посвящена изучению алгоритмов с досрочным выходом из цикла. Досрочный выход подразумевает использование циклов с предусловием и с постусловием. Эти циклы могут завершаться раньше, чем будут просмотрены все элементы массива. Рассматриваются алгоритмы проверки присутствия, отсутствия и повторения.
Rencontrer les enseignants
Ерохина Елена АльфредовнаСтарший преподаватель
Департамент компьютерной инженерии МИЭМ Высшая Школа Экономики
[МУЗЫКА]
Продолжаем изучение
темы «Алгоритмы с досрочным выходом из цикла».
Рассмотрим следующую задачу.
Нам дан массив a, длина которого na и нам нужно сформировать массив b,
который состоит из повторяющихся элементов массива a.
Например, рассмотрим следующий массив.
Для того чтобы сформировать новый массив нам нужно понять, что значит,
что элемент повторяется в нашем массиве.
Мы с вами видим, что, например, 1 у нас в данном массиве повторяется 3 раза,
то есть существует три элемента равных 1, номера у которых разные.
То есть, если наш элемент повторяется в нашем массиве, то это значит, что
существует хотя бы один элемент на другом месте, равный текущему элементу массива.
То есть первый элемент массива a равный 1 попадет в новый массив b.
Затем рассматриваем 2.
Для 2 также есть повтор, поэтому,
элемент равный 2 также попадет в наш новый массив на следующее место.
Затем рассматриваем элемент равный 4.
Четверка не повторяется, она в этом массиве только одна,
поэтому мы не будем записывать ее в новый массив.
Далее рассмотрим вторую 1.
По условию задачи нам не сказано,
что каждый элемент нашего нового массива должен быть уникален,
то есть если у нас с вами элемент, равный 1, который расположен на четвертом месте,
является повторяющимся, то мы его тоже запишем в массив.
Далее мы запишем в массив следующий элемент, равный 2,
так как он тоже повторяется.
Тройка не попадет в массив, потому что этот элемент не является повторяющимся.
Второй тройки у нас в массиве исходном нет.
И затем последняя 1.
Мы с вами понимаем, что в данной задаче результат может как существовать,
если есть повторяющиеся элементы, так и быть не найденным,
то есть при выводе результата нам нужно предусмотреть два возможных случая.
Рассмотрим постановку задачи.
В пункте «Дано» перечисляем исходные данные, а дан нам массив и его длина.
В пункте «Результат» мы указываем все возможные варианты результата.
У нас, либо есть новый массив, либо результатом будет сообщение о том,
что массива b нет.
Ограничения на исходные данные касаются длины нашего массива a.
Она должна быть натуральным числом и не превышать максимально возможную длину.
И затем рассмотрим самый интересный пункт «Связь».
Мы с вами должны записать условие того, что элемент повторяется в массиве a.
Для каждого номера элемента массива i, в диапазоне от 1 до na,
такого, что существует j в том же диапазоне,
для которого i ≠ j, а элементы равны.
То есть номера у элементов разные, а сами элементы одинаковые.
Мы этот элемент будем записывать в новый массив,
то есть у нас будет существовать индекс k в диапазоне от 1 до nb, такой,
что элемент массива b на этом месте будет равен текущему элементу массива a.
И теперь запишем алгоритм для решения этой задачи.
Новый массив из повторяющихся элементов исходного массива.
Вначале введем исходные данные, и мы с вами собираемся формировать новый массив.
Новый массив у нас b, длина массива nb, вначале она равна 0,
потому что этого массива у нас еще нет.
Теперь рассматриваем последовательно все номера элементов в массиве a.
И для того чтобы определить, есть ли у нас повтор,
мы берем второй индекс j и будем его использовать в качестве номера элемента,
с которым мы сравниваем текущий элемент ai.
j вначале равно 1.
Теперь мы запишем цикл с досрочным выходом.
В заголовке этого цикла мы указываем три условия.
Первое условие: пока j меньше или равно na,
то есть мы при помощи индекса j не дошли до конца массива a, а второе
условие у нас состоит из двух отдельных условий, объединенных связкой «или».
Обратите внимание, что эти два условия находятся в скобках.
Потому что по приоритетам, по порядку выполнения операций,
«или» у нас выполняется после «и», а нам надо, чтобы наоборот —
сначала вычислилось значение двух выражений соединенных связкой «или»,
а потом к первому выражению и к результату в скобках была применена связка «и».
В скобках у нас записаны два условия.
Первое условие — то, что ai ≠ aj или i = j,
то есть элементы наши разные по значению, «или» элемент сравнивается сам с собой.
Если элемент равен сам себе, то в этом случае наш цикл будет продолжаться,
потому что нам надо найти элемент, который расположен на другом месте и равен ai.
Пока выполняются все эти условия, мы будем увеличивать счетчик j,
то есть переходить к следующему элементу массива.
Теперь, когда мы закрыли цикл, мы должны определить — найден ли элемент,
равный нашему ai?
Для этого мы можем вообразить себе,
при каком условии завершится наш предыдущий цикл.
Он завершится в одном из двух случаев: либо кончился наш массив,
то есть j у нас станет больше, чем na, кстати,
оно будет равно na + 1, потому что, как только оно превысит значение na,
так цикл сразу завершится, либо у нас нарушилось второе условие,
которое у нас состоит из двух условий заключенных в скобки.
Возьмем мысленно отрицание от этого условия.
Что мы получим?
У нас будет ai = aj и i ≠ j.
Это делается по закону де Моргана,
который мы с вами рассматривали на предыдущих занятиях.
То есть это условие того, что у нас найден элемент,
равный заданному, стоящий на другом месте, то есть повтор.
В этом случае мы еще не дошли до конца массива, то есть j у нас будет ≤ na.
Если наша j ≤ na, то наш элемент повторяется.
Тогда мы увеличиваем длину массива b на 1 и на
это место записываем текущий элемент массива a.
Закрываем наше условие и завершаем наш цикл.
Теперь нам нужно проанализировать существование результата.
Если длина нашего нового массива nb осталась равной 0,
то это значит, что у нас нового массива нет, и мы выводим сообщение об этом.
Затем мы с вами рассматриваем противоположный случай.
В этом случае массив у нас создан, и мы выводим последовательно все его элементы.
Завершаем наше условие и заканчиваем наш алгоритм.
Вот этот прием – проверка повторений – у нас с вами будет встречаться
довольно часто.
Давай посмотрим, какие особенности есть у алгоритмов,
которые включают фрагмент проверки повторений.
Во-первых, представим себе, что нам нужно проверить противоположное условие.
Мы сейчас проверяли, что наш элемент повторяется в массиве a,
а нам нужно, чтобы он, наоборот, там не повторялся.
В этом случае мы просто заменяем всего лишь одно условие —
мы заменяем условие, которое рассматривалось по завершении цикла.
У нас было условие повторения, которое записывалось j ≤ na, а если j > na,
то это значит, что элемент не повторяется, цикл пока завершился,
когда мы просмотрели весь массив и не нашли другого такого же элемента,
как наше текущее ai, но расположенного на другом месте.
И второе, если мы с вами проверяем условие того, что элемент наш повторялся.
Иногда студенты делают попытку изменить условие, которое проверяет,
повторялся ли элемент, на условие ai = aj,
то есть вместо j ≤ na, написать ai = aj — вот это ошибка.
Почему это является ошибкой?
Вспомним, как работал наш цикл «пока».
Он завершался, либо при j ≤ na, когда элемент повторялся,
тогда мы рассматриваем элемент, который мы записывали в массив.
Пока мы не дошли до конца массива, до элемента с номером na,
мы рассматриваем те числа, которые мы при вводе поместили в наш массив.
А вот если у нас элемент не повторялся, то у нас j > na на 1.
В этом случае на этом месте,
которое расположено на 1 дальше, чем последний элемент массива,
находится случайное число, неопределенное.
Правда, замечу, что это зависит от используемого языка, но в общем случае,
без относительно к нашему Pascal, мы будем считать, что это число не определено.
Так вот сравнивать наши значения текущего элемента с неопределенным — это
некорректно, потому что там может быть любое число,
в том числе оно может быть случайно равно нашему текущему элементу массива a.
Потому что при выходе индекса за границы массива наше сравнение невозможно.
Это следует запомнить.
Рассмотрим выполнение программы, которая формирует новый массив,
состоящий из повторяющихся элементов исходного массива.
Здесь у нас сначала вводится длина массива, а затем сами элементы.
Напоминаю, что массив в данном случае может быть только целочисленным,
потому что элементы сравниваются на строгое равенство,
и наш основной цикл работает следующим образом.
У нас есть количество элементов в массиве b.
Вначале оно равно 0.
Далее мы проходим по всем номерам элементов в массиве a и проверяем,
повторяется ли текущий элемент в нашем массиве.
Мы рассматриваем при помощи счётчика j все элементы этого массива и смотрим.
Пока j не превышает длины массива,
и ai‐тое не равно aj‐тому, или i = j, то есть, иными словами говоря,
пока не найден повтор этого элемента, мы увеличиваем j на 1.
Если элемент повторялся, то j остаётся ≤ na,
то есть нарушилось второе условие,
которое состоит из двух частей: ai‐тое стало = aj‐тому,
и при этом i ≠ j, мы взяли отрицание по закону де Моргана.
И если найден повтор, то тогда мы записываем этот элемент в новый массив.
То есть увеличиваем количество элементов массива b,
и на это место в наш массив записываем текущий элемент массива a.
Дальше проверяем существование массива b.
Если его длина осталась равной 0, то мы сообщаем о том, что этого массива нет.
А если это не так, то выводим последовательно все элементы в одну
строку, а затем переходим на новую строчку.
Сейчас мы запустим нашу программу
и попробуем задать те исходные данные,
которые были у нас с вами в примере, когда мы рассматривали, как решается эта задача.
Итак, количество элементов массива a = 7,
и эти элементы были:
[БЕЗ ЗВУКА] Получаем массив b,
в котором все повторяющиеся элементы массива a присутствуют.
Поскольку по нашему условию не было сказано,
что все элементы массива b различны, то каждый элемент массива a,
который повторяется, будет попадать в массив b.
То есть у нас 1, которая повторяется три раза, 2,
которая повторяется два раза, и в новом массиве у нас тоже две 2, ну и единиц три.
Теперь давайте попробуем запустить программу ещё раз и посмотреть,
что будет, если элементы массива не повторяются.
Ну, допустим, я возьму четыре элемента — 1 3 5 и 9.
В данном случае мы получаем сообщение о том, что у нас нет массива b.
Теперь давайте попробуем изменить условия задачи.
Предположим, мы с вами хотим, чтобы в массив попадали
не повторяющиеся элементы, а, наоборот, те, которые не повторяются.
В нашем случае мы должны внимательно посмотреть на алгоритм
и подумать: а что, собственно говоря, придётся в этом алгоритме изменить.
Основная часть останется неизменной.
По‐прежнему длина массива b вначале равна 0.
Мы проходим по всем номерам элементов в массиве a, проверяем,
повторяется ли элемент, и нам с вами нужно будет записать условие,
противоположное исходному.
Здесь у нас было j ≤ na, когда элемент у нас повторялся.
Если мы изменим знак на противоположный,
запишем, что j у нас было больше,
чем na, то есть это условие означат то,
что наш элемент ai‐тое не повторяется.
Тогда, если мы запустим программу ещё раз
и попробуем задать следующие исходные данные.
Допустим, у меня будет семь элементов массива: 1 2
3 4 1 2 и 5.
В результате у меня получились элементы 3,
4 и 5, которые, в отличие от 1 и 2, в массиве не повторяются.
Теперь давайте придумаем исходные данные, при которых нового массива не будет.
Например, три элемента, каждый из которых равен 1.
В результате у нас нет массива b.
То есть мы видими, что проверка того,
что элемент повторяется в массиве, отличается от проверки того,
что он в массиве не повторяется только лишь знаком неравенства.
Если элемент повторяется, неравенство было нестрогое меньше или равно,
а если он не повторяется, то, наоборот, — строго больше.
В остальном, эти алгоритмы одинаковы.
[МУЗЫКА]
[МУЗЫКА]
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
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.
