Урок 11

Тема:  Анализ программы, содержащей подпрограммы, циклы и ветвления.
Актуализация опорных знаний

Что нужно знать:

·      операции целочисленного деления (div) и взятия остатка (mod)

·      как работают операторы присваивания, циклы и условные операторы в языке программирования

Пример задания:

Ниже записан алгоритм. Укажите наименьшее из таких чисел , при вводе которых алгоритм печатает сначала 3, а потом 2.

var x, a, b, c: integer;

begin

  readln(x);

  a:= 0; b:= 0;

  while x > 0 do begin

    c:= x mod 2;

    if c = 0 then a:= a + 1

    else b:= b + 1;

    x:= x div 10;

  end;

  writeln(a);

  writeln(b);

end.

Решение:

1)      видим, что в последний строках выводятся на экран переменные a и b, поэтому сначала нужно определить, что они обозначают в программе

2)      перед началом цикла обе переменные обнуляются

3)      на каждом шаге цикла при выполнении некоторого условия переменная a увеличивается на 1, а если это условие не выполняется, то на 1 увеличивается b; таким образом, обе переменных – счётчики

4)      теперь посмотрим на условие c = 0: в предыдущей строке в переменную c записывается остаток от деления числа x на 2, то есть, переменная c определяет четность числа или, что равносильно, чётность его последней цифры

5)      если последняя цифра чётная, то увеличивается счётчик a, а если нечётная – увеличивается счётчик b

6)      в конце каждого шага цикла операция x:=x div 10 отсекает последнюю цифру в десятичной записи числа

7)      таким образом, делаем вывод: после завершения цикла в переменной a находится количество чётных цифр в десятичной записи числа, а в переменно b – количество нечётных цифр

8)      если было выведено 3 и 2, то в числа 5 цифр, из них 3 чётных и 2 нечётных; таким образом, нам нужно найти минимальное пятизначное число, в котором 3 чётные и 2 нечётные цифры

9)      минимальная чётная цифра – это 0, минимальная начётная – 1; 0 не может стоять на первом месте, поэтому число начинается с 1

10)   для получения минимального числа после 1 должны идти нули и последняя цифра – снова 1

11)   ответ: 10001

Ещё пример задания:

Ниже записан алгоритм. После выполнения алгоритма было напечатано 3 числа. Первые два напечатанных числа – это числа 9 и 81. Какое наибольшее число может быть напечатано третьим?

var x, y, z: integer;

    r, a, b: integer;

begin

  readln(x, у);

  if у > x then begin

    z:= x; x:= у; у:= z;

  end;

  a:= x; b:= y;

  while b > 0 do begin

    r:= a mod b;

    a:= b;

    b:= r;

  end;

  writeln(a);

  writeln(x);

  write(у);

end.

Решение:

12)   сложность этой задачи состоит в том, чтобы разобраться в алгоритме

13)   сначала вводятся два числа и переставляются так, чтобы в переменной x было наибольшее число, а в переменной y – наименьшее из двух:

  if у > x then begin

    z:= x; x:= у; у:= z;

  end;

14)   затем исходные значения копируются в переменные a и b и с ними выполняется следующий алгоритм

  while b > 0 do begin

    r:= a mod b;

    a:= b;

    b:= r;

  end;

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

15)   делаем вывод, что это классический Алгоритм Евклида, который служит для вычисления наибольшего общего делителя (НОД) двух чисел; это делитель в результате оказывается в переменной a

16)   смотрим, что выводится на экран: сначала значение переменной a (наибольший общий делитель исходных чисел, НОД(x,y)), затем значение x (большее из исходных чисел) и значение y (меньшее из исходных чисел)

17)   по условию первое число – 9, второе – 81, поэтому третье число должно быть меньше, чем 81, и НОД(81,y) = 9

18)   наибольшее число, которое меньше 81 и делится на 9, равно 72 (обратите внимание, что исходные числа не могут быть равны, потому что в этом случае их НОД был бы равен 81)

19)   ответ: 72

Ещё пример задания:

Ниже записана программа. Получив на вход число , эта программа печатает два числа,  и . Укажите наибольшее из таких чисел , при вводе которых алгоритм печатает сначала 3, а потом 7.

var x, L, M: integer;

begin

  readln(x);

  L:=0; M:=0;

  while x > 0 do begin

    L:=L+1;

    if M < (x mod 10) then begin

      M:=x mod 10;

    end;

    x:= x div 10;

  end;

  writeln(L); write(M);

end.

 Решение:

20)   для решения задачи необходимо понять, что делает эта программа

21)   если это не видно сразу, можно выполнить ручную прокрутку для какого-то простого числа, например, для числа 251:

оператор

условие

x

L

M

readln(x);

 

251

?

?

L:=0; M:=0;

 

 

0

0

while x > 0 do…

251 > 0? да

 

 

 

L:=L+1;

 

 

1

 

if M<(x mod 10) then…

M <(251 mod 10)? да

 

 

 

M:=x mod 10;

 

 

 

1

x:=x div 10;

 

25

 

 

while x > 0 do…

25 > 0? да

 

 

 

L:=L+1;

 

 

2

 

if M<(x mod 10) then…

M <(25 mod 10)? да

 

 

 

M:=x mod 10;

 

 

 

5

x:=x div 10;

 

2

 

 

while x > 0 do…

2 > 0? да

 

 

 

L:=L+1;

 

 

3

 

if M<(x mod 10) then…

M <(2 mod 10)? нет

 

 

 

x:=x div 10;

 

0

 

 

while x > 0 do…

0 > 0? нет

 

 

 

writeln(L); write(M);

 

 

3

5

22)   можно догадаться, что в результате работы программы в переменной L окажется число цифр числа, а в переменной M – наибольшая цифра, но это предположение нужно постараться доказать

23)   нужно вспомнить (и запомнить), что для целого числа остаток от деления на 10 (x mod 10) – это последняя цифра в десятичной записи числа, а целочисленное деление (x div 10) отсекает последнюю цифру, то есть из 123 получается 12

24)   рассмотрим цикл, число шагов которого зависит от изменения переменной x:

  while x > 0 do begin

    ...

    x:= x div 10;      { отсечение последней цифры }

  end;

здесь оставлены только те операторы, которые влияют на значение x

25)   из приведенного цикла видно, что на каждом шаге от десятичной записи x отсекается последняя цифра до тех пор, пока все цифры не будут отсечены, то есть x не станет равно 0; поэтому цикл выполняется столько раз, сколько цифр в десятичной записи введенного числа

26)   на каждом шаге цикла переменная L увеличивается на 1:

  L:=L+1;

других операторов, меняющих значение L, в программе нет; поэтому после завершения цикла в переменной L действительно находится количество цифр

27)   теперь разберемся с переменной M, которая сначала равна 0; оператор, в котором она меняется, выглядит так:

  if M < (x mod 10) then begin

    M:=x mod 10;

  end;

учитывая, что x mod 10 – это последняя цифра десятичной записи числа, получается что если эта цифра больше, чем значение M, она записывается в переменную M; 

28)   этот оператор выполняется в цикле, причем выражение x mod 10 по очереди принимает значения всех цифр исходного числа; поэтому после завершения циклам в переменной M окажется наибольшая из всех цифр, то есть наша догадка подтверждается

29)   итак, по условию задачи фактически требуется найти наибольшее трехзначное число, в котором наибольшая цифра – 7; очевидно, что это 777.

30)   ответ: 777.

Возможные ловушки и проблемы:

·    это очень неплохая задача на понимание, тут достаточно сложно «вызубрить» метод решения, можно только освоить последовательность (системность) анализа

·    ручной прокрутки в такой задаче недостаточно, по её результатам можно угадать алгоритм, но можно и не угадать; в критическом случае можно сделать ручную прокрутку для нескольких чисел им попытаться понять закономерность

Ещё пример задания:

Ниже записана программа. Получив на вход число , эта программа печатает два числа,  и . Укажите наибольшее из таких чисел , при вводе которых алгоритм печатает сначала 3, а потом 120.

var x, L, M: integer;

begin

  readln(x);

  L:=0; M:=1;

  while x > 0 do begin

    L:=L+1;

    M:= M*(x mod 8);

    x:= x div 8;

  end;

  writeln(L); write(M);

end.

 Решение:

1)      для решения задачи необходимо понять, что делает эта программа; повторяя рассуждения из предыдущего примера, выясняем, что

а)      переменная L с каждым шагом цикла увеличивается на 1

б)      переменная x на каждом шаге цикла делится на 8 и остаток отбрасывается

поэтому можно сделать вывод, что в конце цикла переменная L будет равна количеству цифр введенного числа, записанного в восьмеричной системе счисления; таким образом, восьмеричная запись числа содержит ровно 3 цифры

2)      выражение x mod 8 – это последняя цифра восьмеричной записи числа; на каждом шаге цикла переменная M умножается на эту величину, поэтому в результате в M будет записано произведение всех цифр восьмеричной записи введенного числа

3)      по условию это произведение равно 120, то есть , где a, b и с – числа от 0 до 7 (которые в восьмеричной системе счисления записываются одной цифрой)

4)      поскольку нам нужно наибольшее число, перебираем делители числа 120, начиная со старшей цифры – 7; видим, что 120 на 7 не делится, поэтому такой цифры в восьмеричной записи числа нет

5)      но 120 делится на 6, поэтому старшей цифрой может быть 6 – только в том случае, когда второй сомножитель можно представить в виде произведения двух чисел в интервале 1..6

6)      делим 120 на 6, получаем 20; это число представляется как произведение 5 и 4, каждое из этих чисел записывается в виде одной восьмеричной цифры, то есть, они нам подходят

7)      вспомним, что нас интересует максимальное число, поэтому цифры нужно выстроить в порядке убывания: 6548

8)      заметим, что мы получили число в восьмеричной системе, а ответ нужно дать в десятичной; переводим: 6548 = 6·82 + 5·81 + 4·80 = 428.

9)      ответ: 428.

 

Содержание