Иллюстрированный самоучитель по Tirbo Pascal


Множества - часть 3


  • взять из BEGINSET первое входящее в него число NEXT и поместить его в PRIMERSET;
  • удалить из BEGINSET число NEXT и все другие числа, кратные ему, т.е.2*NEXT, 3*NEXT и т.д. 

Цикл повторяется до тех пор, пока множество BEGINSET не станет пустым.

Эту программу нельзя использовать для произвольного N, так как в любом множестве не может быть больше 256 элементов.

Пример 4.1

Program Primer_numbers_detect;

{Выделение всех простых чисел из первых N целых}

const

N = 255; {Количество элементов исходного множества}

type

SetOfNumber = set of 1..N;

var

n1,next,i : Word; {Вспомогательные переменные} 

BeginSet, {Исходное множество} 

PrimerSet : SetOfNumber; {Множество простых чисел} .

begin

BeginSet := [2. .N] ; {Создаем исходное множество}

PrimerSet:= [1]; {Первое простое число} 

next:= 2; {Следующее простое число}

while BeginSet <> [] do {Начало основного цикла} 

begin

n1 := next;{n1-число,кратное очередному простому (next)} 

{Цикл удаления из исходного множества непростых чисел:} 

while n1 <= N do 

begin

Exclude(BeginSet,nl);

n1 := n1+next {Следующее кратное} 

end; {Конец цикла удаления} 

Include(PrimerSet,next);

{Получаем следующее простое, которое есть первое невычеркнутое из исходного множества} 

repeat

inc(next)

until (next in BeginSet) or (next > N) 

end; {Конец основного цикла} 

{Выводим результат:} 

for i := 1 to N do

if i in PrimerSet then Write(i:8); 

WriteLn 

END.

Перед тем как закончить рассмотрение множеств полезно провести небольшой эксперимент. Измените описание типа SETOFNUMBER следующим образом:

type

SetOf Number = set of 1. . 1 ;

и еще раз запустите программу из предыдущего примера. На экран будет выведено

1   3   5   7

Множества BeginSet и PrimerSet состоят теперь из одного элемента, а программа сумела поместить в них не менее семи! Секрет этого прост: внутреннее устройство множества таково, что каждому его элементу ставится в соответствие один двоичный разряд (один бит); если элемент включен во множество, соответствующий разряд имеет значение 1, в противном случае - 0. Минимальной единицей памяти является один байт, содержащий 8 бит. Компилятор выделил множествам по одному байту, в результате мощность каждого из них стала равна 8 элементов. Максимальная мощность множества - 256 элементов. Для таких множеств компилятор выделяет по 16 смежных байт.

И еще один эксперимент: измените диапазон базового типа на 1.256. Хотя мощность этого типа составляет 256 элементов, при попытке компиляции программы компилятор сообщит:

Error 23: Set base type out of range.

(Ошибка 23: Базовый тип множества выходит за допустимые

границы.)

Компилятор разрешает использовать в качестве базового типа целочисленный тип-диапазон с минимальной границей 0 и максимальной 255 или любой перечисляемый тип не более чем с 256 элементами (максимальная мощность перечисляемого типа -5536 элементов).




- Начало -  - Назад -  - Вперед -