Задание 20 (презентация по типам задач к ЕГЭ)

100 . Укажите наименьшее такое (т.е. 100) число x , при вводе которого алгоритм печатает 26 . Решение: var x, L, M: integer; begin readln(x); L := x; M := 65; if L mod 2 = 0 then M := 52; while L M do if L M then L := L – M else M := M – L ; writeln( M ); end. 1. в последней строке выводится на экран переменная M 2. видим, что в циклической части программы записан АЛГОРИТМ ЕВКЛИДА для вычисления наибольшего общего делителя ( НОД ) чисел, записанный в переменные M и L 3. введённое значение x записывается в переменную L и участвует в поиске НОД " width="640"

Ege 20 (повышенный уровень, время – 5 мин)

Анализ алгоритма, содержащего цикл и ветвление

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

• операции целочисленного деления ( div ) и взятия остатка ( mod )
• как работают операторы присваивания, циклы и условные операторы в языке программирования

Пример I:

Получив на вход число x , этот алгоритм печатает число M . Известно, что x100 . Укажите наименьшее такое (т.е. 100) число x , при вводе которого алгоритм печатает 26 .

Решение:

var x, L, M: integer;

begin

readln(x);

L := x; M := 65;

if L mod 2 = 0 then M := 52;

while L M do

if L M then

L := L – M

else

M := M – L ;

writeln( M );

end.

1. в последней строке выводится на экран переменная M

2. видим, что в циклической части программы записан АЛГОРИТМ ЕВКЛИДА для вычисления наибольшего общего делителя ( НОД ) чисел, записанный в переменные M и L

3. введённое значение x записывается в переменную L и участвует в поиске НОД

4. в переменную M до начала цикла записывается 65 , но если было введено чётное ( L mod 2 = 0 ) значение x (оно же L ), значение M заменяется на 52

if L mod 2 = 0 then M := 52;

5. сначала предположим, что замены не было, и в M осталось значение 65 ;

L := x; M := 65;

поскольку по условию алгоритм печатает 26 , тогда получается, что НОД(x,65)=26 ;

этого явно не может быть, потому что 65 не делится на 26

6. делаем вывод, что введено чётное значение x и произошла замена M на 52

7. тогда нужно найти чётное число x , большее 100, такое, что НОД(x,52)=26

8. первое число, большее 100, которое делится на 26 – это 104 , но оно не подходит, потому что делится ещё и на 52 , так что НОД(x,52)=52

9. поэтому берём следующее число, которое делится на 26 :

104 + 26 = 130

Ответ: 130

0 do begin if (x mod 10) mod 2 = 0 then A:=A*10+x mod 10 else begin K := K *10; B:=B*10 + x mod 10 end; x:=x div 10 end; A := A * K + B ; writeln( A ) end. 1. в последней строке выводится на экран переменная A , которая вычисляется в предыдущей строке по формуле A:=A*K+B 2. сколько раз выполняется цикл while ? при условии x 0 , с переменной x выполняется единственная операция – деление на 10 нацело: while x0 do begin ... x:=x div 10 end; Т.е. цикл выполняется столько раз, сколько цифр в десятичной записи введённого числа x " width="640"

Пример II:

Ниже записан алгоритм. Укажите минимальное число x, при вводе которого алгоритм печатает 26391 .

Решение:

var x, K, A, B: integer;

begin

readln(x);

K :=1; A:=0; B:=0;

while x0 do begin

if (x mod 10) mod 2 = 0 then

A:=A*10+x mod 10

else

begin

K := K *10;

B:=B*10 + x mod 10

end;

x:=x div 10

end;

A := A * K + B ;

writeln( A )

end.

1. в последней строке выводится на экран переменная A , которая вычисляется в предыдущей строке по формуле A:=A*K+B

2. сколько раз выполняется цикл while ?

• при условии x 0 , с переменной x выполняется единственная операция – деление на 10 нацело:

while x0 do begin

...

x:=x div 10

end;

Т.е. цикл выполняется столько раз, сколько цифр в десятичной записи введённого числа x

3. внутри цикла: выбор варианта действия зависит от выполнения условия (x mod 10) mod 2 = 0 , где x mod 10 – это последняя цифра x , а в условии проверяется её чётность (делимость на 2)

4. если последняя цифра числа чётная , то выполняется оператор A:=A*10+x mod 10 т.е., предыдущее значение A умножается на 10 и к результату добавляется последняя цифра x ;

Т.о. переменная A составляется из чётных цифр числа x , причём в обратном порядке , т.к. новая цифра добавляется в конец числа, а предыдущие (которые были ближе к концу в записи числа x ) продвигаются влево, в старшие разряды

5. теперь смотрим, как строится B : здесь всё то же самое, только нечётные цифры собираются в обратном порядке;

например , если исходное число было 12345, после окончания цикла мы получим A=42 и B=531

6. но есть ещё переменная K , её начальное значение = 1, и с каждой найденной нечётной цифрой она умножается на 10 ,

Т.е. K=10 в степени, равной количеству нечётных цифр!

для числа 12345 получим K=1000

7. в предпоследней строке по формуле A:=A*K+B собирается итоговое значение A ;

для нашего примера (12345) получим A:=42*1000+531=42531 , т.е. K служит для того, чтобы сдвинуть комбинацию чётных цифр в начало числа

8. итак, нам задано число 26391 , поэтому в искомом числе есть чётные цифры (по порядку, слева направо) { 6 , 2 } и нечётные цифры { 1 , 9, 3 } (тоже по порядку)

9. как же расположить эти цифры, чтобы получилось минимальное число?

• для этого сравниваем первые числа в списках чётных и нечётных чисел, и записываем в ответ меньшее из них;

• эту операцию повторяем, пока числа в обоих списках не кончатся;

• помним, что менять порядок чётных и нечётных чисел нельзя!

10. в данном случае получается { 1, 6, 2, 9, 3 } = 16293

Ответ: 16293

0 do begin y := x mod 10; if y 3 then a := a + 1; if y then b := b + 1; x := x div 10 end; writeln( a ); writeln( b ) end. 1. видим, что на каждом шаге цикла при выполнении некоторых условий переменные a и b увеличиваются на 1 , то есть представляют собой счётчики 2. увеличение переменных зависит от значения y = x mod 10 , то есть от последней цифры числа 3. если последняя цифра 3 , то увеличивается счётчик a , если – счётчик b ; 4. в конце каждого шага цикла операция x:=x div 10 отсекает последнюю цифру в десятичной записи числа " width="640"

Пример III:

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

Решение:

var x, y, a, b: longint;

begin

a := 0; b := 0;

readln( x );

while x 0 do begin

y := x mod 10;

if y 3 then a := a + 1;

if y then b := b + 1;

x := x div 10

end;

writeln( a );

writeln( b )

end.

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

2. увеличение переменных зависит от значения y = x mod 10 , то есть от последней цифры числа

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

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

5. таким образом: после завершения цикла в переменной a находится количество цифр, больших 3 , в десятичной записи числа, а в переменной b – количество цифр, меньших 8

6. если по условию было выведено 4 и 2, то в числе 4 цифры больше 3 и 2 цифры меньше 8

7. так как число пятизначное, то есть 4 + 2 – 5 = одна цифра, которая больше 3 и меньше 8 одновременно; она должна быть минимальной, поэтому эта цифра 4

8. чтобы число было минимальным , ещё одна цифра должна быть минимальной и меньшей 3 – это старшая 1 , и три цифры минимальные из цифр, больших или равных 8 , то есть три цифры 8

Ответ: 14888

0 do begin a := a + 1; b := b + ( x mod 10); x := x div 10; end; writeln( a ); write( b ); end. 1. на каждом шаге цикла при выполнении некоторых условий переменная a увеличиваются на 1 , а b увеличивается на x mod 10 2. цикл завершается операцией x:=x div 10 , которая отсекает последнюю цифру в десятичной записи числа 3. можно сделать вывод: после завершения цикла в переменной a находится количество цифр в десятичной записи числа, а в переменной b – их сумма 4. по условию выведено 2 и 12 , т.е. нужно найти все двузначные числа , в которых сумма значений цифр равна 12 5. число 12 может быть разложено на 2 слагаемых, меньших 10, 6. нам подходят числа 12 = 3 + 9 = 4 + 8 = 5 + 7 = 6 + 6 = 7 + 5 = 8 + 4 = 9 + 3 Ответ: 7 39, 48, 57, 66, 75, 84 и 93 " width="640"

Пример IV:

Ниже записан алгоритм. Сколько существует таких чисел , при вводе которых алгоритм печатает сначала 2 , а потом 12 ?

Решение:

var x, a, b: integer;

begin

readln( x );

a :=0; b :=0;

while x0 do

begin

a := a + 1;

b := b + ( x mod 10);

x := x div 10;

end;

writeln( a ); write( b );

end.

1. на каждом шаге цикла при выполнении некоторых условий переменная a увеличиваются на 1 , а b увеличивается на x mod 10

2. цикл завершается операцией x:=x div 10 , которая отсекает последнюю цифру в десятичной записи числа

3. можно сделать вывод: после завершения цикла в переменной a находится количество цифр в десятичной записи числа, а в переменной b – их сумма

4. по условию выведено 2 и 12 , т.е. нужно найти все двузначные числа , в которых сумма значений цифр равна 12

5. число 12 может быть разложено на 2 слагаемых, меньших 10,

6. нам подходят числа

12 = 3 + 9 = 4 + 8 = 5 + 7 = 6 + 6 = 7 + 5 = 8 + 4 = 9 + 3

Ответ: 7

39, 48, 57, 66, 75, 84 и 93

0 do begin a:=a+1; b:=b*(x mod 10); x:= x div 10 end; writeln(a); write(b) end. 1. на каждом шаге цикла при выполнении некоторых условий переменная a увеличиваются на 1 , а b умножается на ( x mod 10) 2. цикл завершается операцией x:=x div 10 , которая отсекает последнюю цифру в десятичной записи числа 3. можно сделать вывод: после завершения цикла в переменной a находится количество цифр в десятичной записи числа, а в переменной b – их произведение 4. по условию выведено 2 и 15 , т.е. нужно найти все двузначные числа , в которых произведение цифр равно 15 5. число 15 может быть разложено на 2 сомножителя, меньших 10: 15 = 3*5 = 5* 3 6. минимальное число: 35 Ответ: 35 " width="640"

Пример V:

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

Решение:

var x, a, b: integer;

begin

readln(x);

a:=0; b:=1;

while x0 do begin

a:=a+1;

b:=b*(x mod 10);

x:= x div 10

end;

writeln(a); write(b)

end.

1. на каждом шаге цикла при выполнении некоторых условий переменная a увеличиваются на 1 , а b умножается на ( x mod 10)

2. цикл завершается операцией x:=x div 10 , которая отсекает последнюю цифру в десятичной записи числа

3. можно сделать вывод: после завершения цикла в переменной a находится количество цифр в десятичной записи числа, а в переменной b – их произведение

4. по условию выведено 2 и 15 , т.е. нужно найти все двузначные числа , в которых произведение цифр равно 15

5. число 15 может быть разложено на 2 сомножителя, меньших 10:

15 = 3*5 = 5* 3

6. минимальное число:

35

Ответ: 35

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 увеличиваются на 1 , то есть представляют собой счётчики 2. увеличение переменных зависит от значения c = x mod 2 , то есть от четности цифры числа 3. если последняя цифра четная , то увеличивается счётчик a , если нечетная, то счётчик b 4. в конце каждого шага цикла операция x:=x div 10 отсекает последнюю цифру в десятичной записи числа 5. т.е. после завершения цикла в переменной a находится количество четных цифр, а в переменной b – количество нечетных цифр " width="640"

Пример VI:

Ниже записан алгоритм. Укажите наименьшее из таких чисел , при вводе которых алгоритм печатает сначала 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 увеличиваются на 1 , то есть представляют собой счётчики

2. увеличение переменных зависит от значения c = x mod 2 , то есть от четности цифры числа

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

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

5. т.е. после завершения цикла в переменной a находится количество четных цифр, а в переменной b – количество нечетных цифр

6. т.к. по условию будет выведено 3 и 2 , то в числе x должно быть 5 цифр:

• из них 3 чётных и 2 нечётных;

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

7. минимальная чётная цифра – это 0, минимальная начётная – 1

0 не может стоять на первом месте, поэтому число начинается с 1

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

Ответ: 10001

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. 1. вводятся два числа и переставляются так, чтобы в переменной x было наибольшее число, а в переменной y – наименьшее из двух 2. затем исходные значения копируются в переменные a и b и с ними выполняется следующий алгоритм суть сводится к тому, что меньшее из двух чисел, a и b , каждый раз заменяется на остаток от деления большего на меньшее до тех пор, пока этот остаток не станет равен нулю ; это классический Алгоритм Евклида , который служит для вычисления наибольшего общего делителя (НОД) двух чисел; этот делитель в результате оказывается в переменной a " width="640"

Пример VII:

Ниже записан алгоритм. После выполнения алгоритма было напечатано 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.

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

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

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

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

этот делитель в результате оказывается в переменной a

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

4. по условию первое число – 9 , второе – 81

поэтому 3-е число должно быть 81 , и НОД (81,y) = 9

5. наибольшее число , которое и делится на 9 , равно 72

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

Ответ: 72

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. Решение: 1. Чтобы понять, что делает эта программа, можно выполнить ручную прокрутку для какого-то простого числа, например, для числа 251 : " width="640"

Пример VIII:

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

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.

Решение:

1. Чтобы понять, что делает эта программа, можно выполнить ручную прокрутку для какого-то простого числа, например, для числа 251 :

0 do… L M   L:=L+1; 251 0? да ? if M x mod 10) then…   0 ?   M 0   M := x mod 10;   x := x div 10;     1           while x 0 do…   L:=L+1; 25 25 0? да   if M    1   M M :=x mod 10;       x:=x div 10;   2     while x 0 do…         2   L:=L+1; 2 0? да   if M      5   x:=x div 10;     M while x 0 do…       3     0 0 0? нет writeln( L ); write( M );                 3 5 " width="640"

оператор

readln(x);

условие

L:=0; M:=0;

x

 

 

251

while x 0 do…

L

M

 

L:=L+1;

251 0? да

?

if M x mod 10) then…

0

?

M

0

M := x mod 10;

x := x div 10;

1

while x 0 do…

L:=L+1;

25

25 0? да

if M

1

M

M :=x mod 10;

x:=x div 10;

2

while x 0 do…

2

L:=L+1;

2 0? да

if M

5

x:=x div 10;

M

while x 0 do…

3

0

0 0? нет

writeln( L ); write( M );

3

5

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

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

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

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

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

L:=L+1

• т.е. в переменной L действительно находится количество цифр

5. теперь разберемся с переменной M , которая сначала равна 0

• оператор, в котором она меняется, выглядит так:

if M

begin

M:=x mod 10;

end;

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

6. выражение x mod 10 по очереди принимает значения всех цифр исходного числа

• поэтому после завершения цикла в переменной M окажется наибольшая из всех цифр

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

• очевидно, что это 111

Ответ: 111

0 do begin L := L +1; M:=M* ( x mod 8 ) then begin x: = x div 8 ; end; writeln( L ); write( M ); end. Решение: 1. повторяя рассуждения из предыдущего примера, выясняем, что переменная L с каждым шагом цикла увеличивается на 1 переменная L с каждым шагом цикла увеличивается на 1 переменная x на каждом шаге цикла делится на 8 и остаток отбрасывается переменная x на каждом шаге цикла делится на 8 и остаток отбрасывается можно сделать вывод, что в конце цикла переменная L будет равна количеству цифр введенного числа, записанного в восьмеричной системе счисления таким образом, восьмеричная запись числа содержит ровно 3 цифры " width="640"

Пример IX:

Ниже записан алгоритм. Получив на вход число , эта программа печатает два числа, L и M . Укажите наибольшее из таких чисел , при вводе которых алгоритм печатает сначала 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 ) then begin

x: = x div 8 ;

end;

writeln( L );

write( M );

end.

Решение:

1. повторяя рассуждения из предыдущего примера, выясняем, что

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

• переменная x на каждом шаге цикла делится на 8 и остаток отбрасывается
• переменная 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. Т.к. нас интересует максимальное число, то цифры нужно выстроить в порядке убывания:

654 8

8. заметим, что получено число в восьмеричной системе, а ответ нужно дать в десятичной

• переводим: 654 8 = 6·8 2 + 5·8 1 + 4·8 0 = 428

Ответ: 428

0 do begin d := x mod 10; R := 10* R + d ; x := x div 10 end; writeln( R ) end. Данный алгоритм выводит наименьшее двузначное число R ( x - записанное в обратном порядке), у которого сумма цифр равна 16. Ответ: 79 " width="640"

ДЕМО - 2017

Ниже на языке программирования записан алгоритм. Получив на вход натуральное число x , этот алгоритм печатает число R . Укажите такое число x , при вводе которого алгоритм печатает двузначное число , сумма цифр которого равна 16 . Если таких чисел x несколько, укажите наименьшее из них.

var x,d,R: longint;

begin

readln( x );

R := 0;

while x 0 do

begin

d := x mod 10;

R := 10* R + d ;

x := x div 10

end;

writeln( R )

end.

Данный алгоритм выводит наименьшее двузначное число R ( x - записанное в обратном порядке), у которого сумма цифр равна 16.

Ответ: 79