Цикл с последующим условием

Цель: дать понятие о циклах с постусловием, блок-схемах, изображающих такие циклы. Учить на частных примерах составлять блок-схемы и программы с циклами; дать понятие о различиях между циклами с предусловием и постусловием; учить в одной программе использовать разные циклы, если программа содержит несколько циклов; вводить и выполнять программы, используя компиляторы BPW или Turbo Pascal.

1. Цикл с последующим условием

 

Оператор цикла с последующим условием (постусловием) похож на оператор цикла с предусловием, но условие вычисляется и проверяется после выполнения операторов, составляющих тело цикла.
Общий вид оператора цикла с постусловием такой:
repeat
s1; s2; s3; ... sn
until <условие>,
где s1, s2, s3, ..., sn - операторы тела цикла; <условие> - логическое выражение.
Переводится: repeat - повторять, until - до тех пор пока.
Схематически цикл repeat можно изобразить так (см. рис. 1):


Рис. 22

Как видите, такой цикл начинается с выполнения операторов внутри цикла, а уже затем вычисляется выражение, записанное в условии.
Если значение этого выражения истинно, тогда осуществляется выход из цикла, если значение ложно, то цикл продолжается и снова выполняются операторы s1; s2; s3; ... .
Надо сразу заметить, что в отличии от цикла while ... do, в цикле repeat ... until ... операторные скобки begin ... end могут не использоваться, хотя и использование их вреда не принесет. Можно сказать другими словами, что оператор цикла repeat ... until. ... не требует операторных скобок begin ... end.
Рассмотрим работу этого оператора на примере.

Пример 1. Найти наименьшее натуральное число, дающее при делении на 2, 3, 4, 5, 6 соответственно остатки 1, 2, 3, 4, 5.

Задачу будем решать так: берется наименьшее натуральное число - единица и находятся остатки от деления его на 2, 3, 4, 5 и 6; если остатки будут равны 1, 2, 3, 4 и 5, тогда это число является искомым, его надо выдать на экран и закончить программу, в противном случае, надо брать следующее натуральное число - 2 и проверять его, и так далее.

Блок-схема


Рис. 23

Программа

Program Problem1;
uses WinCrt;
var
n : integer;
begin
n := 0;
repeat
n := n + 1;
until (n mod 2 = 1) and (n mod 3 = 2) and (n mod 4 = 3) and
                   (n mod 5 = 4) and (n mod 6 = 5);
writeln("Искомое целое число ", n)
end.

Еще один пример, который демонстрирует работу цикла с постусловием.

Пример 2. Числа, одинаково читающиеся и слева направо, и справа налево, называются палиндромами. Например, числа 42324 или 1331 - палиндромы. Составьте программу, которая будет находить числа - палиндромы из заданного промежутка.

Логика составления программы такова.
Переставить цифры в числе и сравнить полученное число с заданным.
Раньше уже составлялась программа перестановки цифр числа, которая была выполнена с помощью цикла с предусловием
while ... do ...
Как будет построена часть программы о перестановки цифр с помощью цикла
repeat ... until ...
Пусть заданное число a, тогда введем еще одну переменную b, которой будет присвоено значение переменной a (для чего это делается вы узнаете позже): b := a;
Заведем еще одну переменную a1 для нового числа, в котором цифры уже будут переставлены.
Первоначальное значение этой переменной - ноль: a1 := 0;
Почему значение этой переменной равно нулю станет ясно из программы.
Далее организуем цикл repeat, в котором будет происходить перестановка цифр числа b:
repeat
a1 := a1*10 + b mod 10;
b := b div 10
until b = 0;

Итак, в цикле, также как и в цикле while ... do ..., отделяется последняя цифра:
b mod 10; (например, 343 mod 10 = 3); переменной a1 присваивается значение:
a1 := a1*10 + b mod 10; 0 * 10 + 3 =3;
"отбрасывается" последняя цифра заданного числа с помощью операции целочисленного деления:
b := b div 10; 343 div 10 = 34;
проверяется условие: b = 0, 34 = 0, условие не выполняется, значит цикл продолжается.
Отделяется последняя цифра уже нового числа:
b mod 10 = 34 mod 10;
новое число a1, уже равное 3, умножается на 10 и к результату прибавляется следующая цифра - 4:
a1 := a1*10 + b mod 10;
"отбрасывается" последняя цифра числа b:
b := b div 10 ; 34 div 10 = 3;
проверяется условие: b = 0, 3 = 0; условие не выполняется, значит цикл продолжается.
Отделяется последняя цифра числа:
b mod 10 ; 3 mod 10 = 3;
формируется новое число:
a1 := a1*10 + b mod 10 ; 34 * 10 + 3 = 343;
"отбрасывается" последняя цифра числа и получается новое число:
b := b div 10 ; 3 div 10 = 0;
проверяется условие: b = 0, 0 = 0; условие выполняется, значит цикл заканчивается.
Теперь становится ясно, почему введена другая переменная b для заданного числа, ее значение в цикле меняется от начального до нуля и, чтобы сохранить заданное число в переменной a, и вводится, так сказать, "рабочая" переменная - b.
После окончания цикла перестановки цифр числа, сравнивается первоначальное число, которое "сохранилось" в переменной a и число, которое получилось после перестановки цифр и "накопилось" в переменной a1.
Если a = a1, тогда значение a выдается на экран, так как это число является палиндромом.
Далее, значение a увеличивается на 1, т. е. берется для рассмотрения следующее по порядку натуральное число и снова продолжается внешний цикл. Цифры числа переставляются, полученное новое число после перестановки цифр - a1, сравнивается с первоначальным a и так далее.
Внешний цикл заканчивается, когда значение a становится равным правой границе интервала - n.
          Блок-схема


       Рис. 24

Программа

Program Problem2;
uses WinCrt;
var
m, n, a, b, a1 : longint;
begin
write("Введите левую границу промежутка "); readln(m);
write("Введите правую границу промежутка "); readln(n);
a := m;
writeln("Числа палиндромы из [", m, ";", n, "]");
repeat
b := a; a1 := 0;
repeat
a1 := a1*10 + b mod 10;
b := b div 10
until b=0;
if a1 = a then write(a, " ");
a := a + 1
until a > n;
end.

Программы, составленные с циклом с предусловием (while ... do...), легко можно переделать с циклом с постусловием (repeat ... until ...) и они будут такими:

Блок-схема и программа, подсчитывающая сумму цифр числа


Рис. 25
Program Sum; { Сумма цифр числа }
uses WinCrt;
var
n, s, a : integer;
begin
write("Введите целое число "); readln(n);
a := n; s := 0;
repeat
s := s + n mod 10;
n := n div 10
until n = 0;
writeln("Сумма цифр числа ", a, " равна ", s)
end.

Программа перестановки первой и последней цифр в числе:

Program Transpose;
uses WinCrt;
var
n, n1, p, a, i : longint;
begin
write("Введите натуральное число n "); readln(n);
a := n; i := 1;
p := n mod 10; {последняя цифра введенного числа}
repeat
i := i*10; n := n div 10
until n<10;
n1 := a - n*i - p + n + p*i;
writeln("Число после перестановки цифр ", n1)
end.

2. Различия между циклом - while и циклом - repeat

 

1. Оператор, находящийся в цикле while, повторяется до тех пор, пока условие удовлетворено (т.е. истинно). Последовательность операторов, находящихся в цикле repeat, повторяется до тех пор, пока условие не удовлетворено (т. е. ложно).
Следовательно, в цикле while используется условие продолжения цикла, а в цикле repeat - условие окончания цикла.
2. В цикле while повторяется один оператор (несколько операторов надо объединять в составной оператор с помощью операторных скобок begin ... end), а в цикле repeat можно повторять несколько операторов без операторных скобок.
3. В цикле while сначала проверяется условие, а после этого в зависимости от значения условия выполняется или не выполняется оператор или группа операторов после слова do.
В цикле repeat последовательность операторов выполняется один раз, а после этого проверяется условие, т. е. эта последовательность всегда выполняется хотя бы один раз, а в цикле while операторы, составляющие тело цикла могут вообще не выполняться ни одного раза.

Задание 1

Найти наименьшее натуральное число, кратное 131 с четным количеством цифр. Составить блок-схему и программу.

3. Программы с совместным использованием циклов repeat и while ... do ...

 

Пример 3. Если мы сложим все цифры какого-либо числа, затем - все цифры найденной суммы и будем повторять это много раз, мы наконец получим однозначное число (цифру), называемое цифровым корнем данного числа. Например, цифровой корень числа 561 равен 3 (5 + 6 + 1 = 12; 1 + 2 = 3).


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

Соображения по составлению программы

Ясно, что в программе должен быть цикл, который определяет сумму цифр числа. В свою очередь, этот цикл должен также выполняться до тех пор, пока значение суммы цифр не станет равным одной цифре, т.е. станет меньше 10, но остается больше 0. Для этого надо организовать еще один цикл, который будет являться внешним по отношению к циклу, подсчитывающему сумму цифр.
Одна тонкая особенность! Каждый раз после выполнения внутреннего цикла подсчета суммы цифр, значение этой суммы надо присваивать переменной, в которой содержится первоначальное число, т. е. заменять число на его сумму, проверять условие (не является ли сумма меньше десяти) и продолжать цикл уже с новым числом - суммой, если условие не выполняется. А ту переменную, в которой накапливалась сумма надо каждый раз не забывать обнулять.
Итак, если введенное число было присвоено переменной n, а сумма его цифр переменной s, то после подсчета суммы цифр, переменная должна получить значение s (n:= s), проверить условие (n < 10), если оно еще не выполняется, тогда обнулить переменную s (s:= 0) и продолжить цикл подсчета суммы цифр.
Внешний цикл по проверке значения суммы организуем с помощью операторов repeat ... until n < 10, а внутренний по подсчету суммы цифр с помощью операторов while ... do.

   Блок-схема

    Рис. 26


Программа

Program Problem3; { Цифровой корень числа }
uses WinCrt;
var
n, a, s : integer;
begin
write("Введите натуральное число "); readln(n);
a := n;
repeat
s := 0;
while n <> 0 do
                   begin
s := s + n mod 10;
n := n div 10
             end;
n := s
until n < 10;
writeln("Цифровой корень числа ", a, " равен ", n)
end.

Задание 2

1. Выполните эту программу. Измените ее так, чтобы она находила цифровые корни каждого из чисел от 10 до 100.


2. Найти трехзначное число, являющееся точным квадратом натурального числа k, и такое, что произведение его цифр равно k - 1. Составьте блок-схему и программу.

4. Разные задачи

 

Пример 4. Составить программу определения всех делителей числа n.

Когда ставится такая задача, то очень часто учащиеся предлагают такой способ решения.
Надо испробовать все натуральные числа, начиная от 1 до n и, если какое-то из них будет являться делителем числа n, тогда выдавать его на экран. Например, для числа 36, берем для проверки числа 1, 2, 3, ..., 36 и выбираем из них делители 36. Делители будут следующими: 1, 2, 3, 4, 6, 9, 12, 18 и 36.
Такой способ возможен. Но, если вы внимательно посмотрите на делители числа 36, то обнаружите, что все они находятся в интервале от 1 до 18, т.е. до половины числа 36 и лишь последний делитель - это само число.
Да и простая логика рассуждений убеждает нас, что делители будут располагаться именно в этом интервале: от 1 до .
Если допустить мысль, что есть делитель больше половины числа, тогда умножив его только лишь на 2, мы получим число большее заданного.
Итак, становится ясным, что все делители числа, кроме самого, находятся в промежутке от 1 до , а значит надо проверять числа на возможные делители именно из этого промежутка.
Отсюда возникает такой план составления программы: организовать цикл от 1 до ; если число n делится на число из этого промежутка, тогда вывести этот делитель на экран; продолжить цикл; выдать на экран само число.

Программа
Program Problem4; { Простой алгоритм. 1 - способ }
uses WinCrt;
var
n, d : integer;
begin
write("Введите целое число "); readln(n);
d := 1;
writeln("Делители числа ", n);
repeat
if n mod d = 0 then write(d, " ");
d := d + 1
until d > n div 2;
write(n)
end.
Но и при решении этой задачи машине можно помочь и облегчить ее работу. Здесь на помощь снова приходит математика.
Оказывается, для того чтобы найти делители числа n, достаточно обнаружить делители не превышающие .
Все остальные делители получаются в результате деления числа n на найденные делители.
Например, если n = 30, то достаточно найти делители 1, 2, 3, 5 (натуральный квадратный корень из 30 равен 5), а все прочие делители получаются делением на найденные:
30 div 1 = 30;
30 div 2 = 15;
30 div 3 = 10;
30 div 5 = 6.
При составлении программы возникает проблема - нет встроенной функции извлечения квадратного корня в множестве целых чисел. Это препятствие легко обойти, если организовать цикл для выбора делителей d от 1 до тех пор пока d*d<n (что является тем же, что и < n), а если корень квадратный извлекается нацело, тогда этот случай надо рассмотреть отдельно после завершения основного цикла.
Почему надо сделать именно так. Это становится понятным на примере для числа 36. = 6, цикл - пока d d < 6;
d = 1, d d = 1 1 = 1 < 36 (истина),
цикл продолжается;
находится остаток от деления 36 mod 1 = 0; выдается 1 и частное от деления 36 на 1, 36 div 1 =36;
d = 2, d d = 2 2 = 4 < 36 (истина),
цикл продолжается;
36 mod 2 = 0;
выдается 2 и частное от деления 36 на 2, 36 div 2 = 18;
d = 3, d d = 3 3 = 9 < 36 (истина),
цикл продолжается;
36 mod 3 = 0;
выдается 3 и частное от деления 36 на 3, 36 div 3 = 12;
d = 4, d d = 4 4 = 16 < 36 (истина),
цикл продолжается;
36 mod 4 =0;
выдается 4 и 36 div 4 = 9;
d = 5, d d = 5 5 = 25 < 36 (истина),
цикл продолжается;
36 mod 5 <>0, ничего не выдается на экран,
цикл продолжается;
d = 6, d d = 6 6 = 36 < 36 (ложь), цикл заканчивается.
Проверяется d = 6 (d d = n), 6 6 = 36 (истина), выдается 6.
Если бы цикл продолжался, пока d d <= n, тогда при d = 6 на экран выдавалось бы - 6 и 36 div 6 = 6, т. е. две шестерки, что было бы ошибкой.
  Блок-схема


Рис. 27
Программа

Program Problem4a; { Делители числа. 2 - способ }
uses WinCrt;
var
n, d : integer;
begin
write("Введите целое число "); readln(n);
writeln("Делители числа ", n);
d := 1;
while d*d < n do
begin
if n mod d=0 then write(d, " ", n div d, " ");
d := d + 1
end;
if d*d = n then write(d); writeln
end.

Задание 3

 

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

Пример 5. Найти наибольший общий делитель (НОД) двух чисел a и b.

Вопрос определения наибольшего общего делителя двух чисел настолько детально и тщательно изложен во всех учебных пособиях, что сообщить что-нибудь новое в составлении алгоритмов нахождения НОД очень трудно.
Однако, я заметил, что в большинстве пособий излагается определение НОД с помощью алгоритма Евклида, причем не самым лучшим способом.
Мы изберем другой подход к этому вопросу, как мне кажется, более естественный.
Итак, допустим, что мы не знаем алгоритма Евклида и пробуем исходя из элементарных знаний математики и простой логики рассуждений найти наибольший общий делитель чисел, а затем и составить программу.
Прежде четко определим для себя, что такое НОД двух чисел. Так, для чисел 36 и 45 существуют три общих делителя: 1, 3, 9. Наибольший среди них 9. Он и является НОД чисел 36 и 45.
Для 30 и 45 немного больше общих делителей: 1, 3, 5 и 15. Наибольшим является 15, значит НОД(30, 45) = 15.


Наибольшим общим делителем чисел a и b называется наибольшее число среди всех общих делителей чисел a и b.

Тогда, по логике вещей, возникает естественная идея найти НОД следующим образом.
Во-первых, надо проверить не делится ли одно из чисел на другое, если делится, тогда то на которое разделилось и является наибольшим общим делителем. Например, для чисел 45 и 15 НОД будет число 15. Если ни одно из них не делится на другое, тогда будем брать поочередно все натуральные числа от 1 до меньшего из чисел a или b и проверять на какие из них делятся оба числа, последний из этих общих делителей и будет наибольшим.
Такой процесс для чисел 36 и 45 будет выглядеть так:
проверяем деление a на b и b на a;
находим остаток от деления на 1, 36 mod 1= 0, 45 mod 1 = 0, значит 1 - общий делитель;
на 2, 36 mod 2 = 0, 45 mod 2 <>0, 2 не является общим делителем;
на 3, 36 mod 3 = 0, 45 mod 3 = 0, 3 - общий делитель;
на 4, .................................................. и так далее до 36.
Последний из этих общих делителей будет 9, он и является НОД.

Блок-схема

Рис. 28


Программа

Program Problem5;
uses WinCrt;
var
a, b, n, k, i : integer;
begin
write("Введите первое число "); readln(a);
write("Введите второе число "); readln(b);
if a mod b = 0
then n := b
else
if b mod a = 0
then n := a
else
begin
if a > b then i := b else i := a;
k := 1;
while k < i do
begin
if (a mod k = 0) and (b mod k = 0) then n := k;
k := k + 1
end
end;
writeln("НОД числе ", a," и ", b, " равен ", n)
end.

Но подумайте, сколько бесполезной работы проделывает компьютер, работая по этой программе!
Так, для чисел 36 и 45 всего цикл будет выполняться 36 раз. Из них "чисто" бесполезных или "пустых" будет 27, так как наибольший общий делитель равен 9 и от 9 до 36 - бесполезная работа.

Естественно возникает вопрос, а нельзя ли выбрать другой путь для определения НОД? А что, если попробовать "с другого конца", т.е. выбрать меньшее число и уменьшать его на единицу, каждый раз проверяя, не является ли полученное число делителем.
Как только такой делитель найден, цикл прекращается, а этот делитель и будет наибольшим, таким образом, число бесполезных циклов уменьшится.
Например, для тех же чисел 36 и 45 цикл уже будет выполняться не 36 раз, а 27: 36, 35, 34, 33, 32, 31, ..., 9.

Алгоритм

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


Блок-схема


Рис. 29

Программа

Program Problem5a;
uses WinCrt;
var
a, b, n, k : integer;
begin
write("Введите первое число "); readln(a);
write("Введите второе число "); readln(b);
if a > b then k := b else k := a;
n := k + 1;
repeat
n := n - 1
until (a mod n = 0) and (b mod n = 0) ;
writeln("НОД чисел ", a, " и ", b, " равен ", n)
end.

При такой конструкции программы уже не надо проверять деление одного числа на другое (подумайте почему?).
Конечно, эти программы можно усовершенствовать, сделать менее трудоемкими для компьютера (попробуйте это сделать сами), и все-таки нам придется обратиться к алгоритмам Евклида, которые до сих пор являются совершенством в математике.
Они отличаются не только математической оригинальностью, но и простотой. Все гениальное просто!
Итак, первый из алгоритмов Евклида нахождения НОД состоит в следующем.
Например, надо найти НОД чисел 36 и 45.
Вычитаем из большего числа меньшее: 45 - 36 = 9,
заменяем большее из данных чисел на разность, получаем два других числа:
9 и 36;
снова, из большего вычитаем меньшее: 36 - 9 = 27,
заменяем большее на разность, получаем 9 и 27; из большего вычитаем меньшее:
27 - 9 = 18,
заменяем большее на разность, получаем 9 и 18; из большего вычитаем меньшее:
18 - 9 = 9,
заменяем большее на разность, получаем 9 и 9.
Получены два равных числа, значит НОД чисел 45 и 36 равно 9.

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

Этот алгоритм Евклида имеет строгое математическое обоснование и не может вызывать никаких сомнений.


Блок-схема


Рис. 30

Программа

Program Problem2b;
uses WinCrt;
var
a, b, c, a1, b1 : integer;
begin
write("Введите первое число "); readln(a);
write("Введите второе число "); readln(b);
a1 := a; b1 := b;
while a <> b do
begin
if a > b then a := a - b else b := b - a
end;
writeln("НОД чисел ", a1, " и ", b1, " равен ", a)
end.

В этой программе использован цикл "пока", а не цикл "до". Как вы думаете почему? Для ответа на этот вопрос, замените цикл " пока" на цикл " до ...", т. е. операторы while ... do на repeat ... until ... Цикл станет таким:

repeat
    if a > b then a := a - b else b := b - a
until a = b;

Как вам уже известно, цикл repeat обязательно выполняется хотя бы один раз. Если вы введете два равных числа, то программа "зациклится". В самом деле, условие a > b не выполняется, значит будет выполнен оператор b := b - a. b получит значение 0, цикл повторится, условие a > b выполняется, тогда a получит значение: a := a - 0, т.е. значение a не изменится, равенство a=b никогда не выполнится и цикл будет продолжаться "бесконечно", как говорят, "программа зациклится".
Если же применяется цикл while a <> b do ..., то даже при вводе равных чисел a и b (a = b), цикл не выполнится ни одного раза и НОД получит значение одного из равных чисел - a.
Существует и второй алгоритм Евклида для нахождения НОД..
Пусть a и b - натуральные числа, b <> 0 и r - остаток от деления a на b. Тогда НОД(a, b) = НОД(r, b).
Для доказательства используется очевидное свойство наибольшего общего делителя: натуральное число d тогда и только тогда является наибольшим общим делителем a и b, когда это число:
1) делит a и b, т.е. является общим делителем a и b;
2) делится на любой общий делитель a и b.
Пусть a  b  0 и a > 0. Тогда применение алгоритма Евклида происходит так: если b = 0, то НОД(a, b) = a. Иначе вычисляем r, равное остатку от деления a на b, и сводим задачу отыскания НОД(a, b) к задаче отыскания НОД(r, b). При r>0 этот процесс можно продолжить. Имеем: b > r > r1 > r2 > r3 >, ..., но так как b, r, r1, r2, r3 - неотрицательные целые числа, то найдется n такое, что rn = 0. В соответствии с высказанным утверждением
НОД(a, b) = НОД(b, r) = НОД(r1, r) = ... = НОД(rn-1, 0) = rn-1.
Практически это выглядит так. Надо найти НОД чисел 888 и 351.
Большим из них является 888, a = 888, b = 351.
Находим остаток от деления a на b: 888 mod 351 = 186, r = 186;
заменим a на b и b на остаток r, получим: a = 351, b = 186;
снова находим остаток от деления a на b: 351 mod 186 = 165, r = 165;
заменим a на b и b на остаток r, получим: a = 186, b = 165;
находим остаток от деления a на b: 186 mod 165 = 21, r = 21;
заменим a на b и b на остаток r, получим: a = 165, b = 21;
находим остаток от деления a на b; 165 mod 21 = 18, r = 18;
заменим a на b и b на остаток r, получим: a = 21, b = 18;
находим остаток от деления a на b; 21 mod 18 = 3, r = 3;
заменим a на b и b на остаток r, получим: a = 18, b = 3;
находим остаток от деления a на b: 18 mod 3 = 0, r = 0;
заменим a на b и b на остаток r, получим: a = 3, b = 0.
Как только b стало равным нулю, цикл заканчивается, выдается значение a, которое и является наибольшим общим делителем, НОД(888, 351) = a = 3.
Этот процесс можно записать в виде следующей цепочки, которая в общем виде была записана выше:
НОД(888, 351) = НОД(351, 186) = НОД(186, 165) =
= НОД(165, 21) = НОД(21, 18) = НОД(18, 3) = НОД(3, 0) = 3.

Замечание. Совсем не обязательно выбирать большее из двух чисел. Если число a окажется меньшим, тогда при первом шаге цикла произойдет перестановка чисел a и b.
Например, a = 351, b = 888. Находится остаток от деления a на b:  r = 351; заменим a на b и b на остаток r, получим:    все стало на свои места и процесс пойдет прежним порядком.

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


  Рис. 31

Программа

Program Problem2c; { 2 - способ. Алгоритм Евклида }
uses WinCrt;
var
          a, b, r, a1, b1 : integer;
begin
write("Введите первое число "); readln(a);
write("Введите второе, не равное нулю, число "); readln(b);
a1 := a; b1 := b;
repeat
r := a mod b;
a := b; b := r
until b = 0;
writeln("НОД чисел ", a1, " и ", b1, " равен ", a)
end.

Задание 4

 

Составьте программу определения наименьшего общего кратного (НОК) двух чисел по меньшей мере двумя способами.
Напоминание
Наименьшим общим кратным двух чисел a и b, НОК(a, b) называется наименьшее число, которое делится и на a и на b.


Например, для чисел 18 и 27 наименьшим общим кратным является число 54. Оно делится без остатка и на 18 и на 27. Хотя общих кратных для этих чисел существует бесконечно много: 54, 108, 162, 216, ..., однако, 54 является меньшим среди них.

Подсказка
1. Идея составления первой программы или, иначе говоря, идея первого алгоритма состоит в следующем.
Выбираем большее из чисел, если оно делится на меньшее, тогда оно и будет являться наименьшим общим кратным, иначе, большее число увеличивается вдвое, т.е. к нему прибавляется само это число и снова происходит проверка, делится ли новое число на меньшее, если делится, тогда оно является НОК, если не делится, тогда снова увеличивается на такое же число, т.е. первоначальное большее из двух уже увеличивается втрое и так далее.
Например, для чисел 10 и 36 этот процесс будет выглядеть так: 36 большее из чисел, 36 mod 10 <>0, т.е. 36 не делится на 10; увеличим 36 на 36, получим:  проверяем: 72 mod 10 <> 0; увеличим 72 еще на 36, получим:  проверяем: 108 mod 10 <> 0; увеличиваем на 36, получим:  проверяем: 144 mod 10 <> 0; увеличиваем:  проверяем: 180 mod 10=0, 180 делится на 10, значит 180 и является наименьшим общим кратным чисел 10 и 36, НОК(10, 36) = 180.

2. Идея второго алгоритма основывается на следующем математическом утверждении: a b = НОК(a, b) НОД(a, b).

Пример 3. Составить программу, которая определяет является ли данное число n простым.

Простым называется натуральное число, которое имеет только два делителя - 1 и само себя. Надо заметить, что число 1 не подходит под это определение, так как имеет только один делитель - само себя, а значит не является простым числом.
Натуральные числа, отличные от 1 и не являющиеся простыми называются составными.
Таким образом, число 1 не относится ни к простым ни к составным.
Но это лишь между прочим для того, чтобы вспомнить арифметику и расширить наш математический кругозор.
Зная все это, возникает такой план составления программы. Найти количество делителей числа, исключая 1 и само число. Если таких делителей будет нуль, т.е. вообще не будет, тогда число является простым, иначе, оно является составным.
Для подсчета числа делителей в программе надо завести счетчик, а по окончанию цикла, выяснять его значение.

      Блок-схема


    Рис. 32
Программа

Program Problem3;
uses WinCrt;
var
n, d, k : integer;
begin
write("Введите натуральное число большее 2 "); readln(n);
d := 2; k := 0;
repeat
if n mod d =0 then k := k + 1;
d := d + 1
until d > n div 2;
if k = 0 then writeln("Число ", n, " является простым")
else writeln("Число ", n, " составное")
end.

Ее можно усовершенствовать. В самом деле, зачем продолжать цикл, если найден хотя бы один делитель? Цикл надо прервать и выдать сообщение, что число составное, а затем закончить программу, иначе, продолжать цикл до конца, т. е. до  и после цикла выдать сообщение - число простое.

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

Program Problem3a;
uses WinCrt;
var
n, d, k : integer;
label 1, 2, 3;
begin
write("Введите натуральное число, большее 1 "); readln(n);
if n = 2 then goto 1;
d := 2; k := 0;
repeat
if n mod d = 0 then goto 2;
d := d + 1
until d > n div 2;
1: writeln("Число ",n, " - простое"); goto 3;
2: writeln("Число ",n, " - составное");
3: end.

В обоих из приведенных вариантов компьютер проделывает много ненужной работы.
Существуют и другие способы определения, является ли число простым или составным.
Вот один из них, который вытекает из естественных соображений.
Во-первых, если число является четным, то ясно, что оно будет составным, но перед этим надо исключить из рассмотрения число 2 (оно является простым числом), т.е. проверить, если данное число равно 2, то оно является простым.
Во-вторых, надо проверять деление только на нечетные числа до n/2. И в этом случае можно использовать досрочное прерывание цикла, если делитель найден.
Программа достаточно проста и вам надо составить ее
самостоятельно.

Задание 5

 

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

Пример 4. Составить программу нахождения всех простых чисел из заданного промежутка [n, m].

Алгоритм

Первые соображения такие: проверять каждое из чисел заданного промежутка [n, m], начиная с m и проверять является ли оно простым числом, если является, тогда выводить его на экран.
Затем увеличить проверенное число на единицу и снова проверить и так далее до конца промежутка.
Для того, чтобы проверить каждое из чисел можно организовать цикл
repeat ... until ...
Первоначальное значение переменной цикла установить равной значению левого конца промежутка (p := n), а в качестве условия окончания цикла, равенство значения p правой границе промежутка - m (until p = m).
Тогда внешний цикл будет таким:
p := n;
repeat
....
p := p + 1
until p = m;
"Внутри" этого цикла записываются уже известные вам операторы проверки числа, является ли оно простым. Если является, тогда выдавать его на экран.
Этот процесс проверки выполним с помощью операторов, которые вы должны были составить при выполнении предыдущего задания:
  if p = 2 then write(p:4 , " ")
else if p = 3
then write(p:4, " ")
else if p mod 2 <> 0
then
begin
i := 3; k := 0;
repeat
if p mod i = 0 then k := k + 1;
i := i + 2
until i > p div 2;
if k = 0 then write(p:4, " ")
end;
Если число p равно 2 или p равно 3, тогда оно является простым и его надо выдать на экран: if p = 2 then write(p:4, " ")
иначе, надо проверять только нечетные числа, ибо ясно, что любое четное число - составное:
else if p mod 2 <> 0,
также надо выдавать на экран число 3: else if p = 3
then write(p:4, " ")
далее, надо проверять деление числа p на нечетные числа, а значит в качестве первоначального значения делителя i берется 3, а в цикле оно увеличивается на 2. Счетчик k, как и в предыдущей программе подсчитывает число делителей. После завершения цикла подсчета числа делителей, его значение проверяется, если оно равно нулю, значит ни одного делителя у числа нет - оно является простым и выдается на экран.

Полностью программа приведена ниже:

Program Problem4; { Простые числа из промежутка [n; m] }
uses WinCrt;
var
n, m, p, i, k : integer;
begin
write("Введите левую границу промежутка "); readln(n);
write("Введите правую границу промежутка "); readln(m);
writeln("Простые числа из промежутка [", n, " ", m, "]");
p := n;
if p = 1 then p := p + 1;
repeat
if p = 2 then write(p:4, " ")
else if p = 3
then write(p:4, " ")
else
if p mod 2 <> 0
then
begin
i := 3; k := 0;
repeat
if p mod i = 0 then k := k + 1;
i := i + 2
until i > p div 2;
if k = 0 then write(p:4, " ")
end;
p := p + 1
until p = m;
writeln
end.

Задание 6

 

Найти простые числа p из промежутка [1; 1000], такие, что p + 10 и p + 14 тоже являются простыми числами.


Упражнения

 

  1. Найти наименьшее целое число, делящееся на 7, которое при делении на 2, 3, 4, 5, 6 дает в остатке 1.
  2. Какие числа, заключенные между числами 2320 и 2350 простые, а какие составные?
  3. Составьте программу для нахождения наименьшего нечетного неравного 1 натурального делителя любого заданного натурального числа, большего 1.
  4. Найти двузначное число, которое на 6 меньше квадрата суммы своих цифр.
  5. Дана сократимая дробь, ее числитель и знаменатель - натуральные числа m и n. Найти такие натуральные числа m1 и n1, не имеющие общих делителей, что , т. е. сократить дробь
  6. Напишите программу, которая для каждого из целых чисел от 1 до n напечатает все его делители. Например, для числа 35 - делители: 1, 5, 7, 35. Аналогичный список делителей должен быть выдан для каждого из чисел от 1 до заданного числа n.
  7. Найти наименьшее натуральное число n, обладающее следующими свойствами: а) его запись в десятичной системе счисления оканчивается цифрой 6; б) если переставить цифру 6 из конца числа в его начало, то полученное число будет в 4 раза больше данного.
  8. Написать программу вывода всех натуральных чисел, меньших n, квадрат суммы цифр которых равен m.
  9. Можно ли данное целое p представить в виде суммы двух квадратов целых чисел? Написать программу решения этой задачи.
  10. Найти все четырехзначные числа , удовлетворяющие условию:  = (  + ).
  11. Найти числа, оканчивающиеся на цифру a (a = 2, 3, 4, 5, 6, 7, 8, 9) и обладающее тем свойством, что если последнюю цифру переставить в начало числа, то число увеличится во столько раз, сколько единиц в переставляемом числе.
  12. Найти целые числа n, делящиеся на все простые числа, не большие .
  13. Составьте программу для проверки, можно ли заданное натуральное число представить в виде: а) произведения двух простых чисел; б) произведения трех простых чисел; в)квадрата какого-либо простого числа; г) куба какого-либо простого числа. Следует напечатать ответ ДА или НЕТ.
  14. Разрезание прямоугольника на квадраты.

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

  1. Составить программу для нахождения всех прямоугольников указанной площади (площадь - исходное данное выраженное натуральным числом), стороны которых - натуральные числа. Например, если площадь равна 12, то получим три разных прямоугольника:


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

  1. Составить программы, которые устанавливают, являются ли два числа взаимно простыми, три числа взаимно простыми.
  2. Найти все натуральные числа n, меньшие заданного числа k, для которых  делится на
  1. Найти наименьшее натуральное число n, для которого  есть составное число. (Задача Серпинского.)

Автор: Тишин Владимир Иванович

Сравнение предметов

Сравнение предметов Важно, готовя ребёнка к школе, научить его наблюдать, сравнивать, выделять черты сходства и различия в рас¬сматриваемых предметах, рассказывать, что нарисовано на картинке, чем похожи и чем отличаются сравниваемые предметы. Задания, направленные на формирование этих умений, даются в этом разделе. Ребёнок должен научиться сравнивать предметы по цве¬ту ...

Нуклеиновые кислоты

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

Упражнение 17

Упражнение 17 Цель упражнения - развитие наблюдательности, воображения и речевой деятельности. Формирование умения оценивать количественную характеристику видоизменяющейся конструкции (без изменения количества элементов). Материал: счетные палочки двух цветов. Примечание: первое задание упражнения является также подготовительным к правильному восприятию смысла ...

Можно ли считать 'Обломов' романом о любви

Можно ли считать «Обломов» романом о любви? Оценивать произведение можно, лишь посмотрев и взвесив все действия главного героя по отношению к окружающим его лицам. Обломов живет под одним небом с Захаром, своим слугой, со Штольцем, другом детства, с Ольгой, с Агафьей Матвеевной. Итак, посмотрим, что же связывало Илью Ильича с этими разными людьми. Отношения между Обломовым и Захаром ...