 |
Машинные задачи на рекурсию.
|
|
|
|
Часть 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), формулировка этой задачи:
|
|
|
