Правила выполнения линейных, разветвляющихся и циклических алгоритмов icon

Правила выполнения линейных, разветвляющихся и циклических алгоритмов



НазваниеПравила выполнения линейных, разветвляющихся и циклических алгоритмов
страница1/11
Дата конвертации06.10.2012
Размер1.39 Mb.
ТипПравила
источник
  1   2   3   4   5   6   7   8   9   10   11

© К. Поляков, 2009-2010

A18 (высокий уровень, время – 6 мин)


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

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

  • правила выполнения линейных, разветвляющихся и циклических алгоритмов

  • основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну)

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

  • в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз

  • запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1
^

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


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

вверх вниз влево вправо.

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

сверху свободно снизу свободно

слева свободно справа свободно




















6



















5



















4



















3



















2



















1

A

B

C

D

E

F



Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?

1) 1 2) 2 3) 3 4) 0

^ НАЧАЛО

ПОКА <снизу свободно> вниз

ПОКА <слева свободно> влево

ПОКА <сверху свободно> вверх

ПОКА <справа свободно> вправо

КОНЕЦ




















































































































































Решение:

  1. легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо:

на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;

  1. кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода

  2. обратим внимание, что возможны еще «вырожденные» варианты, вроде таких:
































































  3. итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:

















    6

















    5


















    4


















    3

















    2

















    1

    A

    B

    C

    D

    E

    F









































































































































































  4. 6


















    5


















    4


















    3


















    2


















    1

    A

    B

    C

    D

    E

    F



    этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют:




  1. проверяем оставшиеся четыре клетки-кандидаты, но для каждой из них после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал:





















6



















5



















4



















3


















2



















1

A

B

C

D

E

F





















6



















5



















4



















3



















2



















1

A

B

C

D

E

F






















6


















5



















4



















3



















2



















1

A

B

C

D

E

F

























6



















5



















4



















3



















2


















1

A

B

C

D

E

F







  1. итак, условию удовлетворяет только одна клетка – F4

  2. таким образом, правильный ответ – 1.

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

    • вариантов может быть достаточно много, важно не пропустить ни один из них

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

    • нужно правильно определить свойства, по которым клетку можно считать «кандидатом»

    • можно не заметить стенку и таким образом получить лишнее решение
  1   2   3   4   5   6   7   8   9   10   11




Похожие:

Правила выполнения линейных, разветвляющихся и циклических алгоритмов iconПравила выполнения линейных, разветвляющихся и циклических алгоритмов
«начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз
Правила выполнения линейных, разветвляющихся и циклических алгоритмов iconАлгоритмическая структура "ветвление"
В отличие от линейных алгоритмов в алгоритмическую структуру ветвление входит условие. В зависимости от выполнения или невыполнения...
Правила выполнения линейных, разветвляющихся и циклических алгоритмов iconПрограммирование линейных алгоритмов
Вычислить периметр и площадь прямоугольного треугольника по заданным длинам двух катетов a и b
Правила выполнения линейных, разветвляющихся и циклических алгоритмов icon"Составление линейных алгоритмов."
В банк был положен вклад в размере n рублей. Через три года он увеличился на 50%. Сколько денег получил вкладчик?
Правила выполнения линейных, разветвляющихся и циклических алгоритмов iconРабота Программирование циклических алгоритмов на Паскале (к § 7) Суммы и произведения числовых последовательностей
Дан числовой ряд и некоторое малое число  (например, =0,00001). Найти сумму тех членов ряда, модуль которых больше или равен заданному...
Правила выполнения линейных, разветвляющихся и циклических алгоритмов iconКалендарно-тематическое планирование учебного материала алгебра и начала анализа, 10 класс
Решение рациональных неравенств (линейных, дробно – линейных и квадратных) методом интервалов
Правила выполнения линейных, разветвляющихся и циклических алгоритмов iconТема: Решение линейных неравенств в зависимости
Познакомить учащихся с алгоритмом решения линейных неравенств, содержащих параметр
Правила выполнения линейных, разветвляющихся и циклических алгоритмов iconУрок. Алгоритм и его свойства Цели урока: изучить понятие алгоритма; сформулировать свойства алгоритма; вырабатывать умения построения простейших (линейных) алгоритмов
Краткий анализ предыдущих знаний учащихся по понятию алгоритма. Мы изучали тему алгоритмы в 6 классе. Где можно встретить алгоритмы...
Правила выполнения линейных, разветвляющихся и циклических алгоритмов iconУрок алгебры в 7 классе. Тема: Решение линейных уравнений
Образовательная цель: углубить, расширить и обобщить сведения о линейных уравнениях и выражениях, умения по решению уравнений
Правила выполнения линейных, разветвляющихся и циклических алгоритмов iconКонспект урока взаимное расположение графиков линейных функций. Тема урока. Фио (полностью) Умарова Гульсум Амиржановна
Образовательная: повторить определение линейной функции, свойства графиков в зависимости от k и m; закрепить навыки построение графиков;...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib2.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы