Учебная программа PRIMSET
В следующем примере, иллюстрирующем приемы работы с множествами, реализуется алгоритм выделения из первой сотни натуральных чисел всех простых чисел[ Простыми называются целые числа, которые не делятся без остатка на любые другие целые числа, кроме 1 и самого себя. К простым относятся 1, 2, 3, 5, 7, 11, 13 и т. д.. ]. В его основе лежит прием, известный под названием "решето Эратосфена". В соответствии с этим алгоритмом вначале формируется множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до N. В множество primerset (оно будет содержать искомые простые числа) помещается 1. Затем циклически повторяются следующие действия:
взять из BeginSet первое входящее в него число Next и поместить его В PrimerSet;
удалить из BeginSet число Next и все другие числа, кратные ему, Т. е. 2*Next, 3*Next И Т.Д.
Цикл повторяется до тех пор, пока множество BeginSet не станет пустым.
Эту программу нельзя использовать для произвольного N, так как в любом множестве не может быть больше 256 элементов.
|
Code: |
|
procedure TfmExample.bbRunClick(Sender: TObject); // Выделение всех простых чисел из первых N целых const N = 255; // Количество элементов исходного множества type SetOfNumber = setof1..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 := 2to N do if i in PrimerSet then S := S+', '+IntToStr(i); mmOutput.Lines.Add(S) end; |
Перед тем как закончить рассмотрение множеств, полезно провести небольшой эксперимент. Измените описание типа SetOfNumber следующим образом:
|
Code: |
|
type SetOfNumber = setof1..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 элементов).
- << Назад
- Вперёд
Просьба писать ваши замечания, наблюдения и все остальное,
что поможет улучшить предоставляемую информацию на этом сайте.
ВСЕ КОММЕНТАРИИ МОДЕРИРУЮТСЯ ВРУЧНУЮ, ТАК ЧТО СПАМИТЬ БЕСПОЛЕЗНО!