Основы алгоритмизации и программирования. Часть третья. Структурированные типы данных. Асламова В.С - 37 стр.

UptoLike

ВУЗ: 

АГТА | Ангарск

Составители: 

Рубрика: 

73
Пример 19:
Поиск простых чисел с помощью решета Эратосфена.
Суть этого метода в следующем: следует из ряда натуральных чисел,
начиная с j>2 удалить все числа кратные 2 (это каждое второе число),
начиная j>3 удалить все числа кратные 3 (это каждое третье число) и т.д. В
результате в ряду останутся только простые числа. Решить эту задачу,
используя множество.
Обозначение: MN – исходное множество,
PR - результирующее множество простых чисел,
N - максимальное количество перебираемых простых чисел.
const N=255;
var MN,PR:set of 1..N;
i:byte; j:word;
begin
MN:=[2..N]; i:=1; PR:=[1];
repeat
while not (i in MN) do i:=i+1; {поиск в множестве наименьшего
простого числа}
PR:=PR+[i]; {помещаем простое число во множество PR }
j:=i
while j<=N do begin
MN:=MN-[j]; {удаляем из множества все числа кратные i}
j:=j+i end;
until MN:=[ ]; writeln(′простые числа:′);
for i:=1 to N do
if i in PR then write(i:4); writeln;
end.
Результат работы программы:
1 2 3 5 7 11 13 17 19 23 29 31 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113 127 131 136 149 151 157
163 167 173 181 191 193 197 211 223 227 229 233 239 241 251
74
Рис.10. Блок-схема примера 19
Тип данных “множество” особенно удобен для проверки однотипных
условий, которые часто вырождаются в сложные операторы if.
удаление из
множества всех
чисел кратных i
N=255
i не в
MN
начало
д
а
нет
MN:=[2..N];
i:=1; PR:=[1]
д
а
нет
д
а
нет
i:=i+1
MN:=MN-[j];
j:=j+i
j<=N
Печать
′Простые числа′
Печать i
нет
i in PR
i:=1
,
N
запись
простого числа
в множество
PR
поиск в MN
наименьшего
простого числа
PR:=PR+[i];
j:=i
Перевод
курсора
коне
ц
MN:=[ ]
д
а
        Пример 19:
                                                                                                                                                  удаление из
      Поиск простых чисел с помощью решета Эратосфена.                                  начало                                                    множества всех
      Суть этого метода в следующем: следует из ряда натуральных чисел,                                                                           чисел кратных i
начиная с j>2 удалить все числа кратные 2 (это каждое второе число),                    N=255
                                                                                                                                                        нет
начиная j>3 удалить все числа кратные 3 (это каждое третье число) и т.д. В                                                               j<=N
результате в ряду останутся только простые числа. Решить эту задачу,                 MN:=[2..N];
                                                                                     i:=1; PR:=[1]                                           да
используя множество.                                                                                       поиск в MN
                                                                                                           наименьшего                MN:=MN-[j];
      Обозначение: MN – исходное множество,
                                                                                                           простого числа               j:=j+i
      PR - результирующее множество простых чисел,
      N - максимальное количество перебираемых простых чисел.                           i не в       нет
       const N=255;                                                                      MN                                     нет
                                                                                                                                        MN:=[ ]
      var MN,PR:set of 1..N;                                                                да
      i:byte; j:word;                                                                                                                        да
                                                                                        i:=i+1             запись
      begin                                                                                                простого числа             Печать
         MN:=[2..N]; i:=1; PR:=[1];                                                                        в множество            ′Простые числа′
         repeat                                                                     PR:=PR+[i];            PR
         while not (i in MN) do i:=i+1;       {поиск в множестве наименьшего            j:=i                                            i:=1,N
                                               простого числа}
                                                                                                                                нет
         PR:=PR+[i];               {помещаем простое число во множество PR }                                                            i in PR
         j:=i
                                                                                                                                             да
         while j<=N do begin
                                                                                                                                        Печать i
            MN:=MN-[j]; {удаляем из множества все числа кратные i}
            j:=j+i end;
         until MN:=[ ]; writeln(′простые числа:′);
                                                                                                                                        Перевод
         for i:=1 to N do                                                                                                               курсора
         if i in PR then write(i:4); writeln;
      end.                                                                                                                               конец

       Результат работы программы:
 1 2 3 5 7 11 13 17 19 23 29 31 41 43 47 53 59 61 67 71                                                      Рис.10. Блок-схема примера 19
 73 79 83 89 97 101 103 107 109 113 127 131 136 149 151 157
 163 167 173 181 191 193 197 211 223 227 229 233 239 241 251
                                                                                     Тип данных “множество” особенно удобен для проверки однотипных
                                                                               условий, которые часто вырождаются в сложные операторы if.




                                    73                                                                                74

Страницы