Сортировка методом слияний.
Определение. Целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов называется упорядоченным.
Использование упорядоченности позволяет создавать эффективные алгоритмы для решения многих интересных задач.
Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов.
Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[1] сравнивается с элементом В[1] и наименьший из них записывается в массив С. Если наименьшим был А[1], то на следующем шаге сравниваются А[2] и B[1], а если наименьшим был B[1], то будут сравниваться A[1] и B[2] и т.д. Если на очередном шаге окажется, что из одного входного массива все элементы переписаны в С, то переписывается элемент из другого массива.
Рассмотрим пример работы алгоритма слияния.
Пусть в массиве А содержатся 3 элемента: {5, 13, 14}, а в массиве В - 4 элемента: {7, 9, 10, 12}. Внимательно рассмотрите таблицу, в которой по шагам показано изменение переменных i, i1, i2 и действия с массивами.
Рассмотрите фрагмент решения задачи на слияние двух массивов А и В, которые содержат соответственно n1 и n2 элементов. Результирующий массив С будет содержать n1+n2 элементов.
Функции обработки строковых выражений.
Строка–это либо пустая упорядоченная последовательность символов, либо пустая строка. Для обозначения строки используются кавычки:
"" – обозначение пустой строки;
"Иван" – пример непустой строки.
Между кавычками в обозначении пустой строки пробела ставить нельзя, так как пробел — это тоже символ. Число символов строки называется длиной строки. Длина пустой строки равна нулю.
Каждый символ строки имеет свою позицию —порядковый номер при счёте слева направо. Например, символ И в строке "Иван" имеет позицию1,а символн —позицию4.
В VisualBasicиспользуется понятиеподстроки, например:
"Иван" —это подстрока строки "Иванов";
"+1" —это подстрока строки "Число+100";
"01" не является подстрокой строки "Число+100"
Подстрока S1строкиSназываетсялевой подстрокой, если их первые символы совпадают("Иван" —левая подстрока строки "Иванов").
Подстрока S1строкиSназываетсяправой подстрокой, если их последние символы совпадают ("ов" — правая подстрока строки "Иванов").
Пример С помощью оператора присваивания или оператора ввода задать строковой переменной значение некоторой строки можно следующим образом:
Text1.Text = "Обычное праздничное блюдо на пикнике - шашлык. Однако можно придумать и что-нибудь оригинальное."
S = Text1
Объединение строк
В VisualBasicдля работы со строками предусмотрен только один оператор — операторобъединения (конкатенации). Сего помощью можно слить несколько строк в одну большую строку, наподобие того, как можно сложить несколько чисел в одно. Знаком операции объединения строк является символ амперсанда (&). При объединении нескольких строк, вторая строка помещается в конец первой, третья в конец второй и т.д. В результате получается одна строка, содержащая все указанные в операторе объединения строки.
Синтаксис оператора конкатенации строк выглядит следующим образом:
НоваяСтрока = Строка1 & Строка2 [& СтрокаЗ]
В переменную Новая Строкапомещается результат выполнения операции, а качестве операндовСтрока1, Строка2, СтрокаЗмогут выступать любые допустимые вVisualBasicстроки. Символ амперсанда должен быть отделен от операндов хотя бы одним пробелом. Он указываетVisualBasicна то, что две строки нужно слить в одну.
Пример: Составим проект, который склеивает значения двух текстовых переменных.
Private Sub Command2_Click()
X = Text1.Text
Y = Text2.Text
Z = X & Y
Text3.Text = Z
End Sub
Определение длины строки
Для выполнения некоторых операций со строками требуется знать их длину. Например, при объединении двух строк нужно проверить длину результирующей строки, чтобы она не вышла за пределы допустимой длины строковой переменной, в которую предполагается поместить результат. В любом случае, для определения размеров строки используется функция Len() :
Результат = Len(Строка)
Функцию Len() можно использовать в программе для разнообразных целей. Чаще всего данная конструкция применяется для определения пустой строки. Например, если пользователь ввел некоторую строку, а ее длина равна нулю. нужно выдать соответствующее сообщение об ошибке и прекратить все дальнейшие операции.
Например:
Len("Иван" + "Иванович")возвращает12;
Len ("Иван" + " " + "Иванович") возвращает13;
Len (900 & "- " & 4567)возвращает8.
Пример: Вычислить длину строки
Private Sub Command2_Click()
Dim S As String
Text1.Text = "Обычное праздничное блюдо на пикнике - шашлык. Однако можно придумать и что-нибудь оригинальное (запечённую в углях рыбу или мясо, жаренную на вертеле индейку)."
S = Text1
Text2.Text = Len(S)
End Sub
Изменение регистра символов в строке
Для изменения регистра символов в строке предусмотрены две специальные функции: UCase() иLCase(). ФункцияUCase() возвращает переданную ей в качестве аргумента строку, все символы которой преобразованы в верхний регистр. Функция LCase () выполняет обратную задачу, конвертирует символы исходной строки в нижний регистр.
Описываемые функции изменения регистра символов оказываются очень полезными при работе с командами, введенными пользователем с клавиатуры. В этом случае в программе нужно сравнить полученную строку с набором ключевых слов, которые обычно бывают набраны только прописными буквами. Таким образом, если преобразовать символы введенной команды в верхний регистр, то операция сравнения будет всегда правильно выполняться.
Синтаксис этих команд следующий:
Строка2 = UCase ( Строка1 );
Строка3 = LCase (Строка1).
Где Строка1 может быть набрана как прописными так и строчными буквами,Строка2 – результат работы функцииUСase– строка, содержащая только прописные буквы, аСтрока3 – результат работы функцииLСase– строка, содержащая только строчные буквы.
Например:
UCase ("Visual Basic") возвращает " Visual Basic ";
LCase ("Visual Basic") возвращает " visual basic "
Поиск текста в строке
При работе со строками зачастую нужно выяснить, не встречается ли заданное слово, фраза или любая другая последовательность символов в некоторой строке, и если — да. то в каком именно месте. В VisualBasicпредусмотрены средства поиска одной строки в другой. С их помощью можно создавать программы для поиска нужных слов в тексте, а также для их последующей замены другими словами. Например, может понадобиться в тексте какого-нибудь документа заменить словотекстсловомстрока.
С помощью функции InStr() можно выполнять поиск в строке как отдельного символа, так и целой группы символов. У описываемой функции есть два обязательных и два необязательных параметра. К обязательным параметрам относятся строка, в которой выполняется поиск, и строка. содержащая искомые символы. Если заданная последовательность символов найдена, функция InStr () возвращает номер первого совпадающего символа в исходной строке, начиная с единицы. Если последовательность символов не найдена, функция InStr () возвращает нулевое значение. В простейшем случае, синтаксис функции InStr () выглядит следующим образом:
НомерПервогоСимвола = InStr(ИсходнаяСтрока, ИскомаяСтрока)
Например, в результате выполнения строки кода
PrintInStr('Я встречу вас во вторник", "вас")
будет напечатано число 11, поскольку слово васрасположено в исходной строке с 11 позиции от начала.
С помощью первого (необязательного) параметра функции InStr () можно указать начальную позицию в исходной строке, с которой нужно начинать поиск. Данный параметр должен быть положительным целым числом. Если начальная позиция больше длины строки, функция InStr () возвращает нулевое значение. В данном случае, синтаксис функции InStr () выглядит следующим образом:
НомерПервогоСимвола = InStr(НачальнаяПозиция, ИсходнаяСтрока, ИскомаяСтрока)
Например, в результате выполнения строки кода
Print Instr(7,"KTO не работает, тот ест", "е")
будет напечатано число 14, несмотря на то, что первая буква евстречается в данной фразе на 6-й позиции. Причина состоит в том. что мы заказали поиск символаев строке, начиная с 7-й позиции.
Еще один необязательный параметр определяет, будет ли выполняться поиск без учета или с учетом регистра букв. В последнем случае одноименные строчные и прописные буквы будут восприниматься как совершенно разные символы. Если установить значение данного параметра равным 0 (принято по умолчанию), будет выполнен поиск с учетомрегистра букв. Чтобы выполнить поиск без учета регистра букв, присвойте данному параметру значение 1. Синтаксис функции InStr (), для выполнения поиска без учета регистра букв выглядит следующим образом:
НомерПервогоСимвола = InStr(НачальнаяПозиция, ИсходнаяСтрока, ИскомаяСтрока, 1)
С помощью последнего необязательного параметра можно найти все вхождения заданной цепочки символов в исходной строке.
Для выполнения поиска в обратном направлении в VisualBasicпредусмотрена еще одна функция, которая называетсяInStrRev(). Принцип ее работы совпадает с функцией InStr (), только синтаксис немного отличается: