Рекурсия (стр. 9 из 12)

Решение. Это задача в каком-то смысле является обобщением предыдущей. Здесь выводятся правильные вписанные n-угольники, количество их не обязательно четно и первая из вершин начального n-угольника может лежать в любой точке единичной окружности. Правда, здесь многоугольники не “описываются” один вокруг другого, а “вписываются” друг в друга. Но существа дела это не меняет.

Прежде всего, составим программу, которая формирует массив вершин правильного n-угольника, вписанного в окружность радиуса r и содержащего вершину (r×cos(a) r×sin(a)). Сделать это можно, например, так:

Тогда массив polyone(n,1,a) может служить базой рекурсии. Более того, эта функция при правильном выборе r и a позволяет получить массив вершин любого из следующих вписанных n-угольников, что помогает организовать и декомпозицию. Если уже построена матрица ma точек для (n-1)-го вписанного правильного n-угольника, то, пополнив её точками матрицы:

получим матрицу точек для 2×n таких многоугольников. Соответствующая рекурсивная функция, реализующая эти идеи, может выглядеть так:

Контрольный пример.

Результат вычислений представлен на рис. 3.6 c неодинаковым масштабом по осям.

Рис. 3.6. k вложенных правильных n-угольников (k=20, n=6)

Несколько слов перед формулировкой новой задачи. В основах анализа [8, с. 17-38] операции сложения и умножения над натуральными числами определяются рекурсивным способом, опираясь на аксиомы Пеано “о существовании последующего числа” и “индукции”. Первая из названных аксиом звучит так: “для каждого натурального x имеется и притом только одно натуральное число, называемое его последующим и обозначаемое число x¢ ”.Постараемся промоделировать указанные выше и некоторые иные операции.

Задача 36. Для целых неотрицательных чисел n, m разрешены операции:

нахождения последующего числа (n+1) и предыдущего числа n-1 (n>0). Промоделировать с помощью рекурсивных функций операции нахождения суммы (n+m), разности (n-m(n³m)), умножения (n×m), возведения в степень n^m (n>0), частного и остатка при делении n на m (n/m).

Решение.

A. Сумма: a+b. Очевидноесоотношение

задает одновременно и базу рекурсии и правило декомпозиции. По нему и построена следующая рекурсивная программа-функция:

Контрольный пример:

B. Разность: a-b (a³b). В данном случае база рекурсии и декомпозиция могут быть извлечены из соотношения:

Соответствующая рекурсивная программа-функция выглядит так.

Контрольный пример:

C. Умножение: a×b. Будем считать, что операция сложения уже определена. Тогда соотношение, из которого легко извлекаются база и декомпозиция для данного случая выглядит следующим образом:

Соответствующая рекурсивная программа-функция может быть записана, например, так:

Контрольный пример:

D. Возведение в степень: a^b (a¹0). Будем считать, что операция умножения уже определена. Тогда:

и рекурсивная программа-функция возведения в степень может быть задана так:

Контрольный пример:

E. Частное и остаток: a/b (b>0). В данной задаче речь идет об отыскании величин q и r из представления: a=q×b+r (0£r<b, q³0). Будем предполагать, что операция вычитания уже определена, а ответ должен быть возвращен в виде вектора с двумя компонентами: (qr)^T. Если a<b, то q=0 и r=a. Этот факт и определяет базу рекурсии. Если же b>a, то a/b=1+(a-b)/b, что позволяет организовать декомпозицию. Все сказанное учтено в рекурсивной функции divi(q,a,b). В ней первый аргумент q является вспомогательным параметром. При обращениях к divi() он должен определять базовое значение частного, то есть быть равен нулю. Однако проще решать задачу с помощью вспомогательной функции div(a,b), возлагая на неё решение вопроса о правильном значении вспомогательного параметра вызовах divi(). Это довольно типичный случай при обобщениях исходной задачи за счет введения дополнительных параметров.

Контрольный пример.

Замечание. Моделирование различных операций возможно не только для целых неотрицательных чисел. Их можно было бы определить и для множества всех целых чисел и даже для множества вещественных чисел. Ограничимся рассмотрением одного примера. Напишем рекурсивную программу-функцию нахождения дробной части вещественного числа, если разрешены лишь операции x+1 и x-1. Вот один из возможных достаточно ясных вариантов её определения:

Контрольный пример.

Синтаксические языковые конструкции

Задача 37. Составить программу-функцию проверяющую, является ли данная последовательность символов идентификатором языка Фортран.

Решение. Будем считать, что речь идет о версиях Фортрана, где идентификатор определялся как последовательность из шести заглавных латинских букв и (или) цифр, начинающаяся с буквы и для символов была принята ASCII кодировка. Превратить последовательность символов в вектор соответствующих им ASCII-кодов можно с помощью встроенной функции str2vec(). Например:

Дополнительное ограничение на первый символ идентификатора (буква, но не цифра) усложняет общую проверку (или буква, или цифра). Чтобы действия были стандартными для всех символов, проверку первого из них будем осуществлять на допустимость отдельно в головной программе. Естественно там же располагать и проверку длины слова, которая должна находиться в пределах от 1 до 6. Тогда в подпрограмме останется решить вполне рекурсивную подзадачу: “если первый символ исходного слова не буква и не цифра, то формируем ответ “не идентификатор”. В противном случае, если длина слова равна единице, то возвращаем ответ “идентификатор”, а иначе укорачиваем слово на первый символ и снова решаем эту же подзадачу. Все сказанное и реализуется головной программой identity(word) и рекурсивной подпрограммой iden(v):

Контрольные примеры.

Замечание. В любом языке программирования все базовые языковые конструкции (идентификаторы, константы, переменные, выражения, метки, типы и т.п.) определяются рекурсивно. Особенно наглядно это видно, когда они представлены с помощью синтаксических диаграмм [7, c. 685-703] или в форме Бэкуса-Наура. Подобные определения в рамках конкретного языка программирования могут служить наборами тренировочных заданий по написанию рекурсивных программ и даже простейших рекурсивных трансляторов.

Приведем пример. Идентификатор в Паскале определяется, как и в Фортране, но без ограничений на длину последовательности символов. С помощью синтаксической диаграммы это выглядит так, как это указано на рис.3.7., а в форме Бэкуса-Наура следующим образом (значок “::=” читается как “есть по определению”):

<идентификатор>::=<буква>

<идентификатор>::=<идентификатор><буква>

<идентификатор>::=<идентификатор><цифра>

Рис. 3.7. Синтаксическая диаграмма идентификатора (Паскаль)

И в том и в другом случаях идентификатор определяется сам через себя.

3.28 Проблемная ситуация

Задача 38. При любом ли натуральном n ли рекурсивная функция