Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Машинные задачи на рекурсию.

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

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...