Погода
Календарь
Май 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 12345
6789101112
13141516171819
20212223242526
2728293031  
Страницы сайта

Выполнение алгоритмов для исполнителя.

АЛГОРИТМ ВЕТВЛЕНИЕ

Блок-схема разветвляющегося алгоритма выглядит следующим образом:

Полная форма ветвления

Что в словесной форме будет звучать так:

  • ввод a и b;
  • если a больше b, то переменной max присваиваем значение a, иначе переменной max присваиваем значение b;
  • вывод max.

Реализуем это в Паскале:

Ветвление в Паскале

Ветвление бывает неполное, в таком случае отсутствует блок «иначе»:

Неполная форма ветвления

На Паскале:

Неполная форма условного оператора

ЦИКЛ СО СЧЕТЧИКОМ (С ПЕРЕМЕННОЙ)

Рассмотрим блок-схему работы цикла со счетчиком (счетчик считает, сколько раз выполнилось тело цикла):

Блок — схема цикла со счётчиком

Что словесно будет означать следующее:

  • i равно 0;
  • если i равно 5, то заканчиваем программу, иначе выводим на экран слово Привет и увеличиваем i на единицу;
  • возвращаемся к проверке i (к предыдущему пункту).

На языке Паскаль цикл со счетчиком выглядит так:

Цикл со счетчиком
Цикл со счётчиком


Если в теле цикла более одного оператора:

В теле цикла больше одного оператора

Бывает так, что в программе удобней счетчик отсчитывать обратно:

Цикл с обратным счётчиком

ЦИКЛ С ПРЕДУСЛОВИЕМ

Рассмотрим блок-схему цикла с предусловием:

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

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

  • вводится число n
  • присваивается 0 (т.е. обнуляем счетчик)
  • пока n не равно 0 выполняем:
    • увеличиваем c на единицу
    • делим целочисленно n на 10 и n присваиваем получившееся значение
  • выводим значение c
  • конец

Теперь рассмотрим этот алгоритм в Паскале:

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

ЦИКЛ С ПОСТУСЛОВИЕМ

Рассмотрим блок-схему:

Цикл с постусловием

Что дословно означает:

  • вводится n
  • если n больше 0 то продолжаем программу, иначе возвращаемся к предыдущему пункту (ввод n)

В Паскале:

Цикл с постусловием, Паскаль

Решение заданий.

Задание 1: Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
заменить (v, w)
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.
нашлось (v)
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (222) ИЛИ нашлось (555)
ЕСЛИ нашлось (222)
ТО заменить (222, 5)
ИНАЧЕ заменить (555, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из
А) 247 идущих подряд цифр 5?
Б) 247 идущих подряд цифр 2?
В ответе запишите полученную строку.

Решение:

  1. Рассмотрим алгоритм решения для  пункта А. Дана последовательность из 247 пятерок. Вначале, так как трёх «2» в последовательности нет, согласно алгоритму, первые три «5» заменяются одной «2». Получается одна «2» и двести сорок четыре «5».
  2. Так как еще не набирается  трёх «2», происходит следующая замена трёх «5» на «2». И имеется теперь две «2» и двести сорок одна «5».
  3. Трёх «2» по-прежнему нет, поэтом опять три следующие «5» заменяются на «2», и теперь имеем три «2» и двести тридцать восемь «5». Так как появились три «2», они заменяются на одну «5».
  4. Далее операции повторяются. Таким образом, девять «5» заменяются на одну «5», то есть можем сказать, что при каждом повторении описанных выше действий вычеркиваются по восемь «5».
  5. Поэтому найдем, сколько «5» остались невычеркнутыми. Для этого вычислим целочисленный остаток от деления 247 (количество «5» по условиям вначале) на 8. Это 7. То есть остаются семь «5»: 5555555.
  6. Теперь заменим первые три «5» двойкой, получится 25555. Далее снова заменим три «5» на «2», и в итоге ответ: 225.
  7.          Как же поступить, если остаток от деления равен 0? Например, будут даны вначале двадцать четыре «5». Тогда выполним шаг назад, когда оставались последние восемь «5» и преобразуем последовательность. Имеем: 55555555, далее 255555, затем 2255.
  8. Теперь рассмотрим решение для пункта Б. Дана последовательность из 247 двоек. Первые три «2» заменяются «5», далее следующие три «2» заменяются на «5», и следующие три «2» заменяются «5».
  9. Несмотря на то, что набирается три «5», не происходит замена трех «5» на «2», так как ветвь «Иначе» выполняется только в том случае, если не отработала ветвь «То». А так как далее идет последовательность  «2», в которой количество «2»  больше, чем две, происходит замена следующих идущих подряд трех «2» на «5», и так далее.
  10. Подсчитаем, сколько раз три «2» заменятся на «5». Вычислим целую часть от деления 247 на 3. Это 82. То есть в последовательности станет восемьдесят две «5»  и оставшаяся одна «2» (целочисленный остаток от деления 247 на 3).
  11. Теперь к последовательности «5» применим алгоритм,  описанный в пункте А. Найдем целочисленный остаток от деления 82 на 8. Это будет 2, то есть останется две «5» и плюс еще одна «2», полученная ранее. Имеем последовательность «552».

Ответ: А) 225. Б) 552.

Задание 2:  Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w)

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w.

Б) нашлось (v)

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка при этом не изменяется.

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (222) ИЛИ нашлось (888)

  ЕСЛИ нашлось (222)

    ТО заменить (222, 8)

    ИНАЧЕ заменить (888, 2)

  КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 68 идущих подряд цифр 8? В ответе запишите полученную строку.

Решение:

  1. из программы видим, что Редактор что-то делает только тогда, когда в строке есть цепочка 222 или цепочка 888; то есть, если ни одной из этих цепочек нет, программа останавливается
  2. если в строке есть 222, то, в первую очередь, именно эта цепочка меняется (на 8)
  3. если в строке нет цепочки 222, но есть 888, то цепочка 888 меняется на 2
  4. попробуем формально выполнить первые шаги алгоритма для цепочки цифр 8
  5. сначала первые 888 меняются на 2, получается
    2 [65 цифр 8]
  6. дальше так же меняем следующие две тройки из цифр 8:
    222 [59 цифр 8]
  7. теперь у нас появилась цепочка 222, поэтому в соответствии с алгоритмом она сразу будет заменена на 8, получаем
    [60 цифр 8]
  8. таким образом, за первые 4 шага работы цикла мы заменили 9 восьмерок на 1 или, что то же самое, удалили 8 восьмерок
  9. очевидно, что следующие 4 шага удалят ещё 8 восьмерок и т.д.
    сколько раз мы сможем это сделать? видимо, 8 раз, после этого останется 68 — 8·8 = 4 восьмерки
  10. итак, в цепочке 8888 на последнем шаге заменяем 888 на 2 и получаем 28

Ответ: 28.

Задание 3: Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a; y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).
Цикл  
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным). Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа):
НАЧАЛО
сместиться на (–1, –2)
ПОВТОРИ n РАЗ
сместиться на (a, b)
сместиться на (-1, -2)
КОНЕЦ ПОВТОРИ
сместиться на (–24, -12)
КОНЕЦ
Укажите наибольшее возможное значение числа n, для которого найдутся такие значения чисел a и b, что после выполнения программы Чертёжник возвратится в исходную точку.

Решение:

  1. запишем общее изменение координат Чертёжника в результате выполнения этого алгоритма:
  • поскольку Чертёжник должен вернуться в исходную точку, эти величины должны быть равны нулю; следовательно, нужно найти набольшее натуральное n, при котором система уравнений

разрешима в целых числах относительно a и b

  • несложно заметить, что для этого число n должно быть одновременно делителем чисел 14 и 25
  • наибольший общий делитель чисел 14 и 25 равен 1

Ответ – 1.

Задание 4:  Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
вверх                  вниз           влево         вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно                   снизу свободно
слева свободно           справа свободно
Цикл
ПОКА < условие >
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно. В конструкции
ЕСЛИ < условие >
ТО команда 1
ИНАЧЕ команда 2
выполняется команда 1 (если условие истинно) или команда 2 (если условие ложно). Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.
Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка А1)?

1) 8             2) 12          3) 17                    4) 21

ПОКА слева свободно ИЛИ сверху свободно
ЕСЛИ слева свободно
ТО влево
ИНАЧЕ вверх
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

Решение:

  • в программе один цикл со сложным условием, внутри которого расположен условный оператор «если»
  • в этой программе Робот не может разрушиться, так как возможность шага влево проверяется, а если влево ходить нельзя, то можно идти вверх, так как условие цикла «слева свободно ИЛИ сверху свободно» выполнено
  • Робот останавливается в клетке, где нарушается условие «слева свободно ИЛИ сверху свободно», в этой клетке должны быть стенки слева и сверху; таких клеток на поле всего три: конечная цель маршрута А1 и две «ложные цели» в В3 и Е1:
  • из п. 2 и 3 следует, что Робот успешно придет в клетку А1, если только он не попадёт в клетки В3 и Е1
  • подсчитаем, сколько есть клеток, из которых Робот попадает в клетку В3; Робот сначала идет влево до упора, потом – вверх, пока не упрётся в стенку сверху или не откроется «окно» влево; отметим голубым цветом все клетки, из которых Робот попадает в  В3, их всего 13
  • кроме того, есть две клетки, из которых Робот попадает в Е1, они показаны фиолетовым цветом:
  • таким образом, на поле есть всего 15 клеток, из которых Робот при выполнении заданной программы не попадает в клетку А1
  • следовательно, «нужных» клеток 36 – 15 = 21

Ответ: 4.

 Задание 5:  В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a, b, c имеют тип «строка», а переменные i, k – тип «целое». Используются следующие функции:
Длина(a) – возвращает количество символов в строке a. (Тип «целое»)
Извлечь(a,i) – возвращает i-тый (слева) символ в строке a. (Тип «строка»)
Склеить(a,b) – возвращает строку, в которой записаны сначала все символы строки a, а затем все символы строки b. (Тип «строка»)
Значения строк записываются в одинарных кавычках (Например, a:=’дом’). Фрагмент алгоритма:
i := Длина(a)
k := 2
b := ‘А’
пока i > 0
нц
c := Извлечь(a,i)
b := Склеить(b,c)
i := i – k
кц
b := Склеить(b,’Т’)
Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ‘ПОЕЗД’?
1) ‘АДЕПТ’      2) ‘АДЗЕОП’                             3) ‘АДТЕТПТ’  
         4) ‘АДЕОТ’

Решение:

  • эта задача более близка к классическому программированию, здесь выполняется обработка символьных строк; вся информация для успешного решения, вообще говоря, содержится в условии, но желательно иметь хотя бы небольшой опыт работы с символьными строками на Паскале (или другом языке)
  • заметим, что последняя команда алгоритма, b:=Склеить(b,’Т’), добавляет букву ‘Т’ в конец строки b, поэтому ответ 2 – явно неверный (строка должна оканчиваться на букву ‘Т’, а не на ‘П’)
  • для решения будем использовать ручную прокрутку; здесь пять переменных: a, b, c, i, k, для каждой из них выделим столбец, где будем записывать изменение ее значения
  • перед выполнением заданного фрагмента мы знаем только значение a, остальные неизвестны (обозначим их знаком вопроса):
  • в первой команде длина строки a (она равна 5 символам) записывается в переменную i:
  • следующие два оператора записывают начальные значения в k и b:
  • далее следует цикл пока с проверкой условия i>0 в начале цикла; сейчас i=5>0, то есть,  условие выполняется, цикл начинает работать и выполняются все операторы в теле цикла:
  • поскольку i=5, вызов функции Извлечь(a,i) выделяет из строки a символ с номером 5, это ‘Д’;
  • следующей командой этот символ приписывается в «хвост» строки b, теперь в ней хранится цепочка ‘АД’;
  • в команде i:=i-k значение переменной i уменьшается на k (то есть, на 2)
  • далее нужно перейти в начало цикла и снова проверить условие i>0, оно опять истинно, поэтому выполняется следующий шаг цикла, в котором к строке b добавляется 3-й символ строки a, то есть ‘Е’:
  • условие i>0 истинно, поэтому тело цикла выполняется еще один раз, к строке b добавляется 1-й символ строки a, то есть ‘П’:
  • теперь i=-1, поэтому при очередной проверке условие i>0 в начале цикла оказывается ложным, выполнение цикла заканчивается, и исполнителю остается выполнить единственную строчку после цикла, которая дописывает в конец строки b букву ‘Т’:
  • у нас получилось, что в конце выполнения фрагмента алгоритма в переменной b будет записана последовательность символов ‘АДЕПТ’

Ответ – 1.

Задание 6:   Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
вверх                  вниз                    влево         вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно                   снизу свободно
слева свободно           справа свободно
Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку.

Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет (не врежется в стену)?
1) 1             2) 13                  3) 21               4) 39
НАЧАЛО
ПОКА <снизу свободно> вниз
ПОКА <слева свободно> влево
вверх
вверх
КОНЕЦ

Решение:

  • нарисуем примерный путь Робота в соответствии с программой; вот три варианта, когда Робот не разбивается:

здесь ключевые клетки – две стенки (слева и снизу) и три ярко-зеленых клетки, которые должны быть свободны

  • теперь ищем на карте участки, где есть все ключевые клетки (они выделены на рисунке):

обратите внимание, что в двух случаях нижняя «ключевая» стенка имеет длину больше 1 (темно-коричневый цвет), то есть Робот может спускаться по разным линиям.

  • теперь осталось подсчитать все клетки, спускаясь из которых Робот упирается в темно-коричневые стенки:
  • подсчет показывает, что их 39 штук;

Ответ – 4.

Задание 7:  Ис­пол­ни­тель Чертёжник пе­ре­ме­ща­ет­ся на ко­ор­ди­нат­ной плос­ко­сти, остав­ляя след в виде линии. Чертёжник может вы­пол­нять ко­ман­ду сме­стить­ся на (a, b), где a, b — целые числа. Эта ко­ман­да пе­ре­ме­ща­ет Чертёжника из точки с ко­ор­ди­на­та­ми (x, y) в точку с ко­ор­ди­на­та­ми (x + a, y + b). На­при­мер, если Чертёжник на­хо­дит­ся в точке с ко­ор­ди­на­та­ми (4, 2), то ко­ман­да сме­стить­ся на (2, −3) пе­ре­ме­стит Чертёжника в точку (6, −1).
Цикл
ПО­ВТО­РИ число РАЗ
по­сле­до­ва­тель­ность ко­манд
КОНЕЦ ПО­ВТО­РИ
озна­ча­ет, что
по­сле­до­ва­тель­ность ко­манд будет вы­пол­не­на ука­зан­ное число раз (число долж­но быть на­ту­раль­ным).
 Чертёжнику был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм (ко­ли­че­ство по­вто­ре­ний и сме­ще­ния в пер­вой из по­вто­ря­е­мых ко­манд не­из­вест­ны):
НА­ЧА­ЛО
сме­стить­ся на (5, 2)
ПО­ВТО­РИ … РАЗ
сме­стить­ся на (…, …)
сме­стить­ся на (−1, −2)
КОНЕЦ ПО­ВТО­РИ
сме­стить­ся на (−25, −12)
КОНЕЦ 
После вы­пол­не­ния этого ал­го­рит­ма Чертёжник воз­вра­ща­ет­ся в ис­ход­ную точку. Какое наи­боль­шее число по­вто­ре­ний могло быть ука­за­но в кон­струк­ции «ПО­ВТО­РИ … РАЗ»?.

Решение:

Обо­зна­чим не­из­вест­ное сме­ще­ние по оси x, по оси y как a и b, не­из­вест­ное ко­ли­че­ство по­вто­ре­ний как n.

После вы­пол­не­ния ко­манд сме­стить­ся на (5, 2) и (−25, −12) Чертёжник ока­жет­ся в точке с ко­ор­ди­на­та­ми (−20, −10). После вы­пол­не­ния цикла Чертёжник пе­ре­ме­стит­ся на n · (a − 1, b − 2).

По­сколь­ку тре­бу­ет­ся, чтобы после вы­пол­не­ния про­грам­мы Четрёжник вер­нул­ся в ис­ход­ную точку, имеем два урав­не­ния: n · (a − 1) = −20 и n · (b − 2) = −10.

Пе­ре­мен­ные a, b и n долж­ны быть це­лы­ми, причём n > 1. Сле­до­ва­тель­но, числа −20 и −10 долж­ны быть крат­ны n. Наи­боль­шее под­хо­дя­щее n равно 10.

Ответ: 10.

Задание 8. Демоверсия ЕГЭ 2018 информатика (ФИПИ).
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x,y) в точку с координатами (x + a, y + b).
Чертёжнику был дан для исполнения следующий алгоритм (число повторений и величины смещения в первой из повторяемых команд неизвестны):
НАЧАЛО
сместиться на (4, 6)
ПОВТОРИ … РАЗ
сместиться на (…, …)
сместиться на (4, -6)
КОНЕЦ ПОВТОРИ
сместиться на (-28, -22)
КОНЕЦ

В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?

Ответ: 8

Top