Программа

Program Problem2;

var

a, b, i : integer;

{---------------------------------------------------------------------------------}

Procedure to_square(n : integer);

label 1;

var

a, b, k : integer;

begin

a := 1; k := 1;

while a*a + 1 <= n do

begin

k := k + 1;

a := a + 1

end;

for a := 1 to k do

for b := 1 to a do

if a*a + b*b = n

then

begin

writeln(n, '=', a, '*', a, '+', b,'*', b); goto 1

end;

1: end;

{---------------------------------------------------------------------------------}

begin

write('Введите начало промежутка '); readln(a);

write('Введите конец промежутка '); readln(b);

write('Числа, которые можно представить в виде суммы ');

writeln('квадратов следующих чисел');

for i := a to b do to_square(i);

end.

Пример 18. Составить программу нахождения и вывода на экран всех простых чисел из заданного промежутка [n; m]. (Массивы не использовать.)

Следует сразу заметить, что эта задача решается иначе с помощью программы "Решето Эратосфена", но ее мы будем разбирать при изучении работы с массивами чисел и множествами.

А сейчас приведем другой вариант решения этой задачи. Ясно, что для ее решения нам потребуется процедура, которая устанавливает, является ли число простым. На предыдущих занятиях мы уже составляли такую программу. Сейчас вспомним ее работу и возможно внесем некоторые изменения.

Алгоритм составления процедуры такой.

Во-первых, вспомним, какие числа называются простыми.

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

Из их числа исключается число 1, которое не относится ни к простым, ни к составным.

Первое простое число - это 2. Если оно есть, тогда его сразу надо выводить на экран:

if p = 2 then write(p,' ')

Ясно, что все остальные четные числа являются составными, а значит их нет смысла проверять. Для исключения из рассмотренных четных чисел введем для проверки условный оператор:

else if p mod 2 <> 0 then

Если число нечетное, тогда его надо проверять. Сущность проверки будет заключаться в определении числа делителей. Но нам уже известен математический факт, что все делители некоторого натурального числа p находятся в промежутке от 1 до корня квадратного из этого числа (исключая само число). Значит, если имеются делители, в данном случае, от 3 до trunc(sqrt(p)), то оно является составным, а если таких делителей нет (четные числа мы уже исключили, а единицу и само число p не рассматриваем), тогда число будет простым.

Для проверки этого факта устроен следующий цикл:

begin

i := 3; k := 0;

while i <= trunc(sqrt(p)) do

begin

if p mod i = 0 then k := k + 1;

i := i + 2

end;

if k = 0 then write(p, ' ')

end

Полностью процедура, устанавливающая является ли число простым будет следующей (probleme number -простое число):

Procedure Probleme_number(p : integer);

var

i, k : integer;

begin

if p=2 then write(p, ' ') else if p mod 2<>0

then

begin

i := 3; k := 0;

while i<=trunc(sqrt(p)) do

begin

if p mod i = 0

then k := k + 1;

i := i + 2

end;

if k = 0 then write(p, ' ')

end

end;

Снова, эта процедура имеет только входной формальный параметр и не имеет выходных.

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

Program Problem3; { Простые числа из промежутка [n; m] }

var

n, m, i : integer;

{---------------------------------------------------------------------------------}

Procedure probleme_number(p : integer);

var

i, k : integer;

begin

if p=2 then write(p, ' ')

else if p mod 2 <> 0

then

begin

i := 3; k := 0;

while i <= trunc(sqrt(p)) do

begin

if p mod i = 0 then k := k + 1;

i := i + 2

end;

if k = 0 then write(p, ' ')

end

end;

{---------------------------------------------------------------------------------}

begin

write('Введите левую границу промежутка > 1 '); readln(n);

write('Введите правую границу промежутка '); readln(m);

writeln('Простые числа из промежутка [', n, ' ', m, ']');

for i := n to m do probleme_number(i);

writeln

end.

Пример 19. Нумерация книжных страниц. В книге n страниц. Составим программу, которая будет находить, сколько цифр понадобится для того, чтобы занумеровать все страницы книги.

Решение

Математическое решение рассмотрим на частном примере, а потом сделаем общий вывод.

Пусть нам требуется определить число цифр для нумерации 357 страниц.

Естественными рассуждения будут такими: однозначных цифр 9, значит они пронумеруют 9 страниц; двузначных чисел 90 - они нумеруют 90 страниц и используют 90 ^. 2 = 180 цифр; трехзначных чисел 900 - они пронумеруют 900 страниц и используют 2700 цифр. Следовательно, для нумерации данных 357 страниц потребуются все однозначные и двузначные числа и часть трехзначных. Чтобы узнать, сколько трехзначных чисел потребуется для нумерации, надо из заданного числа вычесть "использованные" однозначные и двузначные числа: 357 - (9 + 90) = 258.

Итак, всего потребуется цифр:

. . . . . . . . . . .

Итого: 9 + 180 + 774 = 963 цифры.

Теперь обобщим наши соображения. Пусть задано число страниц n, которое имеет c цифр. Тогда для нумерации потребуются цифры:

1 - значные; потребуется: 9 1 = 9 цифр;

2 - значные; 90 2 = 180 цифр;

3^х - значные; 9003 = 2700 цифр;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

c-1 -значные; 9....0 ^. (c-1) . . . цифр,

а c-значных полностью не хватит, также, как не хватило полностью трехзначных для нумерации 357 страниц.

Чтобы узнать сколько потребуется c-значных цифр, надо из данного числа вычесть все число одно, -дву, -трех,- и т. д., c-1 значные, которые уже использованы: а затем полученный результат умножить на c - значность числа. Сложив израсходованные цифры, мы получим окончательный результат.

Попробуем на основе этих рассуждений составить программу.

Прежде, составим процедуру, которая определяет число цифр во введенном числе страниц. С такой программой мы уже раньше имели дело:

Procedure number(n : integer; var k : integer);

begin

k := 0;

repeat

k := k + 1;

n := n div 10

until n = 0

end;

В следующей процедуре будет находиться искомое число цифр. В ней, переменная m будет служить для указания числа цифр в одно, - двух, - трех, ... c-значных числах (9, 90, 900, ..., 9...0).

Переменная c покажет число цифр в числе - номере страницы, в переменной z будет накапливаться искомый результат, а сумма s даст нам сколько всего n-значных чисел было использовано для подсчета.

Первоначальные значения: m := 9; z := 0; s := 0, а число цифр числа будет получено из процедуры number(n, c) и задаст значение переменной c:

m := 9; number(n, c); z := 0; s := 0;

Теперь организуем цикл по количеству цифр введенного числа страниц, от 1 до c - 1. Переменная цикла i.

for i := 1 to c - 1 do

begin

z := z + m*i; {Сумма цифр}

s := s + m;

m := m*10

end;

В цикле подсчитывается сумма цифр (z := z + m*i), сумма использованных однозначных, двузначных и т.д. цифр.

После завершения цикла, к сумме z добавляются оставшиеся c-значные цифры:

z := z + (n - s) c {n - s оставшиеся страницы c-значными}

{цифрами}

Процедура

Procedure Page(n : integer; var z : integer);

var

i, m, c, s : integer;

begin

m := 9;

number(n, c); z := 0; s := 0;

for i := 1 to c - 1 do

begin

z := z + m*i; {Сумма цифр}

s := s + m;

m := m*10

end;

z := z + (n - s)*c

end;

И, наконец, полностью программа

Program Problem7; { Число цифр для нумерации страниц }

var

n, c : integer;

{---------------------------------------------------------------------------------}

Procedure number(n : integer; var k : integer);

begin

k := 0;

repeat

k := k + 1; n := n div 10

until n = 0

end;

{---------------------------------------------------------------------------------}

Procedure Page(n : integer; var z : integer);

var

i, m, c, s : integer;

begin

m := 9; number(n, c); z := 0; s := 0;

for i := 1 to c - 1 do

begin

z := z + m*i; {Сумма цифр}

s := s + m; m := m*10

end;

z := z + (n - s)*c {n - s оставшиеся страницы c-значными цифрами}

end;

{---------------------------------------------------------------------------------}

begin

write('Введите число страниц '); readln(n);

page(n, c);

writeln('Число цифр, необходимых для нумерации ', c)

end.

Пример 20. Счастливые автобусные билеты.

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

3 + 5 + 6 = 4 + 2 + 8 =14.

Будем считать, что номера билетов принадлежат промежутку

[100000; 999999].

Составить программу определения счастливого билета.

Алгоритм

Для программы составим две процедуры: одна - определяющая сумму цифр введенного числа, уже известную нам (sum number - сумма цифр):

Procedure sum_number(p : longint; var s : longint);

begin

s := 0;

while p <> 0 do

begin

s := s + p mod 10;

p := p div 10

end

end;

вторую - отделяющую первые и последние три цифры, а затем, с помощью вызова процедуры sum_number, устанавливает равны ли эти суммы (happiness - счастье):

Procedure happiness(x : longint);

var

l, r : longint;

begin

sum_number(x mod 1000, l);

sum_number(x div 1000, r);

if l = r then write(x,' ')

end;

x mod 1000 - отделяет последнее трехзначное число, а x div 1000 - первое трехзначное число.