Учебная программа PRIMSET
В следующем примере, иллюстрирующем приемы работы с множествами, реализуется алгоритм выделения из первой сотни натуральных чисел всех простых чисел[ Простыми называются целые числа, которые не делятся без остатка на любые другие целые числа, кроме 1 и самого себя. К простым относятся 1, 2, 3, 5, 7, 11, 13 и т. д.. ]. В его основе лежит прием, известный под названием “решето Эратосфена”. В соответствии с этим алгоритмом вначале формируется множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до N. В множество primerset (оно будет содержать искомые простые числа) помещается 1. Затем циклически повторяются следующие действия:
Цикл повторяется до тех пор, пока множество BeginSet не станет пустым. Эту программу нельзя использовать для произвольного N, так как в любом множестве не может быть больше 256 элементов. procedure TfmExample.bbRunClick(Sender: TObject); // Выделение всех простых чисел из первых N целых Const N = 255; // Количество элементов исходного множества Type SetOfNumber = set of 1..N; Var n1,Next,i: Word; // Вспомогательные переменные BeginSet, // Исходное множество PrimerSet: SetOfNumber; // Множество простых чисел S: String; Begin BeginSet:= [2..N]; // Создаем исходное множество PrimerSet:= [1]; // Первое простое число Next := 2; // Следующее простое число while BeginSet о [ ] do // Начало основного цикла Begin nl:= Next; //nl-число, кратное очередному простому (Next) // Цикл удаления из исходного множества непростых чисел: while nl <= N do Begin Exclude(BeginSet, nl); n1:= nl + Next // Следующее кратное end; // Конец цикла удаления Include(PrimerSet, next); // Получаем следующее простое, которое есть первое // число, не вычеркнутое из исходного множества Repeat inc(Next) until (Next in BeginSet) or (Next > N) End; // Конец основного цикла // Выводим результат: S:= '1'; for i:= 2 to N do if i in PrimerSet then S := S+', '+IntToStr(i); mmOutput.Lines.Add(S) End; Перед тем как закончить рассмотрение множеств, полезно провести небольшой эксперимент. Измените описание типа SetOfNumber следующим образом: Type SetOfNumber = set of 1..1; и еще раз запустите программу из предыдущего примера. На экран будет выведено 1, 3, 5, 7 Множества BeginSet и PrimerSet состоят теперь из одного элемента, а программа сумела поместить в них не менее семи! Секрет этого прост: внутреннее устройство множества таково, что каждому его элементу ставится в соответствие один двоичный разряд (один бит); если элемент включен во множество, соответствующий разряд имеет значение 1, в противном случае - 0. В то же время минимальной единицей памяти является один байт, содержащий 8 бит, поэтому компилятор выделил множествам по одному байту, и в результате мощность каждого из них стала равна 8 элементам. Максимальная мощность множества - 256 элементов. Для таких множеств компилятор выделяет по 16 смежных байт. И еще один эксперимент: измените диапазон базового типа на 1..256. Хотя мощность этого типа составляет 256 элементов, при попытке компиляции программы компилятор сообщит об ошибке: Sets may have at most 256 elements (Множества могут иметь не более 256 элементов) т. к. нумерация элементов множества начинается с нуля независимо от объявленной в программе нижней границы. Компилятор разрешает использовать в качестве базового типа целочисленный тип-диапазон с минимальной границей 0 и максимальной 255 или любой перечисляемый тип не более чем с 256 элементами (максимальная мощность перечисляемого типа - 65536 элементов). СТРОКИ Для обработки текстов в Object Pascal используются следующие типы:
Общим для этих типов является то, что каждая строка трактуется как одномерный массив символов, количество символов в котором может меняться в работающей программе: для string [n] длина строки меняется от 0 до n, для string и pchar - от 0 до 2 Гбайт. В стандартном Паскале используются только короткие строки String [n]. В памяти такой строке выделяется n+i байт, первый байт содержит текущую длину строки, а сами символы располагаются начиная со 2-го по счету байта. Поскольку для длины строки в этом случае отводится один байт, максимальная длина короткой строки не может превышать 255 символов. Для объявления короткой строки максимальной длины предназначен стандартный тип ShortString (эквивалент String[255]). В Windows широко используются нуль-терминальные строки, представляющие собой цепочки символов, ограниченные символом #о. Максимальная длина такой строки лимитируется только доступной памятью и может быть очень большой. В 32-разрядных версиях Delphi введен новый тип string, сочетающий в себе удобства обоих типов. При работе с этим типом память выделяется по мере надобности (динамически) и ограничена имеющейся в распоряжении программы доступной памятью. Замечу, что в Delphi 1 тип string эквивалентен String [2 55], т. е. определяет короткую строку максимально возможной длины. Для совместимости с компонентами, основывающимися на OLE-технологии, в Delphi 32 введены также широкие строки, объявляемые стандартным типом wideString. По своим свойствам они идентичны длинным строкам string, но отличаются от них тем, что для представления каждого символа используются не один, а два байта. Примеры объявлений строковых типов: Var ssS: String[250];// Короткая строка длиной до 250 символов ssMax: ShortString;// Короткая строка длиной до 255 символов stS: String; // Длинная строка swS: WideString;// Широкая строка pcS: PChar; // Ссылка на нуль-терминальную строку acS: array [0..1000] of Char; // Нуль-терминальная строка // длиной до 1000 символов При объявлении переменной sss компилятор выделит для ее размещения 250 + 1 = 251 байт и поместит в первый байт 0 - текущую длину строки. При выполнении такого фрагмента программы: procedure TfmExample.bbRunClick(Sender: TObject); Var ssS: String[250]; Begin ssS:='Строка символов'; ssS[6] := ' и'; // Символы в строке нумеруются, начиная с 1 IbOutput.Caption := ssS; // Выводится “Строки символов” End; сначала в переменную ssS будет помещена цепочка символов строка символов, причем 1-й байт получит значение 15 (количество символов в строке). После выполнения второго оператора символ с индексом б (индексация байтов начинается с 0, но, поскольку первый байт содержит текущую длину, первый символ в строке имеет индекс 1) будет заменен на “и”, и в переменной окажется цепочка строки символов. Совершенно другим будет механизм работы с памятью при объявлении длинной строки sts: компилятор выделит для переменной 4 байта, достаточные для размещения номера той ячейки памяти, начиная с которой будет фактически располагаться символьная строка. Говорят, что sts ссылается на строку. Такого рода переменные-ссылки называются указателями и обсуждаются в гл. 9. При выполнении первого оператора такого обработчика: procedure TfmExample.bbRunClick(Sender: TObject); Var stS, stSS: String; Begin stS:='Строка символов'; stSS:= stS; stS:= 'Это - '+stS; stS[7]:= ' c'; // Символы в строке нумеруются, начиная с 1 IbOutput.Caption:= stS; //Выводится “Это - строка символов” End; программа (а не компилятор!) определит длину цепочки символов Строка символов, обратится к ядру перационной системы (ОС) с требованием выделить для нее участок памяти длиной 15+5=20 байт, поместит в переменную sts номер первого выделенного байта [ На самом деле в stS запоминается дескриптор выделенного участка памяти, см. гл. 9. ] и, начиная с него, разместит в этом участке цепочку символов, завершив ее терминальным нулем и 4-байтным счетчиком ссылок. Такое размещение на этапе прогона программы называется динамическим, в то время как размещение на этапе компиляции - статическим. Счетчик ссылок играет важную роль в механизме работы с памятью. С его помощью реализуется “кэширование” памяти: при выполнении оператора stSS:= stS; память для размещения значения переменной stSS не выделяется, в переменную stSS помещается содержимое указателя sts, а счетчик ссылок в связанной с ним памяти увеличивается на единицу. Таким образом, оба указателя будут ссылаться на одну и ту же область памяти, счетчик ссылок которой будет содержать значение 2. При выполнении оператора stS:= 'Это - '+stS; счетчик ссылок уменьшается на единицу, выделяется новая область памяти длиной 2 о + б = 2 б байт, указатель на эту область помещается в stS, а в саму память переписывается цепочка символов Это -строка символов, терминальный ноль и содержащий единицу счетчик ссылок. Теперь переменные stS и stss будут ссылаться на разные участки памяти, счетчики ссылок которых будут содержать по единице. Выделенная для размещения строки String область памяти освобождается, если ее счетчик ссылок стал равен нулю. Похожим образом осуществляется работа с памятью при объявлении переменной pcs типа pchar: компилятор считает эту переменную указателем и выделит для нее 4 байта:
procedure TfmExample.bbRunClick(Sender: TObject); Var pcS: PChar; Begin pcS:='Строка символов'; pcS[5]:= 'и'; {Символы в нуль-строке нумеруются,начиная с 0} IbOutput.Caption:= pcS; // Выводится “Строки символов” End; Программа потребует от ОС 15 + 1 = 16 байт, разместит в памяти цепочку символов и завершающий ее терминальный 0 и поместит адрес выделенного участка памяти в pcs. В стандартном паскале, при обращении к области памяти, на которую ссылается указатель, требуется за именем указателя ставить специальный символ.“^”. В Object Раsса1 интенсивно используется динамическая, память, и поэтому, это жесткое требование смягчено: в большинстве случаев (и при обращении к типу pchar в том числе) символ "^" ставить не следует. И, наконец, последнее объявление acs как массива символов. В Object Pascal считается совместимым с pchar одномерный массив символов с нулевой нижней границей. В отличие от pcs память для такой переменной выделяется статически (в нашем примере компилятор выделит в сегменте данных для переменной acs 1001 байт). Для размещения в acs нуль-терминальной цепочки символов используется процедура strcopy: procedure' TfmExample.bbRunClick(Sender: TObject); Var acS: array [0..1000] of Char; Begin StrCopy(acS,'Строка символов'); acS[5]:= 'и'; { Символы в нуль-строке нумеруются,начиная с 0} lbOutput.Caption:= acS; // Выводится “Строки символов” End; Необходимость в нуль-терминальных строках возникает только при прямом обращении к API-функциям ОС. При работе с компонентами Delphi в основном используются более удобные длинные строки, которые рассматриваются в п. 7.3.1. И несколько слов о широких строках, 32-разрядные версии Windows используют три сорта символов: однобайтный символ ANSI, двухбайтный символ и символ Unicode. Однобайтный символ связан с одним из 256 возможных значений, которые трактуются в зависимости от установленной в Windows национальной страницы (для размещения кириллицы используется страница 1251). 256 символов вполне достаточны для отображения национального алфавита любого европейского языка. Для отображения алфавитов некоторых азиатских языков этого недостаточно. В этом случае используется двухбайтный символ, в котором младший байт обычно кодируется семибитным ASCII-кодом, а старший указывает, как должен трактоваться этот код (каким символом он будет изображаться в документе или на экране). Символ Unicode в памяти занимает одно слово, которое имеет 65536 возможных значений. Специальная международная комиссия по Unicode выработала соглашение, позволяющее с помощью этого кода представить все символы всех языков мира. Двухбайтные символы и символы Unicode объявляются стандартным типом widecnar, а составленные из них строки - типом widestring. Все Windows-программы, использующие OLE-технологию обмена строками, должны кодировать символы в соответствии с Unicode. 7.3.1. Типы String и ShortString Несмотря на разницу во внутреннем представлении, короткие строки ShortString и длинные строки string имеют для программиста одинаковые свойства. Текущую длину строки можно получить с помощью функции Length. Например, следующий оператор уничтожает все ведомые (хвостовые) пробелы: while (Length(stS) о 0) and (stS[Length(stS)] = ' ') do SetLentgh(stS, Length (stS) - 1); В этом примере стандартная процедура setLength устанавливает новую длину строки. К строкам можно применять операцию “+” -сцепление, например: stS:= 'а' + 'b'; // stS содержит "ab" stS:= stS + ' с '; // stS содержит "abc" Если длина сцепленной строки превысит максимально допустимую длину N короткой строки, то “лишние” символы отбрасываются. Следующая программа, например, выведет символ “I”: Procedure TfmExamlpe.bbRunClick(Sender: TObject); Var ssS: String[1]; Begin ssS:= '123'; IbOutput := ssS; end; Операции отношения =, <>, >, <, >=, <= выполняются над двумя строками посимвольно, слева направо с учетом внутренней кодировки символов. Если одна строка меньше другой по длине, недостающие символы короткой строки заменяются значением #о. Следующие операции отношения дадут значение True: '''' < '.' 'А' > '1' 'Object' < ' Object Pascal' 'Пас' > 'Pascal' Все остальные действия над строками и символами реализуются с помощью описываемых ниже стандартных процедур и функций (в квадратных скобках указываются необязательные параметры). Таблица 7.7. Процедуры и функции для работы со строками
При преобразовании с помощью функций StrToxxx строка может содержать недопустимые для типа ххх символы. В этом случае возбуждается исключительная ситуация EConvertError. При обратных преобразованиях xxxToStr формат получаемой строки зависит от установленных в Windows системных параметров: разделителей даты, времени, целой и дробной частей вещественного числа. Обычно разделителем групп разрядов в русской языке принято считать пробел. Однако в русифицированном варианте Windows для этих целей на самом деле используется, не пробел, а символ-#160, внешне похожий на пробел Убедиться: в, этом можно с помощью такой несложной программы: procedure TfmExample.bbRunClick (Sender: TObject); var S: String; Begin S:=FloatToStrF(1000,ffNumber,4,0); EdOutput.Yext:=IntToStr(Ord(S[2])); End; Если вы действительно хотите использовать пробел, его нужно явно указать в окошке. Разделитель: групп разрядов (Пуск.| Настройка | Панель управления | Язык и стандарты | Числа) В Delphi 4...6 изменена функция StrToDate для того, чтобы упростить ввод двух цифр года с учетом смены столетия. С этой целью в модуле system введена глобальная переменная TwoDigitYearCenturywindow, которая определяет цифровой рубеж столетия. Если две цифры года больше или равны значению этой переменной, цифры года относятся к текущему столетию, если меньше - переносятся в следующее. Пусть, например, TwoDigitYearCenturywindow содержит значение 50. Тогда любые две цифры года в диапазоне 00..49 дополняются базой 2000 (2000, 2001,...,2049), в то время как цифры в диапазоне 50..99 дополняются базой 1900 (1950, 1951,...,1999). Такой прием позволяет в известной мере смягчить проблему двухцифровых годов на рубеже столетия, однако полным ее решением будет, разумеется переход на четырехцифровое представление года. По умолчанию TwoDigitYearCenturywindow имеет значение 0, и поэтому любые две цифры года дополняются базой 1900. Используемая в процедуре DateTimeToString и в функции FormatDateTime строка Format может содержать такие символы-спецификаторы (в примерах показаны строки для времени 19 часов 45 минут и даты 8 июня 1999 года): Таблица 7.8. Спецификаторы формата даты/времени
Замечу, что любые другие символы, указанные в строке Format, a также заключенные в апострофы или кавычки специальные символы-спецификаторы помещаются в выходную строку без преобразования, поэтому спецификаторы 'h час n мин' дадут строку 19 час 45 мин, а 'h час "n" мин' - 19час n мин. При форматном преобразовании времени-даты или других типов в строку и обратно могут пригодиться следующие системные переменные. Таблица 7.9. Системные переменные, управляющие стандартным отображением данных
Например, многие бухгалтерские программы в западных странах используют еженедельный отчет. В этом случае может пригодиться следующая подпрограмма, которая по заданной дате возвращает год, номер недели от его начала, дату понедельника и дату воскресенья: procedure WeekToDates(aDate: TDateTime; var Week: Byte; var Year: Word; var FirstDate, LastDate: TDateTime); {Возвращает для указанной даты aDate год Year, номер недели от начала года Week, а также даты начала и конца недели} var
|