Программирование на visual basic
 Скачать 1.19 Mb.
|
|
e ставится так, что слева от него все ' элементы > e, а справа Do ' Найти слева первый элемент, который не больше e While a(i) > e : i = i + 1 : Wend ' Найти справа элемент, который не меньше e While a(j) < e : j = j – 1 : Wend If i <= j Then t = a(i): a(i) = a(j): a(j) = t ‘ Перестановка элементов i = i + 1: j = j - 1 End If Loop While i <= j ' Рекурсивно вызвать программу быстрой сортировки, но уже с ‘ другими левой и правой границами If (L < j) Then Call СортировкаМассиваБыстрая(a, L, j) ' Правая часть If (i < R) Then Call СортировкаМассиваБыстрая(a, i, R)' Левая часть 101 ' Сюда попадаем, если L>=j и R<=j. Т.е., когда весь массив ‘отсортирован End Sub 8.6. Сравнения быстродействия основных типов сорти- ровок Попробуем оценить эффективность приведенных методов сортировок на примере числового массива случайных вещественных чисел с двойной точностью. Тестировать разработанные программы будем на массивах большой размерности. Так как визуальный контроль требует значительно- го времени, мы напишем вначале две логические подпрограммы, которые контролируют правильность отсортированного массива. ‘ Функция, которая возвращает значение True, если массив ‘ отсортирован правильно. Т.е. a i+1 , ≤ a i Function ControlSortMas(a() As Double, n As Long) As Boolean Dim i As Long ' Действуем от противного. Вначале считаем, что массив ' не отсортирован ControlSortMas = False For i = 1 To n – 1 ' Массив отсортирован не правильно If a(i) < a(i + 1) Then Exit Function Next i ' Массив отсортирован правильно ControlSortMas = True End Function Вторая логическая программа контролирует равенство сумм первона- чального и отсортированного массивов. Это необходимо для уверенности в том, что отсортирован именно исходный массив. В этой функции исполь- зуется передача параметра S по значению. Т.е. значение переменной S по- сле выхода из функции восстанавливается. Function ControlSummMas(a() As Double, N As Long, _ ByVal S As Double) As Boolean Dim i As Long For i = 1 To N : S = S - a(i) : Next i ControlSummMas = Abs(S) / N < 0.000001 If Not ControlSummMas Then Debug.Print " S="; S; End Function Теперь напишем основную программу, в которой сформируем два оди- наковых массива a и b . Затем поочередно вызовем подпрограммы сорти- ровки, различными методами восстанавливая каждый раз массив a, ис- пользуя массив b . Между вызовами подпрограмм при помощи функции time считываем текущее время. 102 Sub ТестВсехСортировокНаБыстродействие() Const N = 1000 Dim a(N) As Double, b(N) As Double, i As Long, S As Double Debug.Print " ************N="; N; " ********************" Randomize Timer: S = 0 For i = 1 To N b(i) = Rnd * 10000 S = S + b(i) ' Контрольная сумма a(i) = b(i) Next i Dim time1 As Single ' Время до начала сортировки в секундах от начала суток time1 = Timer Call СортировкаМассиваМетодомПузырька(a, N) time1 = Timer - time1 ' Время сортировки в секундах Debug.Print "Время сортировки методом пузырька="; time1; ' Если обе контролирующие программы возвращают значение True ‘ напечатать Ok! If ControlSortMas(a, N) And ControlSummMas(a, N, S) Then _ Debug.Print "Ok!" time1 = Timer Call СортировкаМассиваМетодомВыбора(a, N) time1 = Timer - time1 Debug.Print "Время сортировки методом Выбора="; time1; If ControlSortMas(a, N) And ControlSummMas(a, N, S) Then _ Debug.Print "Ok!" For i = 1 To N ' Восстановить первоначальный массив a(i) = b(i) Next i time1 = Timer Call СортировкаМассиваМетодомВставки(a, N) time1 = Timer - time1 Debug.Print "Время сортировки методом Вставки="; time1; If ControlSortMas(a, N) And ControlSummMas(a, N, S) Then _ Debug.Print "Ok!" time1 = Timer Call СортировкаМассиваБыстрая(a, 1, N) time1 = Timer - time1 Debug.Print "Время сортировки Быстрая="; time1; If ControlSortMas(a, N) And ControlSummMas(a, N, S) Then _ Debug.Print "Ok!" End Sub На приведенной диаграмме рис. 8.1, представлены результаты сравни- тельного анализа быстродействия четырех методов сортировки. Число элементов массива N изменялось от 1000 до 10000. Время t измерялось в секундах. Самой эффективной является быстрая сортировка. График для нее практически слился с горизонтальной осью. Для простых сортировок с 103 увеличением количества элементов время увеличивается по квадратному закону. Наиболее неэффективной является самая простая сортировка мето- дом "пузырька". Сортировка методами выбора и вставки являются одина- ковыми по быстродействию и примерно в три раза эффективнее сортиров- ки методом "пузырька". Рис. 8.1. Зависимость времени сортировки от количество элементов массива Рассмотрим отдельно зависимость быстрой сортировки от числа эле- ментов (табл.8.1). От N=100000 до N=2000000 время растет линейно. Т.е. при увеличении N в два раза время t (с) также увеличивается в два раза. При N=4000000 время увеличилось в 4 раза. Это связано с тем, что рас- чет проводился на компьютере, имеющем объем оперативной памяти 32 Мб. Массив в 4000000 элементов типа Double занимает 32 Мб. Поэтому при сортировке такого огромного массива используется виртуальная па- мять на диске. Таблица 8.1 N 100 000 200 000 400 000 800 000 t 1,9818 4,0106 8,4584 17,633 N 1 000 000 2 000 000 4 000 000 8 000 000 16 000 000 t 22,24125 46,74094 196,081 536,1816 1689,729 9. Задачи на символьные переменные В задачах на символьные переменные обычно информация записывает- ся в переменную символьного типа и затем производится обработка этой информации. В одну переменную можно записать до 2 31 (≈2 млрд) симво- лов. Обработка символьной информации производится при помощи тек- 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 0 2 0 0 0 4 0 0 0 6 0 0 0 8 0 0 0 1 0 0 0 0 N t П у зы р ь ко в а я В ы б о р В с та в ки Б ы с тр а я 104 стовых функций и операции конкатенации строк. Операция конкатенации строк обозначается символов + или &. 9.1. Задачи обработки текстовой информации 9.1.1. Подсчитать общее количество символов, количество цифр и пробелов в текстовом файле. Решение. Предполагается, что текстовый файл существует и в нем на- ходится некоторая текстовая информация. Для получения текстового фай- ла при помощи Word необходимо после подготовки файла сохранить его в формате только текст . Следует отметить, что в конце текстовой строки стоят два невидимых символа с кодом ASCII 10 и 13, означающие конец строки и возврат каретки. В конце файла стоят управляющие символы, оз- начающие конец файла. Логическая функция EOF возвращает значение True, если код следующего символа файла является кодом конца файла. Кроме перечисленных управляющих символов существуют другие, коды их находятся в диапазоне 0-31. Для того чтобы узнать код символа, ис- пользуется строковая функция Asc, возвращающая код символа. Sub ЧислоСимволовВФайле () Dim s As String, c As String * 1 Dim NBlanks As Long, NDigits As Long, Nsimb As Long ' открыть текстовый файл на чтение и связать его с номером 5 ' d:\aa\docword\metodic\t1.txt - полное имя файла Open "d:\aa\docword\metodic\t1.txt" For Input As #5 NBlanks = 0: NDigits = 0: Nsimb = 0 ‘ Пройти по всем символам файла с номером 5 Do While Not EOF(5) ' Цикл до конца файла с номером 5. ‘В переменную c считать очередной символ из файла c = Input(1, #5) If Asc( с ) >31 Then ‘ Если не управляющий символ Nsimb = Nsimb + 1 ' Общее число символов Select Case c Case "1" To "9" ‘ Символ является цифрой NDigits = NDigits + 1 Case " " ‘ Символ является пробелом NBlanks = NBlanks + 1 End Select End if Loop Close #5 ' Закрывает файл. Debug.Print "Количество цифр в файле="; NDigits; _ " Количество пробелов в файле ="; NBlanks; _ "Количество символов в файле="; Nsimb End Sub 9.1.2. В текстовом файле поменять все символы # на слово файл. Решение. 105 Sub ЗаменаСимволовВФайле () Dim s As String, i As Long, c As String * 1 ‘ открыть текстовый файл на чтение и связать его с номером 1 Open "d:\aa\docword\metodic\t2.txt" For Input As #1 Do While Not EOF(1) ' Цикл до конца файла номер 1. c = Input(1, #1) ' Читает один символ в переменной c. ‘ Копирует в строку s либо слово файл, либо очередной символ If c = "#" Then s = s + "файл" Else s = s + c Loop n = Len(s) ' Длина строки Close #1 ' Закрывает файл. ‘ Открыть текстовый файл на запись и связать его с номером 1 Open "d:\aa\docword\metodic\t2.txt" For Output As #1 ‘ Записывает преобразованную строку s в файл Write #1, s Close #1 End Sub 9.1.3. В текстовом файле поменять слово Дима на два слова – Дмитрий Петрович Решение. Открываем файл на чтение и считываем первые 3 символа. Затем в цикле считываем с файла один очередной символ и накапливаем его в переменной s. После чего проверяем, является ли цепочка из послед- них 4 символов строки s словом Дима. Если да, то вместо последних 4 символов Дима пишем 16 символов – Дмитрий Петрович . Выход из цик- ла происходит при достижении конца файла. После выхода из цикла за- крываем открытый на чтение файл номер 1. Затем открываем его же на за- пись и при помощи оператора Print выводим полученную строку s. Sub ЗаменаДимаНаДмитрийПетровичВФайле () Dim s As String, n As Long, c As String * 1, nSimb As Long Open "d:\aa\docword\metodic\t2.txt" For Input As #1 s = Input(3, #1) ' Прочитать первые 3 символа nSimb = 3 ' Число обработанных символов в строке s Do While Not EOF(1) ' Цикл до конца файла номер 1 c = Input(1, #1) ' Читает один символ в переменной c s = s + c : nSimb = nSimb + 1 If Mid(s, nSimb - 3, 4) = "Дима" Then s = Left(s, nSimb - 4) + "Дмитрий Петрович" : nSimb = nSimb + 12 End If Loop Close #1 ' Закрывает файл Open "d:\aa\docword\metodic\t2.txt" For Output As #1 Print #1, s; : Close #1 End Sub 9.1.4. Во введенном с клавиатуры тексте подсчитать количество рус- ских букв, латинских букв и заглавных букв. 106 Sub КоличествоЦифрБуквРусскихЛатинских() Dim s As String, RusCh As Long, LatCh As Long Dim i As Long, ZgCh As Long, c As String * 1 s = InputBox("Введите текст") For i = 1 To Len(s) c = Mid(s, i, 1) ' i-тая буква введенной строки Select Case c Case "А" To "я" ‘ Русская буква RusCh = RusCh + 1 Case "A" To "z" ‘ Латинская буква LatCh = LatCh + 1 End Select ‘ Заглавная латинская или русская буквы If (c > "A" And c < "Z") Or (c > "А" And c < "Я") Then ZgCh = ZgCh + 1 Next i Debug.Print "Число русских букв в тексте ="; RusCh Debug.Print "Число латинских букв в тексте ="; LatCh Debug.Print "Число заглавных букв в тексте ="; ZgCh End Sub 9.1.5. Во введенном с клавиатуры тексте подсчитать количество рус- ских гласных букв. Решение. В переменную RusGl записываем все гласные буквы. Вводим текст в переменную s. В цикле по всем символам строки s, с помощью функция InStr, проверяем, есть ли i-тый символ в строке RusGl. Функция InStr возвращает либо номер гласной буквы, если этот символ является гласной буквой, либо 0, если этот символ не является гласной буквой. Чет- вертый параметр функции InStr равен 1, поэтому при сравнении большие и маленькие буквы считаются одинаковыми. Sub КоличествоРусскихГласныхБукв() Dim s As String, NGl As Long, RusGl As String, i As Long RusGl = "аеёиоуыэюя" s = InputBox("Введите текст") For i = 1 To Len(s) If InStr(1, RusGl, Mid(s, i, 1), 1) > 0 Then NGl = NGl + 1 Next i Debug.Print "Число гласных русских букв в тексте ="; NGl End Sub 9.1.6. Во введенном с клавиатуры тексте подсчитать количество слов. Решение. Для простоты программы словом будем называть последова- тельность символов, отличных от пробелов, заключенных между пробела- ми. Вводим логическую переменную inWord, принимающую значение Ис- тина, если текущий i-тый символ входит в какое-то слово. Обходим по всем символам введенного текста и подсчитываем количество символов, являющихся последним символом в слове. Символ является последним в 107 слове, если переменная inWord принимает значение Истина и следующий символ – пробел или конец текста. Sub ПодсчетКоличестваСлов() Dim nWord As Long, Text As String, i As Long, c As String * 1 Dim endWord As String, inWord As Boolean endWord = ",;: !?" ' Символы конца слова 'Ввести текст и для упрощения алгоритма добавить пробелы ‘справа и слева Text = “ “+InputBox("Введите текст")+” ” inWord = false ' Обработка первого символа текста For i = 2 To Len(Text) c = Mid(Text, i, 1) ' i-тый символ текста If inWord Then ' Символ находится внутри слова If InStr(1, endWord, C, 0) > 0 Then ' Вышли из слова ‘ Сбросить флажок inWord и накопить 1 inWord = False: nWord = nWord + 1 End If Else ' Вне слова и не пробел. Установить флажок внутри слова If c <> " " Then inWord = True End If Next i Debug.Print "Количество слов в тексте = "; nWord End Sub 9.1.7. Написать программу, которая убирает лишние пробелы в выделенном в Word фрагменте. Данная программа может быть полезна при работе c документами текстового процессора Word 97. Sub УбратьЛишниеПробелы() Dim st As String, st1 As String, c As String * 1, i As Long, P As String * 1 P = " " ' пробел 'Переписать выделенный фрагмент в переменную st st = Selection.Text For i = 1 To Len(st) ' Обойти все символе в фрагменте c = Mid(st, i, 1): st1 = st1 + c If c = P Then ' Если текущий символ пробел ' Пропустить все пробелы после текущего пробела While Mid(st, i + 1, 1) = P ´Пока пробел, выполнять цикл i = i + 1 ' Перейти к следующему символу Wend End If Next i Selection.Text = st1 ' Переписать полученную строку без пробелов End Sub 9.1.8. Написать программу, которая убирает все символы конца абзаца в выделенном фрагменте текста текстового процессора Word. 108 Очень полезная программа для обработки текстов, полученных при помощи текстовых редакторов в операционной системе Dos и преобразо- ванных в формат документов Word. Sub УбратьСимволыКонецАбзаца() Dim st As String, st1 As String, c As String * 1, i As Long 'Переписать выделенный фрагмент в переменную st st = Selection.Text For i = 1 To Len(st) ' Обойти все символы в фрагменте c = Mid(st, i, 1) ‘ i-тый символ ‘ Если символ является символом конца абзаца (код 13), ‘ то его не включать в преобразованный текст st1 If Asc( c ) <> 13 Then st1 = st1 + c Next i Selection.Text = st1 ' Переписать полученную строку без пробелов End Sub 9.1.9. В выделенном фрагменте текста подсчитать количество слов, имеющих три гласных буквы. Sub ПодсчетКоличестваСловСТремяГласными() Dim nWord As Long, Text As String, inWord As Boolean, i As Long, _ c As String*1, Gl As String, NGlInWord As Long, nWodr As Long, _ endWord As String Gl = "аеёиоуыэюя" ' Все русские гласные буквы endWord = ",;: !?" ' Символы конца слова Text = Selection.Text Text = " " + Text + " " ' Добавляем пробелы справа и слева nWord = 0 ' Число слов с тремя гласными NGlInWord = 0 ' Число гласных в слове inWord = False ' =true, если обрабатываемый символ внутри слова For i = 1 To Len(Text) c = Mid(Text, i, 1) ' i-тый символ обрабатываемого текста If inWord Then ' Символ находится внутри слова If InStr(1, Gl, c, 1) > 0 Then NGlInWord = NGlInWord + 1 If InStr(endWord, c) > 0 Then ' Вышли из слова. Сбросить флажок inWord и накопить 1 inWord = False ' Последний символ вне слова If NGlInWord = 3 Then nWord = nWord + 1 'Три гласных в слове End If Else ' Вне слова и не пробел. Установить флажок вошли в слово If c <> " " Then ' Первая буква слова inWord = True 'Последний символ внутри слова ' если гласная, то NGlInWord = 1, иначе NGlInWord = 0 If InStr(1, Gl, c, 1) > 0 Then NGlInWord = 1 Else NGlInWord = 0 End If End If Next i Debug.Print "Количество слов с тремя гласными = "; nWord 109 End Sub 9.2. Задачи шифрования текста Часто возникает необходимость передать некоторую текстовую ин- формацию таким образом, чтобы она была непонятна посторонним поль- зователям компьютерных сетей. Спрятать информацию от посторонних глаз можно при помощи программ шифровальщиков. Программа- шифровальщик по некоторым правилам изменяет текст до неузнаваемости и записывает в файл. После чего файл по сети или другим способом пере- дается адресату, который запускает программу-расшифровщик и получает исходный файл. Приведем некоторые простейшие алгоритмы и программы шифрования и расшифрования русских текстов. 9.2.1. Зашифровать текст, находящийся в ячейке рабочего листа, по следующему правилу: 1) в конце строки добавить три произвольных сим- вола; 2) после каждой гласной буквы добавить два очередных символа из введенного в программе ключевого предложения; 3) в полученном тексте переставить 1 ый символ с 4 ым , 2 ой – 3 ий , 5 ый – 8 ым , 6 ой – 7 ым , и так по всем полным четверкам символов. Решение. При отладке программы будем использовать рабочий лист EXCEL. В ячейку (1,3) запишем текст, который надо закодировать. В ячей- ку (2,3) запишем результат первого шага, а в ячейку (3,3) – окончательно закодированный текст. Для перестановки двух символов в строке напишем подпрограмму Swap с тремя формальными параметрами: |