Курс «Алгоритмизация вычислений» будет вам интересен и просто необходим, если вы хотели бы изучить программирование с нуля и выйти на хороший базовый уровень, научиться составлять, понимать и анализировать алгоритмы. В результате изучения курса вы сможете: • записывать математическую постановку задачи; • применять стандартные алгоритмы для решения задач; • оценивать оптимальность алгоритмов и выбирать алгоритм, дающий лучшее решение задачи; • проверять правильность алгоритма методом трассировки; • кодировать алгоритмы с использованием технологии структурного программирования; • отлаживать и тестировать программы. Изучение данной дисциплины базируется на знании студентами основ математики, информатики и основ алгоритмизации в пределах программы средней школы, умении применять математический аппарат при выборе метода решения задачи. Для освоения учебной дисциплины, студенты должны владеть школьными знаниями, получаемыми в процессе изучения указанных выше курсов. Этот курс лежит в основе всего программирования. Можно сказать, что это фундамент, на котором будет строиться все дальнейшее обучение программированию. Мы будем решать задачи, постепенно переходя от простых к более сложным. В конечном итоге вы научитесь решать задачи обработки динамических списков, т.е. работать на хорошем базовом уровне.
Решение задач обработки символьных строк. Правильность расстановки скобок в формуле. Удаление парных пробелов и подсчет количества слов
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
Ерохина Елена АльфредовнаСтарший преподаватель
Департамент компьютерной инженерии МИЭМ Высшая Школа Экономики
[МУЗЫКА]
[МУЗЫКА] Рассмотрим
решение задач обработки символьных строк.
Первая задача.
Нам дана символьная строка, которая содержит математическую формулу.
Нам нужно проверить, что круглые скобки в этой формуле расставлены верно.
Мы будем проверять, во-первых, что количество открывающихся скобок равно
числу закрывающихся, а во-вторых, что ни одна закрывающаяся
скобка не закрылась раньше, чем открылась соответствующая открывающаяся.
Например, если я рассмотрю формулу (a + b) = ((a + b)), взятое в двойные скобки,
то это верная расстановка скобок — сколько открылось скобок, столько и закрылось,
и ни одна закрытая скобка не предшествует соответствующей открытой.
Если я рассмотрю два вот таких вот выражения, то оба они не верны.
В первом случае у нас открытых скобок больше, чем закрытых,
а во втором у нас закрывающаяся скобка,
которая расположена на третьем месте, предшествует открывающейся,
поэтому во втором и в третьем примере расстановка скобок не верна.
Рассмотрим программу, которая решает эту задачу.
Переменная s предназначена для хранения символьной строки,
и есть переменные no и nz — это количество открытых и закрытых скобок соответственно,
и кроме того переменная цикла i, которая считает,
на какой позиции мы сейчас находимся.
Булевская переменная flag покажет нам, правильно ли расставлены скобки.
Сначала мы вводим символьную строку.
Обращаю ваше внимание, что символьная строка читается при помощи
оператора readln, то есть она должна быть прочитана полностью.
Далее инициализируем число открытых и закрытых скобок нулем,
flag присваиваем начальное значение истина, то есть мы считаем,
что расстановка скобок пока верна, и берем текущий номер символа, равный 1.
Мы с вами используем цикл «пока», а не цикл «от...
до», потому что как только мы найдем в нашей формуле место, где очевидно,
что скобки расставлены неверно, мы не будем рассматривать эту строку до конца.
Поэтому цикл «пока i меньше или равно длины строки»,
и переменная flag остается истинной, то есть расстановка скобок верна.
Внутри этого цикла мы выполняем несколько действий,
и поэтому используется составной оператор.
Если текущий символ — это скобка открытая,
то тогда мы прибавляем 1 к числу открывающихся скобок.
Если у нас s[i] — это скобка закрытая,
тогда к числу закрытых скобок также прибавляется 1.
Далее мы проверяем, если число закрытых скобок превышает число открытых,
то это неверная расстановка, мы меняем значение переменной flag на ложь,
и таким образом мы выйдем из цикла.
Затем мы выбираем следующий символ.
Наш составной оператор заканчивается, то есть закрывается цикл «пока»,
и дальше мы проверяем, верно ли расставлены скобки.
Во-первых, мы проверяем, что у нас flag является истинной,
то есть ни разу число закрытых скобок не превысило число открытых.
И, во-вторых, их количества равны — сколько скобок открылось,
столько и закрылось.
В этом случае скобки расставлены верно, а в противном случае мы выводим сообщения о
том, что расстановка скобок не верна, и наша программа заканчивается end с точкой.
Рассмотрим программу, которая проверяет,
верно ли расставлены скобки в заданной символьной строке.
Мы будем проверять,
что количество открытых скобок и число закрытых совпадает, а кроме того,
что ни одна закрывающаяся скобка не предшествует открывающейся.
Запустим нашу программу и сначала зададим формулу, где скобки расставлены верно.
Для этого нам нужно ввести формулу в символьную строку.
Например.
Здесь расстановка скобок верна.
Попробуем задать еще одну, где глубина вложенности скобок больше.
[БЕЗ_ЗВУКА]
Здесь скобки также расставлены верно.
Теперь попробуем ввести формулу с ошибкой.
Например.
[БЕЗ_ЗВУКА] Здесь расстановка скобок неверна,
потому что закрытая скобка предшествует открывающейся.
Попробуем еще раз.
Здесь у нас скобки расставлены неправильно,
потому что у нас больше закрытых скобок, чем открытых.
Вот она у нас лишняя скобка.
Ну еще раз попробуем.
Здесь у нас, наоборот, лишняя открытая
скобка, и расстановка скобок в этой формуле также неверна.
То есть мы с вами протестировали работу нашей программы на различных строках,
и мы с вами видим, что программа работает верно.
Когда расстановка скобок верна, нам выводится сообщение о том,
что это верная расстановка скобок, ну а во всех случаях неверной расстановки,
так же выводятся соответствующие сообщения.
Рассмотрим программу, которая для данной символьной строки,
содержащей слова, разделенные пробелами, решает две задачи.
Вначале удаляются лишние парные пробелы,
то есть между словами остается ровно по одному пробелу,
а затем происходит подсчет количества слов в этой строке.
Рассмотрим программу.
Для хранения символьной строки предназначена переменная s,
и далее есть несколько целых переменных — это n, i и k: соответственно,
число слов, переменная цикла и позиция пробела в строке.
Для начала мы с вами должны ввести символьную строку,
мы ее читаем при помощи readln, то есть читаем строку целиком.
Далее нужно удалить все лишние парные пробелы.
Для наглядности в этой программе символ пробел обозначен отдельно,
но если мы с вами захотим откомпилировать эту программу,
то мы должны будем написать на этих местах настоящие пробелы.
Здесь символ используется просто для наглядности.
Итак, первым делом мы определим позицию вхождения двух пробелов в нашу строку.
Результатом будет номер первого вхождения двух пробелов в строчку,
при этом, если такое вхождение не обнаружено, то результат будет равен 0.
Далее мы организуем цикл, который будет продолжаться,
пока есть вхождение двух пробелов в строку,
при этом k у нас определяет первое такое вхождение.
Пока k больше 0, то есть пока в строке присутствует два пробела подряд,
мы удаляем один из них и вновь определяем,
есть ли вхождение двух пробелов в нашу строку, то есть цикл будет продолжаться до
тех пор, пока в строке есть хотя бы пара пробелов, расположенных рядом.
После того, как все парные пробелы удалены, то есть из двух пробелов,
стоящих рядом, оставлен ровно один, мы закрываем наш цикл.
Для контроля выведем строку после удаления
пробелов и далее станем решать вторую часть задачи.
Теперь нам нужно подсчитать количество слов в этой строке.
Первым делом мы смотрим, есть ли у нас пробел перед первым словом.
Если он есть, мы его удаляем.
При этом возможно, что после того, как мы его удалили,
в строке вовсе не осталось символов.
Тогда мы смотрим, верно ли это.
Если у нас в строке нет ни одного символа, то есть строка равна пустой,
то тогда мы выводим сообщение о том, что нет слов.
В противном случае мы можем легко подсчитать количество слов,
потому что оно почти равно числу пробелов.
Пробел на первом месте мы удалили.
После каждого слова у нас есть обязательно пробел,
но это может быть неверно для последнего слова.
Поэтому мы говорим, что если на последнем месте в нашей строке находится символ,
отличный от пробела, то мы тогда прибавляем туда пробел.
После этого мы можем сказать, что количество слов равно числу пробелов.
Мы инициализируем переменную k нулем, далее мы проходим по всем символам
нашей строки, то есть от 1 до длины этой строки, и говорим,
что если текущий символ равен пробелу, то количество слов становится на 1 больше.
По завершении этого цикла мы посчитали,
сколько слов в нашей строке, и мы выводим полученный результат.
Далее мы закрываем условие того, что слова в строке вообще были,
и после этого наша программа заканчивается end с точкой.
Рассмотрим программу, которая решает следующую задачу.
Нам дана символьная строка, в которой содержатся слова,
разделенные одним или несколькими пробелами.
Мы должны оставить между каждой парой слов по одному пробелу,
а затем посчитать, сколько слов в нашей строке.
Первая часть удаляет все парные пробелы и выводит строку,
полученную после удаления пробелов.
Затем происходит подсчет числа слов, мы удаляем первый пробел, если он есть.
Далее мы проверяем, не является ли строка пустой,
если это так, то в ней уже нет слов.
И далее мы проверяем, если на последнем месте символ отличен от пробела,
то мы его туда добавим.
После чего число пробелов равно числу слов, мы подсчитываем это
количество и далее выводим, сколько слов у нас получилось.
Итак, запустим нашу программу и зададим некоторое предложение.
Допустим несколько пробелов.
[БЕЗ_ЗВУКА] Мы видим,
что строка после удаления пробелов лишилась всех пробелов,
в которых было больше 1 между словами или перед первым словом,
и количество слов равно 3.
Теперь попробуем задать в качестве исходных данных символьную строку,
в которой одни пробелы.
В данном случае, строка после удаления пробелов пуста,
и выводится сообщение о том, что нет слов.
Причем, если мы не задаем пробелы в
начале [БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА] и
не задаем пробел в конце, то наша программа также работает правильно.
В этом предложении 6 слов, все парные пробелы удалены,
и после этого количество пробелов совпадает с числом слов.
Мы протестировали нашу программу и получили правильные результаты для всех
строк, которые мы рассматривали.
[МУЗЫКА]
[МУЗЫКА]
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.
