Песни о Паскале
Шрифт:
Решето Эратосфена
Древние греки не знали, что они древние. И компьютеров тоже не знали, зато дышали бодрящим морским воздухом, коротая досуг в философских и математических размышлениях. Греческий досуг оказался не таким уж пустым, – иные задачки, придуманные под ласковый шепот волн, не решены по сию пору! Одна из них – вычисление простых чисел.
Прежде всего, выясним, что это за числа? Простым называют число, которое делится без остатка лишь на само себя и единицу. Все прочие числа являются составными.
1 2 3 4 5 6 7 8 9 10
Здесь отмечены составные числа 4, 6, 8, 9 и 10, – они делятся без остатка либо на 2, либо на 3. Оставшиеся числа 1, 2, 3, 5 и 7 являются простыми.
Кто-то из греков задался вопросом: можно ли вычислить очередное простое число, если известны все предыдущие? Например, исходя из того, что числа 1, 2, 3 и 5 простые, определить следующее простое число (7). Как ни мудрили мудрецы, такой формулы или алгоритма пока не придумали! Но усилия в этом направлении породили целые отрасли математики, – вот такой полезный неуспех!
Размышлял над задачей и грек Эратосфен. Он тоже не решил её, однако нашел остроумный способ отсеивать простые числа, не превышающие некоторого числа N. Вот суть его идеи.
Положим, мы ищем простые числа не превышающие 20. Выпишем на морском песочке в ряд числа с 1 до 20. Первые два числа – 1 и 2 – простые, их не тронем, а среди остальных сотрем каждое второе, то есть 4, 6, 8 и так далее.
Затем находим первое нестертое число – это три. Сотрем каждое третье после тройки: 6, 9, 12, 15 и 18 (хотя часть из них уже стерта, лишний раз это сделать не повредит). Повторяя процедуру, находим следующее нестертое число – это пять. Стираем каждое пятое после пятерки: 10, 15, 20 (хотя все они уже стерты). Достигнув середины этого списка – числа 11, остановимся. Дальше двигаться нет смысла, поскольку на песке остались лишь простые числа.
Примечание. Если говорить точнее, лучше остановиться на числе, которое составляет корень квадратный из числа N, в данном случае это 5. Но для упрощения задачи мы будем обрабатывать больше чисел – половину ряда.
Вот результат этой пляжной математики, где стираемые числа выделены, а стертые обозначены звездочками. Здесь хватило всего двух просевов.
1-й отсев чисел, кратных 2:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2-й отсев чисел, кратных 3:
1 2 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 *
Результат – простые числа:
1 2 3 * 5 * 7 * * * 11 * 13 * * * 17 * 19 *
А если бы Эратосфен жил в наше время? Стал бы он царапать на песке? Конечно, нет, – на что ж тогда компьютеры? Программа «P_38_4» находит все простые числа, не превышающие 255, – роль песка исполняет множество чисел.
program P_38_4; {
var Simples : set of byte; { множество чисел }
n, m : integer;
F : text;
begin
Assign(F, 'P_38_4.out'); Rewrite(F);
Simples:= [2..255]; { Сначала множество полное }
{ Цикл вычеркивания составных чисел }
for n:=2 to (255 div 2) do begin
{ если число ещё не вычеркнуто }
if n in Simples then
{ проверяем на кратность ему все последующие }
for m:=2*n to 255 do
{ если остаток(m/n) равен нулю, то m – составное }
if (m mod n)=0
{ и его надо вычеркнуть из множества}
then Simples:= Simples – [m];
end;
{ Распечатка множества простых чисел }
for n:=2 to 255 do if n in Simples then Writeln(F,n);
Close(F); Readln;
end.
Мелочь, а приятно
Одну из первых своих программ мы снабдили разумом попугая, научив повторять имя пользователя. После ввода имени в переменную S программа печатала.
Writeln (’Здравствуй, ’+ S);
Сделаем её чуть умнее, научив отличать мальчиков от девочек. По крайней мере, для русских имен. Русские женские имена оканчиваются на буквы «а» или «я» (Анна, Светлана, Мария и так далее), чего не скажешь о мужских. Последнюю букву имени можно «выдернуть» в символьную переменную C таким оператором.
C:= S[Length(S)];
И теперь приветствовать пользователя можно так:
if (C=’А’) or (C=’а’) or (C=’Я’) or (C=’я’)
then Writeln (’Здравствуй, девочка ’+ S)
else Writeln (’Здравствуй, мальчик ’+ S);
Здесь проверяется совпадение переменной C с буквами верхнего и нижнего регистров, поскольку нельзя предсказать, в каком регистре будет введено имя. Условный оператор выглядит громоздко, но, призвав на помощь множество, мы упростим его.
if C in [’А’, ’а’, ’Я’, ’я’]
then Writeln (’Здравствуй, девочка ’+ S)
else Writeln (’Здравствуй, мальчик ’+ S);
Переменную C проверяем на попадание в множество символов. Согласитесь, этот вариант читается приятней.
Итоги
Если вовремя смекнуть, что имеете дело с множествами, сложные задачи, как по волшебству, превратятся в простые!
А слабо?
А) Напишите программу для решения директорских задач и повторите подвиг контрразведчика. Или слабо?
Б) На острове действовали забавные законы по части транспортных средств – автобусов, грузовиков и легковушек. Во-первых, общее количество автомобилей на острове не должно было превышать 256. Автомобилям назначались номера с 0 до 255, при этом соблюдались следующие правила.