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


Интерактивный тренажер 20 ЕГЭ ДЕМО 2017
"Анализ программы, содержащей подпрограммы, циклы и ветвления"


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


Разбор решения задания 20 демоверсии ЕГЭ 2016
Анализ программы, содержащей подпрограммы, циклы и ветвления
с последующей отработкой на интерактивном тренажере

Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т.е. большее 100) число x, при вводе которого 11алгоритм печатает 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.

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

Подробнее познакомиться с методом трассировки и поэкспериментировать с алгоритмом Евклида можно на одноименном интерактивном тренажере  - демонстрации, расположенном по этой ссылке: http://somit.ru/2016/demo_evklida.html

Ниже показан программный код этого алгоритма, где первая строка есть ничто иное, как команда цикла, который будет выполняться до тех пор, пока выполняется условие: L <> M

while L <> M do  
if L > M then  
L := L – M       
else    
M := M – L;    

А по завершении его выводится на печать значение переменной M, содержащей наибольший общий делитель

writeln(M);

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

Следовательно, введенное число x было четным, а командная строка:

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

заменила значение M с 65 на 52. Откуда делаем вывод, что нужно найти чётное число x, большее 100, такое, что НОД(x,52)=26

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

Поэтому берём следующее число, которое делится на 26: 104 + 26 = 130

Итого правильный ответ: 130


Интерактивный тренажер по заданию 20 демоверсии ЕГЭ 2016 на
Анализ программы, содержащей подпрограммы, циклы и ветвления

Анимации, сопутствующие успешному пониманию данного вопроса:

Интерактивная демонстрация алгоритма Евклида

Интерактивная демонстрация с тренажером и тестовой программой


Интерактивный тренажер 20 ЕГЭ ДЕМО 2015
на "Анализ программы, содержащей подпрограммы, циклы и ветвления"

 

Примеры задач, генерируемых интерактивным тренажером 20 ЕГЭ ДЕМО 2015 на
"Анализ программ, содержащих подпрограммы, циклы и ветвления"
с решением и проверкой методом прокрутки

 

Задание №1.

Ниже записана программа. Получив на вход число x, эта программа печатает два числа. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 3, а потом 8.
var x, L, M: integer;
begin readln(x);
L:=0; M:=0;
while x > 0 do begin
L:=L+1;
if (M < x) and (x mod 2 = 0) then begin;
M:= (x mod 10);
end;
x:= x div 10;
end;
writeln(L); write(M);
end.

Решение:
Для решения задачи необходимо понять, что делает эта программа Видим, что переменная L с каждым шагом цикла увеличивается на 1 Переменная x на каждом шаге цикла делится на 10 и остаток отбрасывается L = 3, это означает, что цикл прокрутился 3 раза, следовательно, и остатков будет взято 3, но только в том случае, если М будет меньше х, и, х - четное, при этом новый остаток будет заменять старое значение на новое Нам нужно найти наименьшее число х, следовательно, первый остаток (с учетом системы счисления) должен быть равен 8 Догадайтесь самостоятельно, почему следующие два остатка могут быть только такими: 1 и 1 Вот и все, задача решена! Но, на всякий случай проверим свое решение простой прокруткой

ПРОВЕРКА:
пусть х = 118, тогда проверяем условие 118 > 0 - ДА - входим в цикл L := L + 1 : =>0 + 1 = 1 M < х; (x mod 10) = 8; => 0 =(118 mod 10 ) = 8 х = 118 div 10; => х = 11 проверяем условие 11 > 0 - ДА - входим в цикл L := L + 1 : =>1 + 1 = 2 х = 11 div 10; => х = 1 проверяем условие 1 > 0 - ДА - входим в цикл L := L + 1 : =>2 + 1 = 3 х = 1 div 10; => х = 0 L = 3: M = 8

Правильный ответ = 118

 

Задание №2.

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

var x, L, M: integer;
begin
readln(x);
L:=0; M:=0;
while x > 0 do begin
L:=L+1;
if x mod 2 = 1 then begin
M:= M + (x mod 8);
end;
x:= x div 8;
end;
writeln(L); write(M);
end.

Решение:
Для решения задачи необходимо понять, что делает эта программа Видим, что переменная L с каждым шагом цикла увеличивается на 1 Переменная x на каждом шаге цикла делится на 8 и остаток отбрасывается L = 3, это означает, что цикл прокрутился 3 раза, следовательно, и остатков будет взято 3 Очевидно, что в М сохранится сумма остатков от нечетных значений х, в данном случае она = 8 Исходя из этого, формируем строку из остатков: 107 Нам остается полученную из остатков строку: 107 перевести в десятичную систему счисления 1*8^2 + 0*8^1 + 7*8^0 = 71 Вот и все, задача решена! Но, на всякий случай проверим свое решение простой прокруткой

ПРОВЕРКА:
пусть х = 71, тогда проверяем условие 71 > 0 - ДА - входим в цикл L := L + 1 : =>0 + 1 = 1 (x mod 8) - нечетное => 0 < (71 mod 8 ); M = 7 х = 71 div 8; => х = 8 проверяем условие 8 > 0 - ДА - входим в цикл L := L + 1 : =>1 + 1 = 2 х = 8 div 8; => х = 1 проверяем условие 1 > 0 - ДА - входим в цикл L := L + 1 : =>2 + 1 = 3 (x mod 8) - нечетное => 7 < (1 mod 8 ); M = 8 х = 1 div 8; => х = 0 L = 3: M = 8

Правильный ответ = 71

 

Задание №3.

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

var x, L, M: integer;
begin
readln(x);
L:=0; M:=0;
while x > 0 do begin
L:=L+1;
if (M < x) and (x mod 2 = 1) then begin;
M:= (x mod 10);
end;
x:= x div 10;
end;
writeln(L); write(M);
end.

Решение:
Для решения задачи необходимо понять, что делает эта программа Видим, что переменная L с каждым шагом цикла увеличивается на 1 Переменная x на каждом шаге цикла делится на 10 и остаток отбрасывается L = 3, это означает, что цикл прокрутился 3 раза, следовательно, и остатков будет взято 3, но только в том случае, если М будет меньше х, и, х - нечетное, при этом новый остаток будет заменять старое значение на новое Нам нужно найти наибольшее число х, следовательно, первый остаток (с учетом системы счисления) должен быть равен 8 Догадайтесь самостоятельно, почему следующие два остатка могут быть только такими: 9 и 9 Вот и все, задача решена! Но, на всякий случай проверим свое решение простой прокруткой

ПРОВЕРКА:
пусть х = 998, тогда проверяем условие 998 > 0 - ДА - входим в цикл L := L + 1 : =>0 + 1 = 1 х = 998 div 10; => х = 99 проверяем условие 99 > 0 - ДА - входим в цикл L := L + 1 : =>1 + 1 = 2 M < х; (x mod 10) = 9; => 0 =(99 mod 10 ) = 9 х = 99 div 10; => х = 9 проверяем условие 9 > 0 - ДА - входим в цикл L := L + 1 : =>2 + 1 = 3 х = 9 div 10; => х = 0 L = 3: M = 9

Правильный ответ = 998

 
© Северобайкальск, Russia
Александр Козлов, 2017

  Рейтинг@Mail.ru