Поиск чисел без одинаковых цифр

Последовательность чисел в порядке убывания

В последовательности натуральных чисел i (i<256) определить число различных чисел и вывести их в порядке убывания. Признаком конца последовательности служит число 0.

В программе определяется тип данных set_byte как множество целых чисел из интервала от 0 до 255. Описывается переменная типа множества Z. До просмотра последовательности чисел множество Z пусто.

Будем просматривать последовательность, и формировать множество чисел Z, входящих в эту последовательность. Для того чтобы вывести элементы множества в порядке убывания используется оператор цикла с убывающим параметром. Для каждого значения параметра цикла проверяется, содержится ли это значение в сформированном множестве чисел Z.

Программа, формирующая требуемое множество чисел, представлена в листинге 10.1.

Числа в порядке убывания

Program p10_1;

type set_byte=set of byte;

var z: set_byte; {множество чисел}

m:byte; {очередное число последовательности}

k: integer;{число различных элементов}

begin writeln('Введите элементы последовательности:');

read(m); {прочли первый элемент}

z:=[]; {до просмотра множество пусто}

while m <>0 do

begin z:= z+[m];

{добавление элемента в множество}

read(m) {чтение очередного числа}

End;

k:=0;

writeln('Последовательность в порядке убывания:');

for m:= 255 downto 1 do

if m in z then begin write(m,' '); inc(k) end;

Writeln;

writeln('Количество различных элементов: ',k)

End.

Если во входном потоке содержится последовательность чисел 15 3 18 20 4 2 8 3 2 0, то в результате работы программы будет выведены сообщения, представленные в листинге 10.1a.

Результат работы программы

Числа в порядке убывания:

20 18 15 8 4 3 2

Количество различных чисел последовательности: 7

Проверка идентификатора

Дана непустая последовательность символов, ограниченная справа пробелом. Требуется написать программу, которая определяет, является ли последовательность идентификатором.

В разных языках программирования даются различные определения идентификатора. В некоторых языках разрешено использовать буквы латинского алфавита, и цифры, причем последовательность, задающая идентификатор, должна начинаться с буквы. Иногда при выборе идентификатора разрешается использовать некоторые специальные символы, например, символ подчеркивания.

Как правило, пробелов в идентификаторе не должно встречаться, хотя в некоторых системах программирования было разрешено использование в идентификаторах символа пробел. Иногда разрешалось использовать буквы русского алфавита. Поэтому при исследовании, является ли последовательность идентификатором, требуется уточнить понятие идентификатора.

Будем считать, что идентификатор – это последовательность букв и цифр, начинающаяся с буквы, причем буквы только латинского алфавита, как строчные, так и прописные.

При решении задачи будем использовать три множества: множество букв, множество цифр, и множество букв и цифр. Проверим отдельно первый символ. Он должен быть буквой. Далее в цикле будем последовательно анализировать символы. Каждый символ, начиная со второго должен быть либо буквой латинского алфавита, либо цифрой. Если это не так, то рассматриваемая последовательность не является идентификатором, просмотр последовательности следует прекратить. Текст программы представлен в листинге 10.2.

Последовательность символов – идентификатор

{программа проверяет, является ли последовательность символов идентификатором. Идентификатор - последовательность букв и цифр, начинающаяся с буквы. разрешено использовать латинские буквы, как прописные, так и строчные. Последовательность символов должна заканчиваться символом пробел}

Program p10_2;

type Set_let = set of char; {множество символов}

var let, {буквы латинского алфавита, прописные и строчные}

sg,{множество цифр}

all: set_let;{буквы и цифры}

c: char; {очередной символ}

sh: boolean; {результат проверки}

begin {формирование множеств}

let:=['A'..'Z','a'..'z'];

sg:= ['0'..'9'];

all:= let+sg;

writeln('Введите последовательность символов:');

read (c); {чтение первого символа}

sh:= c in let;

read (c); {чтение второго символа}

while (c <> ' ') and sh do

begin sh:= c in all;

Read (c)

End;

If sh then

writeln('Последовательность - идентификатор')

Else

writeln ('Последовательность не идентификатор')

End.

Поиск простых чисел

Рассмотрим решение следующей задачи. Требуется найти все простые числа, не превышающие заданного натурального числа N. Можно предложить алгоритм, в котором все числа перебираются по очереди и для каждого из чисел производится проверка, является ли оно простым.

Однако уже в Древней Греции был известен более эффективный алгоритм, получивший название ”решета Эратосфена”. Согласно этому алгоритму сначала рассматривается множество всех чисел от 2 до N, а затем из него последовательно удаляются элементы, не являющиеся простыми числами.

Для этого на каждом шаге алгоритма выбирается наименьший элемент множества, и вычеркиваются из множества все элементы кратные выбранному элементу. Сам элемент является простым числом и в дальнейшем не рассматривается. Будем считать, что в программе определен тип множества resheto и переменная типа множества simple (листинг 10.3a)

Описание формируемого множества

сonst N = 255;

type resheto = set of 2..N;

var simple: resheto; {Формируемое множество}

После выполнения оператора присваивания simple:=[2..N] переменная simple содержит множество целых значений из диапазона 2..N. Выбираем из этого множества наименьшее простое число К. Очевидно, что первым выбранным числом будет число 2.

Далее исключаем из этого множества все числа кратные двум. Во время работы цикла в множествеsimple содержатся все простые числа, не превосходящие К, а среди элементов, больших К содержатся все числа, кроме кратных этим простым числам.

Когда К пробежит значения до SQRT(N+1) в множестве simple останутся лишь простые числа. Программа, представленная в листинге 10.3, реализует описанный алгоритм.

Решето Эратосфена

{Программа находит простые числа, не превышающие заданного значения. Реализован алгоритм, называемый "Решето Эратосфена". Для представления данных используется множество.}

Program p10_3;

const n = 40; {верхняя граница интервала целых чисел}

type resheto = set of 2..n;

var simple: resheto;{формируемое множество}

i, { числа, кратные очередному простому числу}

k, {наименьшее простое число в формируемом множестве}

l: integer; { верхняя граница для делителей n}

Begin writeln;

writeln ('Простые числа, не превышающие ',n, ' ');

simple:=[2..n];

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

l:= trunc(sqrt(n+1));

k:= 1;

while k <= l do

begin repeat k:= k+1 until k in simple;

{поиск наименьшего простого числа рассматриваемого множества}

write(k:3,' ');

for i:= 2 to n div k do

{исключение из множества чисел,

которые кратны наименьшему простому числу k}

simple:= simple - [k*i]

End;

for k:= k+1 to n do

if k in simple then write(k:3,' ')

End.

Если в качестве константы n взять число 40, то в результате работы программы будет выведено сообщение:

Простые числа меньшие 40: 2 3 5 7 11 13 17 19 23 29 31 37.

Поиск чисел без одинаковых цифр

Напишем программу, которая определяет в заданном интервале все числа, в десятичной записи которых нет одинаковых цифр. В листинге 10.4 представлена программа, решающая задачу.

Числа с разными цифрами из заданного диапазона

{программа находит числа из заданного интервала, в десятичной записи которых нет одинаковых цифр.}

Program p10_4;

var m, {нижняя граница интервала поиска}

n: word; {верхняя граница интервала поиска}

i: integer; {очередное число из интервала}

l: boolean; {результат проверки}

{функция eqf выдает значение false, если все цифры числа различны}

function eqf (n: word): boolean;

var p, s, q: word;

z: set of 0..9; {множество чисел от 0 до 9}

begin p:= n;{рассматриваемое число}

eqf:= false;

z:=[]; {множество, соответствующее числам из записи числа}

while p <> 0 do

begin s:= p div 10; {частное}

q:= p-s*10; {число, соответствующее последней цифре}

if q in z then begin eqf:= true; exit end

else z:= z+[q];

p:= s

End;

End;

Begin writeln;

writeln ('Введите интервал значений:'); readln(m,n);

writeln('Числа, в записи которых нет одинаковых цифр: ');

l:= false;

for i:= m to n do

If not eqf(i)

then begin write(i,' '); l:= true end;

if not l then writeln('нет таких чисел')

End.

Поверяются все числа из заданного пользователем интервала. Для каждого из чисел строится множество цифр, из которых состоит это число. При этом в цикле от числа “отделяется” по младшей цифре, и проверяется, встречалась ли ранее эта цифра в записи числа. Если цифра уже встречалась, то в числе есть одинаковые цифры, и анализ числа следует прекратить.

Если в качестве входных данных программы задается интервал 332 и 345, то в результате работы программы будет выведено:

Числа, в записи которых нет одинаковых цифр: 340 341 342 345.

Поиск уникальных символов

Напишем программу, которая определяет, какие из символов заданного текста являются уникальными, т.е. встречаются в тексте лишь один раз. Для решения задачи удобно использовать множества символов.

При анализе текста будем формировать два множества, в множество M включим все символы, которые встречались в тексте хотя бы раз, в множество MM включим символы, которые встречались в тексте более одного раза. Разность множеств M и MM является множеством символов, которые входят в текст только один раз, т.е. множеством уникальных символов. В программе для обозначения уникального множества используется переменная M1.

Первоначально множества пусты, после просмотра текста нужное нам множество символов (M1) получается как разность множеств M и MM.

Для того чтобы вывести результаты необходимо перебирать все символы и для каждого символа проверять, принадлежит ли он множеству. В листинге 10.5 приведена программа, реализующая описанный алгоритм.

Поиск уникальных символов

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

Program p10_5;

type set_let = set of char;

var m1,{множество символов, встречающихся в тексте только один раз}

m, {множество символов, встречающихся в тексте}

Mm: set_let;

{множество символов, встречающихся в тексте более одного раза}

s: string; {исходный текст}

c: char; {очередной символ}

i: byte; {символ при формировании вывода элементов множества}

Begin

writeln('Введите строку символов:');

Readln(s);

{инициализация множеств}

m:=[]; mm:=[];

for i:= 1 to length(s)

do begin c:= s[i];

If c in m

then {символ ранее уже встречался}

mm:= mm+[c]

else {символ встретился впервые}

m:= m+[c]

End;

m1:= m-mm; {построение множества уникальных символов}

writeln('Множество уникальных символов:');

if m1 = [] then writeln ('пусто')

Else

for c:= chr(0) to chr (255)

do if c in m1 then write(c,' ');

Writeln;

End.

Анализ двух текстов

Напишем программу, которая проверяет, состоят ли два заданных текста из одинаковых символов. В программе опишем процедуру, которая по заданной строке s формирует множество символов m, из которых эта строка состоит. Текст процедуры содержится в листинге 10.6.

Процедура формирования множества символов, встречающихся в тексте

procedure settex (var s: string; var m: set_let);

var i: byte;

begin m:=[];

for i:= 1 to length (s) do

m:= m + [s[i]]

End

Для решения задачи нам достаточно по каждому из текстов построить соответствующее множество, и затем эти два множества сравнить. Полностью написать программу предлагается читателю в качестве упражнения.

Рассмотрим еще одну задачу, в которой требуется проанализировать текст. Предположим, что нас в тексте интересуют только буквы.

Выделение из текста букв

Напишем программу, которая по заданному тексту формирует множество букв, которые в тексте встречаются, причем требуется отдельно сформировать буквы латинского и русского алфавитов.

При анализе текста сформируем множество различных символов, входящих в текст, а затем с помощью операции пересечения множеств выделим соответствующие множества. Пусть в программе переменная mlat - множество букв латинского алфавита, mrus - русского, m - множество различных символов текста. Для того, чтобы определить множество букв, встречающихся в тексте, достаточно сформировать множество m*(mrus+mlat). Приведем программу, решающую задачу, в листинге 10.7.

Формирование букв русского и латинского алфавитов

Program p10_7;

type set_let = set of char;

var mlat, {множество букв латинского алфавита}

mrus, {множество букв русского алфавита}

m: set_let;{множество символов текста}

s: string; {исходная строка}

c: char; {очередной символ текста}

{формирование множества символов строки}

procedure settex (var s: string; var m: set_let);

var i: byte;

begin m:=[];

for i:= 1 to length (s) do m:= m + [s[i]]

End;

Begin

mlat:= ['A'..'Z','a'..'z'];

mrus:= ['А'..'Я','а'..'я'];

writeln; writeln('Введите текст:'); readln(s);

Settex(s,m);

writeln('Множество символов текста:');

for c:= chr(0) to chr (255) do