Slider

Задача №14. Выполнение алгоритма.

Автор материалов - Лада Борисовна Есакова.

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

Основные конструкции псевдокода описаны перед текстом задачи.

Исполнитель чертежник

Пример 1.

Ис­пол­ни­тель Чертёжник пе­ре­ме­ща­ет­ся на ко­ор­ди­нат­ной плос­ко­сти, остав­ляя след в виде линии. Чертёжник может вы­пол­нять ко­ман­ду сме­стить­ся на (ab), где ab – целые числа. Эта ко­ман­да пе­ре­ме­ща­ет Чертёжника из точки с ко­ор­ди­на­та­ми (xy) в точку с ко­ор­ди­на­та­ми (x + ay + b).

На­при­мер, если Чертёжник на­хо­дит­ся в точке с ко­ор­ди­на­та­ми (4, 2), то ко­ман­да сме­стить­ся на (2, -3) пе­ре­ме­стит Чертёжника в точку (6, -1).

Цикл

ПО­ВТО­РИ число РАЗ

по­сле­до­ва­тель­ность ко­манд

КОНЕЦ ПО­ВТО­РИ

озна­ча­ет, что по­сле­до­ва­тель­ность ко­манд будет вы­пол­не­на ука­зан­ное число раз (число долж­но быть на­ту­раль­ным).

Чертёжнику был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм (бук­ва­ми nab обо­зна­че­ны не­из­вест­ные числа, n>1):

НА­ЧА­ЛО

сме­стить­ся на (60, 100)

ПО­ВТО­РИ n РАЗ

сме­стить­ся на (ab)

сме­стить­ся на (33, 44)

КОНЕЦ ПО­ВТО­РИ

сме­стить­ся на (13, 200)

сме­стить­ся на (-1, 60)

КОНЕЦ

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

 

Решение:

В результате выполнения алгоритма Чертежник переместится

по оси х на:

60 + n*a + n*33 + 13 – 1

по оси y на:

100 + n*b + n*44 + 200 + 60

Известно, что в результате перемещения Чертежник вернулся в исходную точку, т.е. перемещение по оси х равно нулю, и перемещение по оси y равно нулю:

60 + n*a + n*33 + 13 – 1 = 0

100 + n*b + n*44 + 200 + 60 = 0

Т.е.

n*(a + 33) = -72

n*(b + 44) = -360

Наибольшее n – это наибольший общий делитель чисел -72 и -360. Это число 72.

Ответ: 72

 

Исполнитель робот

Пример 2.

Си­сте­ма ко­манд ис­пол­ни­те­ля РОБОТ, «жи­ву­ще­го» в пря­мо­уголь­ном ла­би­рин­те на клет­ча­той плос­ко­сти:

вверх

вниз

влево

впра­во

При вы­пол­не­нии любой из этих ко­манд РОБОТ пе­ре­ме­ща­ет­ся на одну клет­ку со­от­вет­ствен­но (по от­но­ше­нию к на­блю­да­те­лю): вверх ↑, вниз ↓, влево ←, впра­во →.

Че­ты­ре ко­ман­ды про­ве­ря­ют ис­тин­ность усло­вия от­сут­ствия стены у каж­дой сто­ро­ны той клет­ки, где на­хо­дит­ся РОБОТ (также по от­но­ше­нию к на­блю­да­те­лю):

свер­ху
сво­бод­но

снизу
сво­бод­но

слева
сво­бод­но

спра­ва
сво­бод­но

Цикл

ПОКА < усло­вие >

по­сле­до­ва­тель­ность ко­манд

КОНЕЦ ПОКА

вы­пол­ня­ет­ся, пока усло­вие ис­тин­но.

В кон­струк­ции

ЕСЛИ < усло­вие >

ТО ко­ман­да1

ИНАЧЕ ко­ман­да2

КОНЕЦ ЕСЛИ

вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно)

 

Если РОБОТ начнёт дви­же­ние в сто­ро­ну на­хо­дя­щей­ся рядом с ним стены, то он раз­ру­шит­ся и про­грам­ма прервётся.

Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)?

 

НА­ЧА­ЛО

ПОКА снизу сво­бод­но ИЛИ спра­ва сво­бод­но ПОКА спра­ва сво­бод­но                                  

впра­во

КОНЕЦ ПОКА

вниз

КОНЕЦ ПОКА

КОНЕЦ

 

1) 22

2) 19

3) 15

4) 12

 

Решение:

В дан­ной про­грам­ме РОБОТ сначала про­ве­ря­ет, сво­бод­на ли клет­ка спра­ва или снизу от него. Если это так, то РОБОТ пе­ре­хо­дит к пер­во­му дей­ствию внут­ри цикла. В этом цикле пока у пра­вой сто­ро­ны клет­ки, в ко­то­рой на­хо­дит­ся РОБОТ, нет стены, он про­дол­жа­ет дви­гать­ся впра­во. Как толь­ко это усло­вие пе­ре­ста­нет вы­пол­нять­ся, он пе­ре­хо­дит ко вто­ро­му дей­ствию внут­ри цикла. Вто­рое дей­ствие, за­клю­ча­ет­ся в сле­ду­ю­щем: РОБОТ пе­ре­дви­га­ет­ся на одну клет­ку вниз. После чего воз­вра­ща­ет­ся к на­ча­лу внеш­не­го цикла.

Про­ве­рив последовательно все клет­ки по пра­ви­лу дви­же­ния РО­БО­ТА вы­яс­ня­ем, что число кле­ток, удо­вле­тво­ря­ю­щих усло­вию за­да­чи равно 15 (вся пер­вая строч­ка, весь стол­бец F, клет­ки D2, E2, D4, D6, E4).

 

Пра­виль­ный ответ ука­зан под но­ме­ром 3.

Ответ: 3

 

Исполнитель редактор

Пример 3.

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

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

Эта ко­ман­да за­ме­ня­ет в стро­ке пер­вое слева вхож­де­ние це­поч­ки v на це­поч­ку w. На­при­мер, вы­пол­не­ние ко­ман­ды за­ме­нить (111, 27) пре­об­ра­зу­ет стро­ку 05111150 в стро­ку 0527150. Если в стро­ке нет вхож­де­ний це­поч­ки v, то вы­пол­не­ние ко­ман­ды за­ме­нить (v, w) не ме­ня­ет эту стро­ку.

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

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

 

Цикл

ПОКА усло­вие

по­сле­до­ва­тель­ность ко­манд

КОНЕЦ ПОКА

вы­пол­ня­ет­ся, пока усло­вие ис­тин­но.

В кон­струк­ции

ЕСЛИ усло­вие

ТО ко­ман­да1

ИНАЧЕ ко­ман­да2

КОНЕЦ ЕСЛИ

вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно).

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

 НА­ЧА­ЛО

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

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

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

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

    КОНЕЦ ЕСЛИ

 КОНЕЦ ПОКА

 КОНЕЦ

 

Решение:

Обозначим строку из 68 восьмерок  - 68«8»,

строку из двойки и 65 восьмерок – 1«2»65«8» и т.д.

Отработаем 4 первых цикла программы:

68«8»  →  1«2»65«8»   →  2«2»62«8»   →  3«2»59«8»   →  60«8»

В результате количество восьмерок уменьшилось на 8. Не сложно понять, что строка будет уменьшаться на 8 восьмерок каждые 4 итерации. В результате останется строка из 4 восьмерок. Доработаем программу:

…→  4«8»  →  1«2»1«8»   = 28

Ответ: 28

 

Исполнитель черепашка

Пример 4.

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:

Вперед n, где n – целое число, вызывающее передвижение черепашки на n шагов в направлении движения.

Направо m, где m – целое число, вызывающее изменение направления движения на m градусов по часовой стрелке.

Запись Повтори 5 [Команда1 Команда2] означает, что последовательность команд в скобках повторится 5 раз.

Черепашке был дан для исполнения следующий алгоритм:

Повтори 5 [Повтори 4 [Вперед 40 Направо 90] Направо 120]

Какая фигура появится на экране?

Решение:

Последовательность действий Вперед 40 Направо 90 рисует отрезок длиной 40 шагов, а затем меняет направление на 90 градусов по часовой стрелке. Тогда последовательность Повтори 4 [Вперед 40 Направо 90] нарисует квадрат, а направление вернется в исходное.

Затем выполняется команда Направо 120, она изменит направление на 120 градусов от исходного.

Если повторить все рассмотренные действия 5 раз:

Повтори 5 [Повтори 4 [Вперед 40 Направо 90] Направо 120], то будет 5 раз нарисован квадрат. Причем каждый следующий повернут вокруг вершины относительно предыдущего на 120 градусов. Не сложно заметить, что 4-й  квадрат будет нарисован поверх первого (120*3 = 360, сделан поворот на целый круг, возврат в исходное положение), а 5-й поверх второго.

Результат изображен под номером 3.

Ответ: 3

 

Интенсивная подготовка

Бесплатные пробные ЕГЭ

Расписание курсов

Звоните нам: 8 (800) 775-06-82 (бесплатный звонок по России)
                       +7 (495) 984-09-27 (бесплатный звонок по Москве)

Или нажмите на кнопку «Узнать больше», чтобы заполнить контактную форму. Мы обязательно Вам перезвоним.

БЕСПЛАТНЫЙ РЕПЕТИЦИОННЫЙ ЕГЭ ОНЛАЙН

Типы подготовки:
Сказать спасибо
РЕКОМЕНДУЕМ:
ege-tv

Полный онлайн-курс подготовки к ЕГЭ по математике. Структурировано. Четко. Без воды. Сдай ЕГЭ на 100 баллов!

Смотреть

Для нормального функционирования и Вашего удобства, сайт использует файлы cookies. Это совершенно обычная практика.Продолжая использовать портал, Вы соглашаетесь с нашей Политикой конфиденциальности.

Позвоните мне

Все поля обязательны для заполнения

Отправить

Премиум

Вся часть 2 на ЕГЭ по математике, от задачи 13 до задачи 19. То, о чем не рассказывают даже ваши репетиторы. Все приемы решения задач части 2. Оформление задач на экзамене. Десятки реальных задач ЕГЭ, от простых до самых сложных.

Видеокурс «Премиум» состоит из 7 курсов  для освоения части 2 ЕГЭ по математике (задачи 13-19). Длительность каждого курса - от 3,5 до 4,5 часов.

  1. Уравнения (задача 13)
  2. Стереометрия (задача 14)
  3. Неравенства (задача 15)
  4. Геометрия (задача 16)
  5. Финансовая математика (задача 17)
  6. Параметры (задача 18)
  7. Нестандартная задача на числа и их свойства (задача 19).

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

Каждая тема разобрана с нуля. Десятки специально подобранных задач, каждая из которых помогает понять «подводные камни» и хитрости решения.  Автор видеокурса Премиум - репетитор-профессионал Анна Малкова.

Получи пятерку

Видеокурс «Получи пятерку» включает все темы, необходимые для успешной сдачи ЕГЭ по математике на 60-65 баллов. Полностью все задачи 1-13 Профильного ЕГЭ по математике. Подходит также для сдачи Базового ЕГЭ по математике. Если вы хотите сдать ЕГЭ на 90-100 баллов, вам надо решать часть 1 за 30 минут и без ошибок!

Курс подготовки к ЕГЭ для 10-11 класса, а также для преподавателей. Все необходимое, чтобы решить часть 1 ЕГЭ по математике (первые 12 задач) и задачу 13 (тригонометрия). А это более 70 баллов на ЕГЭ, и без них не обойтись ни стобалльнику, ни гуманитарию.

Вся необходимая теория. Быстрые способы решения, ловушки и секреты ЕГЭ. Разобраны все актуальные задания части 1 из Банка заданий ФИПИ. Курс полностью соответствует требованиям ЕГЭ-2018.

Курс содержит 5 больших тем, по 2,5 часа каждая. Каждая тема дается с нуля, просто и понятно.

Сотни заданий ЕГЭ. Текстовые задачи и теория вероятностей. Простые и легко запоминаемые алгоритмы решения задач. Геометрия. Теория, справочный материал, разбор всех типов заданий ЕГЭ. Стереометрия. Хитрые приемы решения, полезные шпаргалки, развитие пространственного воображения. Тригонометрия с нуля - до задачи 13. Понимание вместо зубрежки. Наглядное объяснение сложных понятий. Алгебра. Корни, степени и логарифмы, функция и производная. База для решения сложных задач 2 части ЕГЭ.

Сразу после оплаты вы получите ссылки на скачивание видеокурсов и уникальные ключи к ним.

Задачи комплекта «Математические тренинги - 2019» непростые. В каждой – интересные хитрости, «подводные камни», полезные секреты.

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

Как пользоваться?

  1. Не надо сразу просматривать задачи (и решения) всех вариантов. Такое читерство вам только помешает. Берите по одному! Задачи решайте по однойи старайтесь довести до ответа.
  2. Если почти ничего не получилось – начинать надо не с решения вариантов, а с изучения математики. Вам помогут книга для подготовки к ЕГЭи Годовой Онлайн-курс.
  3. Если вы правильно решили из первого варианта Маттренингов 5-7 задач – значит, знаний не хватает. Смотри пункт 1: Книгаи Годовой Онлайн-курс!
  4. Обязательно разберите правильные решения. Посмотрите видеоразбор – в нем тоже много полезного.
  5. Можно решать самостоятельно или вместе с друзьями. Или всем классом. А потом смотреть видеоразбор варианта.

Стоимость комплекта «Математические тренинги – 2019» - всего 1100 рублей. За 5 вариантов с решениями и видеоразбором каждого.