Тест: Теория алгоритмов №3 — Информатика 11 класс
Тест: Теория алгоритмов №3 — Информатика 11 классАнглийский язык
Астрономия
Белорусский язык
Биология
География
ИЗО
Информатика
История
Итальянский язык
Краеведение
Литература
Математика
Музыка
Немецкий язык
ОБЖ
Обществознание
Окружающий мир
ОРКСЭ
Русский язык
Технология
Физика
Физкультура
Химия
Черчение
Для учителей
Дошкольникам
VIP — доступ
- Предметы »
- Информатика »
- 11 класс »
- Теория алгоритмов №3
Теория алгоритмов №3
Информатика 11 класс | Автор: Гайнанова Эльвина Назимовна | ID: 9292 | Дата: 21.3.2017
Помещать страницу в закладки могут только зарегистрированные пользователи
Зарегистрироваться
Вопрос №
1
Рекурсия в алгоритме будет прямой, когда:
рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение;
порядок следования команд определяется в зависимости от результатов проверки некоторых условий;
команда обращения алгоритма к самому себе находится в самом алгоритме;
один вызов алгоритма прямо следует за другим.
Вопрос №
2
Рекурсия в алгоритме будет косвенной, когда:
рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение;
команда обращения алгоритма к самому себе находится в самом алгоритме;
один вызов алгоритма прямо следует за другим.
Вопрос №
3
Команда машины Поста имеет структуру п Km, где:
n — действие, выполняемое головкой; К — номер следующей команды, подлежащей выполнению; m — порядковый номер команды;
n — порядковый номер команды; К — действие, выполняемое головкой; m — номер следующей команды, подлежащей выполнению;
n — порядковый номер команды; К — номер следующей команды, подлежащей выполнению; m — действие, выполняемое головкой;
Вопрос №
4
Сколько существует команд у машины Поста:
2
4
6
8
Вопрос №
5
В машине Поста останов будет результативным:
при выполнении недопустимой команды;
если машина не останавливается никогда;
если результат выполнения программы такой, какой и ожидался;
по команде «Стоп».
Вопрос №
6
В машине Поста некорректным алгоритм будет в следующем случае:
при выполнении недопустимой команды;
результат выполнения программы такой, какой и ожидался;
машина не останавливается никогда;
по команде «Стоп».
Вопрос № 7
В машине Тьюринга предписание L для лентопротяжного механизма означает:
переместить ленту вправо;
переместить ленту влево;
остановить машину;
занести в ячейку символ.
Вопрос №
8
В машине Тьюринга предписание R для лентопротяжного механизма означает:
переместить ленту вправо;
переместить ленту влево;
остановить машину;
занести в ячейку символ.
В машине Тьюринга предписание S для лентопротяжного механизма означает:
переместить ленту вправо;
переместить ленту влево;
остановить машину;
занести в ячейку символ.
Вопрос №
10
В алгоритме Маркова ассоциативным исчислением называется:
совокупность всех слов в данном алфавите;
совокупность всех допустимых систем подстановок;
совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;
когда все слова в алфавите являются смежными.
Показать ответы
Получение сертификата
о прохождении теста
Доступно только зарегистрированным пользователям
© TestEdu.ru 2013-2022
E-mail администратора: [email protected]
Косвенная рекурсия — Большая Энциклопедия Нефти и Газа, статья, страница 1
Cтраница 1
Косвенная рекурсия означает, что одна процедура вызывает другую процедуру, а это в свою очередь прямо или косвенно приводит к вызову первоначальной процедуры. [1]
В случае косвенной рекурсии возникает проблема: как и где описать вызываемый модуль. [2]
Все сказанное выше будет также верно и для так называемой косвенной рекурсии — когда подпрограмма А вызывает подпрограмму В, а в В содержится вызов А. [3]
Алгоритм рисования кривых Серпинского, представленный ранее, включает в себя и множественную, и косвенную рекурсию. Поскольку алгоритм состоит из четырех подпрограмм, которые вызывают друг друга, нельзя просто пронумеровать важные строки программы, как в случае с алгоритмом Гильбертовых кривых.
[4]
Рекурсивные процедуры и функции ( модули) имеют одну из двух форм: прямую рекурсию и
В, являющейся копией объекта С, имеющего в качестве компоненты указанное выше имя А. Иными словами, исключается косвенная рекурсия в определениях. [6]
Методы, описанные в предыдущем разделе, используются, когда алгоритм содержит многократную или косвенную рекурсию. [7]
В рассмотренных выше случаях процедуры или функции вызывали себя сами, это называется прямой рекурсией. Кроме того, процедура Р может вызывать процедуру Q, которая в свою очередь вызывает процедуру Р: это называется
[8]
В рассмотренных выше случаях процедуры или функции вызывали себя сами, это называется прямой рекурсией. Кроме того, процедура Р может вызывать процедуру Q, которая в свою очередь вызывает процедуру Р: это называется косвенной рекурсией. Ниже приведен пример, в котором используется
Тот факт, что АЛГОЛ допускает рекурсию, вызван разнообразными причинами, поскольку нужда в рекурсии при решении задач численного анализа не столь очевидна. Некоторые приверженцы АЛГОЛа утверждают, что наличие рекурсии является его основным преимуществом перед другими языками типа ФОРТРАНа. Хотя это утверждение и справедливо для рекурсивно определенных функций, оно неверно для рекурсивного использования процедур ( иногда называемого косвенной рекурсией), которое, как мы видели, имеет важное значение для численного анализа. [10]
Тот факт, что АЛГОЛ допускает рекурсию, вызван разнообразными причинами, поскольку нужда в рекурсии при решении задач численного анализа не столь очевидна.
Рекурсивная процедура может выполняться косвенно, вызывая вторую процедуру, которая, в свою очередь, вызывает первую. Алгоритм кривых Серпинского, рассматриваемый в главе 5, включает в себя четыре процедуры, которые являются одновременно и
Функция может вызывать самое себя. Это называется рекурсией, которая может быть прямой или косвенной. Когда функция вызывает самое себя, речь идет о прямой рекурсии. Если же функция вызывает другую функцию, которая затем вызывает первую, то в этом случае имеет место косвенная рекурсия.
[13]
Страницы: 1
parsing — Пошаговое устранение этой непрямой левой рекурсии
Asked
Изменено 8 лет, 6 месяцев назад
Просмотрено 23k раз
14
Новинка! Сохраняйте вопросы или ответы и организуйте свой любимый контент.
Узнать больше.
Я видел этот алгоритм, который можно использовать для удаления всей левой рекурсии. Тем не менее, у меня возникают проблемы с этой конкретной грамматикой:
А -> CD В -> Се С -> А | Б | ф
Что бы я ни пытался, я получаю циклы или грамматику, которая по-прежнему является непрямой леворекурсивной.
Как правильно реализовать этот алгоритм в этой грамматике?
- разбор
- контекстно-свободная грамматика
- левая рекурсия
1
Правило состоит в том, что вы сначала устанавливаете какой-то порядок для нетерминалов, а затем находите все пути, где происходит непрямая рекурсия.
В этом случае порядок будет A < B < C, а возможные пути рекурсии нетерминала C будут
C=> A => Cd
и
C=> B => Ce
, поэтому новые правила для C будут
C=> Cd | Се | ф
теперь вы можете просто удалить прямую левую рекурсию:
C=> fC' С'=> дС' | еС' | прибыль на акцию
и результирующая нерекурсивная грамматика будет:
A => Cd Б => Се С => fС' С' => дС' | еС' | прибыль на акцию
0
Уже разобрался.
Меня смутило то, что в этом порядке алгоритм, казалось, ничего не делал, поэтому я решил, что это должно быть неправильно, и начал заменять A -> Cd в первой итерации (игнорирование j не может выходить за пределы i), попадая в бесконечные циклы.
1) Путем переупорядочения правил:
C -> A | Б | ф А -> CD В -> Се
2) заменить C в A -> Cd
C -> A | Б | ф А -> Объявление | Бд | фд В -> Се
3) B еще не в диапазоне j, так что оставьте это и замените прямую левую рекурсию A
C -> A | Б | ф А -> БдА' | Управление по санитарному надзору за качеством пищевых продуктов и медикаментов А'-> дА' | эпсилон В -> Се
4) заменить C в B -> Ce
C -> A | Б | ф А -> БдА' | Управление по санитарному надзору за качеством пищевых продуктов и медикаментов А'-> дА' | эпсилон В -> Ае | Быть | фе
5) еще не сделано! также необходимо заменить новое правило B -> Ae (производство A находится в диапазоне j)
C -> A | Б | ф А -> БдА' | Управление по санитарному надзору за качеством пищевых продуктов и медикаментов А'-> дА' | эпсилон B -> BdA'e | фда | Быть | фе
6) заменить прямую левую рекурсию в постановках B
C -> A | Б | ф А -> БдА' | Управление по санитарному надзору за качеством пищевых продуктов и медикаментов А'-> дА' | эпсилон B -> fdA'eB' | feB' B'-> dA'eB' | еБ' | эпсилон
ура! грамматика без левой рекурсии!
3
Зарегистрируйтесь или войдите в систему
Зарегистрируйтесь с помощью Google
Зарегистрироваться через Facebook
Зарегистрируйтесь, используя адрес электронной почты и пароль
Опубликовать как гость
Электронная почта
Обязательно, но не отображается
Опубликовать как гость
Электронная почта
Требуется, но не отображается
Разбор— Косвенная левая рекурсия в моей грамматике?
Спросил
Изменено 6 лет, 11 месяцев назад
Просмотрено 182 раза
Новинка! Сохраняйте вопросы или ответы и организуйте свой любимый контент.
Узнать больше.
Моя грамматика, похоже, имеет случай косвенной левой рекурсии, я посмотрел на некоторые другие похожие вопросы, не могу установить ментальную связь между ними и моей грамматикой, я не могу понять, как это решить.
А ::= А' а
| А
| б
А' ::= с
| А
A' вызывается из A , но A' — это c или A , это вызывает левую рекурсию, как это можно преобразовать в эквивалентную грамматику, исключив левую рекурсию?
- разбор
- рекурсия
- построение компилятора
- грамматика
- левая рекурсия
У вас есть следующие продукты:
a 1: A -> A' 2: А -> А 3: А -> б 4: А' -> с 5: А' -> А
Во-первых, обратите внимание, что постановка № 2 делает эту грамматику двусмысленной и на самом деле бессмысленной. Давайте удалим его.
1: А -> А' а 3: А -> б 4: А' -> с 5: А' -> А
Статья «Левая рекурсия» в Википедии содержит алгоритм (без источника) для устранения всей левой рекурсии, включая непрямую левую рекурсию.