rekursia-mashiny_2011 (793942)
Текст из файла
Машинные задачи на рекурсию.
Часть 1 (обязательная) (срок сдачи: 6 декабря включительно)
12.14 – в разделе операторов программы (помимо выдачи информации об авторе и номере задачи, приглашения к вводу и удержания экрана с результатами) должен быть только один оператор writeln(max), где max – обращение к рекурсивной целочисленной функции без параметров; функция max вводит последовательность положительных чисел и находит их максимум. В основной программе запрещено описывать какие-либо переменные.
12.15 – в разделе операторов программы (помимо выдачи информации об авторе и номере задачи, приглашения к вводу и удержания экрана с результатами) должен быть только один оператор writeln(digits), где digits – обращение к рекурсивной функции без параметров; функция digits вводит последовательность символов и находит количество цифр (т.е. символов из диапазона ‘0’..’9’) среди них. В основной программе запрещено описывать какие-либо переменные.
12.16 – в разделе операторов программы (помимо выдачи информации об авторе и номере задачи, приглашения к вводу и удержания экрана с результатами) должен быть только один оператор PRINT, где PRINT – вызов рекурсивной процедуры без параметров; процедура PRINT считывает текст и печатает его в обратном порядке. В основной программе запрещено описывать какие-либо переменные.
12.17 - в разделе операторов программы (помимо выдачи информации об авторе и номере задачи, приглашения к вводу и удержания экрана с результатами) должен быть только один оператор PRINT, где PRINT – вызов рекурсивной процедуры без параметров; процедура PRINT считывает числа и печатает их по указанному правилу. В основной программе запрещено описывать какие-либо переменные.
“Без четвёрок”. Написать программу, которая вводит (числовой ввод) неотрицательное целое число и печатает новое число, которое получается из исходного путем вычеркивания всех цифр 4.
В программе описать рекурсивную функцию Delete4(N), значением которой является число, полученное из целого неотрицательного N удалением из его десятичной записи всех цифр 4 (например, 14354 135) , или число 0, если в N только цифры 4 (например, 444 0).
“Степень трёх”. Написать программу, которая вводит (с помощью числового ввода) натуральное число и по нему печатает: -1, если это число не является степенью тройки; соответствующий показатель, если число является степенью тройки. В программе описать рекурсивную целочисленную функцию Deg3(N), значением которой является либо число -1 (если N – не степень тройки), либо соответствующий показатель (если N – это степень тройки).
(например, 24 -1, 1 0, 3 1, 9 2, 27 3, 81 4 и т.д.)
Часть 2 (обязательная) (срок сдачи: 13 декабря включительно)
12.26 – решать по аналогии с разобранной на семинаре задачей 12.25. В программе описать рекурсивную целочисленную функцию без параметров для считывания (с клавиатуры) формулы и вычисления её значения.
12.27 – решать согласно образцу, данному на семинаре.
12.28 - в разделе операторов программы должен быть только один оператор PRINT, где PRINT – вызов рекурсивной процедуры без параметров, которая считывает выражение в инфиксной записи и печатает его в постфиксной форме. В основной программе не должно быть описано каких-либо переменных.
Примеры работы программы (все эти тесты должны пройти!):
((a+(b-c))*d) abc-+d*
a a
(a+b) ab+
((a+b)-(c*(d+e))) ab+cde+*-
((((a+b)+b)+c)+d) > ab+b+c+d+
12.33 - реализовать рекурсивную процедуру Move(n:integer;A,B,C:char), где А – исходный стержень, В – промежуточный (вспомогательный) стержень, С – целевой (конечный) стержень. Идея работы процедуры. 1 ЭТАП: пусть мы сумели переложить (n-1) колец с А на B, используя С как промежуточный (это возможно с учетом подсказки к задаче). 2 ЭТАП: после этого перекладываем самое большое кольцо с А на С. 3 ЭТАП: остается переложить (n-1) колец с В на С, используя А как промежуточный стержень. ВНИМАНИЕ: на 1 и 3 ЭТАПАХ (им соответствуют рекурсивные вызовы) по-разному задаются фактические параметры к процедуре Move (т.к. меняется назначение (смысл) стержней). Печать сообщения о переносе дисков производится на 2 ЭТАПЕ.
12.35 (решать без goto !) – по аналогии с разобранным на семинаре решением задачи 12.34. В основной программе в первую очередь необходимо сформировать булевскую матрицу смежности: сначала инициализировать все её элементы значением false, а затем, в цикле запрашивать пары пунктов, соединённых дорогой, и корректировать соответствующие элементы матрицы. Далее программа запрашивает у пользователя начальный и конечный пункты, после чего выдает ответ о наличии пути. Не забудьте сформировать и распечатать найденный путь. Программа должна быть оттранслирована для значения n=10.
Перед отправкой тщательно проверить работу программы на следующих двух тестах:
Подробности решения (для нуждающихся): сформировать так называемую матрицу “смежности”: var P: array[1..n,1..n] of boolean; {где n – число городов}
Матрица должна отражать информацию о наличии прямых дорог из города i в город j; если город i соединен дорогой с городом j, то P[i,j]= P[j,i]= true (т.к. движение двухстороннее); считать также, что все P[i,i]=false (в основной программе изначально заполнить все элементы этой матрицы значениями false, а далее, по мере ввода данных пользователем заполнять нужные элементы значениями true). Итак, матрица симметрична, значения на главной диагонали = false.
Сформировать также массив Visit, отражающий, в каких городах уже побывали в процессе поиска пути: Visit: array[1..n] of Boolean; {до начала поиска заполнить все его элементы значениями false, кроме одного: Visit[first]:=true, так как сейчас уже находимся в городе с номером first}
Завести массив Way: array [1..n] of 1..n {фиксирует найденный путь; выполнить до начала поиска Way[1]:=first, так как начальный пункт маршрута – это город с номером first}.
Завести также глобальную целочисленную переменную Length для вычисления длины искомого пути (т.е. общего количества пройденных городов, включая начальный и конечный пункты; до начала поиска Length:=1, так как в одном городе находимся в начальный момент; очевидно, что длина искомого пути не будет превышать общего количества городов).
Описать рекурсивную логическую функцию: Path(i,j), которая проверяет (на основе анализа элементов матрицы Р), есть ли путь из города i в город j . Нерекурсивная ветвь: обращение к ф-ции при i=j (значение функции вычислено и равно true). Рекурсивная ветвь: перебор в цикле while или repeat всех пар i и k (где k=1..n). Если какая-то пара городов соединена прямой дорогой (т.е. P[i,k]=true) и при этом в городе k еще не побывали в процессе поиска, то выполняется переход на следующий уровень рекурсии путем обращения Path(k,j) (важно только перед выполнением этого обращения скорректировать текущие данные: Visit[k]:=true {чтобы повторно не попасть в город к при дальнейшем поиске}; Length:= Length+1 {появился новый город в маршруте}; Way[Length]:=k {заносим номер нового города в состав маршрута}). Если обращение Path(k,j) увенчалось успехом, то завершаем работу ф-ции Path(i,j) с положительным ответом (в массиве Way – найденный путь), иначе - переходим к следующему шагу цикла для очередного k (предварительно исключив только что проверенный пункт k из формируемого маршрута: Length := Length -1). Если ни для одной пары i и k путь не найден, то дальнейший поиск не имеет смысла (завершаем работу ф-ции Path(i,j) с отрицательным ответом).
Часть 3 (необязательная) (т.е. это дополнительные задачи).
”Формула?” (5 очков) (это вариация на тему решённой задачи 12.25), формулировка этой задачи:
Во входном файле задан непустой текст, за которым следует точка. Проверить, является ли этот текcт правильной записью “формулы” (см. определение формулы к задаче 12.25).
Рекомендуется описать булевскую функцию F без параметров, которая считывает из начала буфера ввода символы и пытается распознать в них правильную формулу. При первом синтаксически неверном символе – функция прекращает дальнейший ввод из буфера и возвращает ответ false. Если функции удается выделить из начала буфера верную формулу – возвращает ответ true. Эта функция запускается из основной программы, после чего анализируется её результат. Если false – все понятно, программа печатает слово “false”. Если true – то надо проверить (прочитать) символ вслед за найденной формулой; если это точка, то программа печатает слово “true”, иначе - “false” (например, для случаев: 23. или 2+3. или (2+3)-1. )
12.32 (10 очков) - требование: решение дать обязательно с использованием косвенной рекурсии; до начала решения полезно разобрать задачу 12.31 и выданный ранее на листочке пример на “опережающее описание” . Предусмотреть взаимно-рекурсивные булевские функции text и elem (они могут быть с параметрами, а могут быть и нет – дело хозяйское – как сумеете), разрешается при необходимости вводить глобальные переменные (которые функции будут менять в процессе работы). Других функций не вводить, не усложнять решение, только эти две функции! Действуйте четко в соответствии с определениями понятий тект и элемент.
12.38 (5 очков) - для представления n заданных чисел используется массив А. Для генерации нужных перестановок из основной программы вызывается процедура generate(n). Процедура generate(k) генерирует все перестановки элементов А[1], A[2], …, A[k] (первый раз вызывается из программы с параметром n). Идея: оставим к-ый элемент A[k] на своём месте и сгенерируем все перестановки элементов A[1], …, A[k-1] (вызвав для этого рекурсивно процедуру generate(k-1)). Далее повторяем процесс, поменяв A[k] местами с A[i] (последовательно для всех значений i=k-1,…,1) и сгенерировав соответствующие этому перестановки с помощью generate(k-1). Цепочка рекурсивных вызовов завершается, когда число элементов, которые должны быть переставлены, станет равным единице (это значит, что полностью сгенерирована очередная перестановка и пора распечатать текущий вид массива А).
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
