ПЕРЕВЕРТЫШИ
Вот одна из простейших задач на работу со строками и символами, которая отлично подходит для отборочных туров внутришкольных олимпиад, называется она «перевертыш». Буквы введенного слова нужно записать в обратном порядке.
В основе решения этой элементарной задачи лежит тот факт, что строка – это последовательность символов, так что во время работы программы с помощью специальной функции можно получить доступ к любому символу. В языках Delphi и С++ доступ к отдельному символу можно получить, указав номер этого символа в квадратных скобках.
Например, если есть строковая переменная s со значением «Камиль Сен-Санс», то в результате выполнения инструкции переменная s будет содержать строку: «Камилл Сен-Санс». С учетом сказанного алгоритм решения этой задачи может быть такой: меняем местами первый и последний элемент, затем -второй и предпоследний, и так далее…
Но представлять строку как одномерный массив символов можно не во всех языках программирования (в старых реализациях Бейсика, например, нельзя), поэтому будем пользоваться специальной функцией, которая позволяет вырезать подстроку из строки.
В языке Delphi эта функция называется Сору, вот ее форма записи: Сору(строковая переменная, а, Ь), где Строковая переменная -это строка, из которой происходит выделение, а – это позиция, с которой начинается выделение, a b -количество выделяемых символов. Чтобы продемонстрировать использование этой функции, возьмем уже имеющуюся строковую переменную s (значение «Камилл Сен-Санс») и вырежем из нее в отдельные строковые переменные имя и фамилию композитора. Nome :*Сору(», 1, в). Fain :*Сору(». в, longth(a)-e+1). В качестве второго параметра функции Сору оператора присваивания переменной Fam я использовал функцию 1епдИт(строковая переменная), которая возвращает количество символов в строке (строка дол -жна быть указана в качестве параметра функции).
Итак, вот алгоритм решения этой задачи: реализуем цикл от предпоследнего до первого символа строки (для этого вместо слова do в объявлении цикла пишем downto) и некой третьей строковой переменной присваиваем значение последнего символа, затем предпоследнего, и т. д., т.е. строка, в которой реализуется добавление символов в цикле, будет иметь вид з1 :»в1 + Сору(з, I, 1).
Ну, теперь написать исходник этой программы для вас не составит
труда.
Продолжим наши увлекательные «разборки со строками» и решим еще парочку стандартных задач на эту тему.
СЧИТАЕМ СТРОКИ
Ну, например, такую – нужно посчитать, сколько в строке открывающих и закрывающих скобок и узнать, каких больше. Тут все вроде просто – перебираем все символы строки (функция Сору) и, если символ – (, то увеличиваем первую переменную-счетчик на один (п1 :=п1 + 1)(а если это – символ закрывающей кавычки, то тогда увеличиваем второй счетчик (п2 :=п2+1) и потом сравниваем эти две переменные.
Вот еще задача на строки – даны три слова (введены в одной строке), нужно подсчитать, сколько в них совпадений (т.е. сколько одинаковых слов). Вообще, это задача довольно муторная в том плане, что все слова сначала нужно вырезать. Каждое слово удобно поместить в массив. Массив – это структура данных, представляющая собой набор однотипных переменных, имеющих одинаковое имя. Доступ к элементам массива осуществляется по индексу (номеру), который указывается в квадратных скобках. Массив объявляется так:
var: nnrtviNi n;i of ТИП
Здесь N1 и N2 в квадратных скобках – это константы (обычные или именованные), определяющие диапазон индексов массива, а ТИП -тип элементов массива. Присвоить какому-либо элементу массива значение можно так:
01 At 100):*1В4
(При этом, разумеется, индекс, указанный в присваивании, должен входить в диапазон при объявлении, а тип элементов массива должен быть целого типа.)
Выше был приведен пример одномерного массива. Рассматривать многомерные массивы в этой статье я не буду.
Теперь вернемся к нашей задаче. Поскольку написать соответствующую программу новичку довольно трудно, воспользуемся приемом разбиения, которым часто пользуются профессиональные программисты при написании больших программ.
Для начала напишем программу, которая просто сортирует буквы в строке. Как я уже говорил выше, в некоторых языках программирования строку можно представить как одномерный массив символов, поэтому будем полагать, что некая строка s -это массив, который нужно отсортировать Существует несколько алгоритмов сортировки массива.
Рассмотрим самый простой из них – метод пузырька». Суть его заключается в обмене двух соседних элементов. Если текущий элемент больше следующего, то элементы меняются местами, т.е. элементы с меньшими значениями «всплывают», а с большими – «тонут» (отсюда и название).
Легче всего реализовать этот алгоритм в цикле for, который будет продолжаться до предпоследнего элемента. Для обмена необходимо использовать «третью» переменную, которая будет хранить один из элементов массива (подробнее об этой проблеме см. следующую задачу).
Реализуем данный алгоритм, экономя такты процессора – для этого заведем булеву переменную, отслеживающую обмены. Ведь если обменов нет. значит, задача решена и не имеет смысла «зацикливаться» дальше.
Ну а теперь, когда вы написали (искренне на это надеюсь) эту «игрушечную» программу, можно обсудить алгоритм решения задачи, ради которой мне пришлось делать столько ремарок и оговорок. Итак, как я уже говорил, мы должны «вогнать» в массив отдельные слова. По идее, слова должны разделять пробелы, поэтому их-то мы и ищем.
Найдя первый пробел, вырезаем (с помощью функции Сору) все символы, которые находятся до этого пробела, встретив второй пробел, вырезаем все. что находится между первым и вторим пробелом (позицию первого пробела нужно сохранить).
Наконец, последний шаг – это вырезать все символы, находящиеся правее последнего пробела (в языке Бейсик, если мне не изменяет память, есть даже такие функции, RIGTHS и LEFTS). Вот, вроде, и все с этой задачей. Только следует помнить, что при «забивке» массива лучше не включать в выделение пробелы – это затруднит сравнение.
ПОМЕНЯЙ ЗНАЧЕНИЯ
Попробуем решить задачу на структуры данных, суть которой заключается в том, чтобы поменять значения двух числовых переменных, не используя буфера, т.е. третьей переменной. Помню, похожий конкурс объявляли даже в журнале «Хакер» пару лет назад…. Итак, первый, самый простой способ поменять значения двух переменных – это использовать буфер для хранения какой-то одной переменной, ведь если записать инструкции
А:=В В :-А,
обе переменные будут содержать значение В. Вот работающий код:
С:=А А:=В В :=С
Но ведь у нас в условии сказано, что третьей переменной быть не должно! Поэтому попробуем сделать так:
А:=А + В В :=А – В А:=А-В
Подумайте, как можно сделать так. чтобы программа меняла значения двух переменных независимо от их типа (наш пример пригоден только для чисел). Подсказка: для решения используйте инструкцию XOR.
Реализовав на своем компьютере эти типовые задачи по программированию, вы сможете уже сейчас приступить к решению довольно сложных олимпиадных задач по программированию, т.к. они,чаще всего, ориентированы на математическую смекалку, а не на знание особых приемов программирования (это относится к школьным задачам).
Попробуйте, например, решить задачи из областной олимпиады кодин-гу, проведенной Нижегородским университетом имени Лобачевского (задания для обоих туров можно найти на страничке факультета ВМК, ссылку поищите на сайте университета, www.unn.ru).
Если вам требуется качественный remont-balkon.ru\ закажите его тут remont-balkon.ru