КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Рекурсия
Цель лабораторной работы: совершенствование навыков процедурного программирования на языке C/С++ при решении рекурсивных задач; освоение передачи имён функций в качестве параметров.
Задание на программирование: используя технологию процедурного программирования разработать программу, содержащую рекурсивную функцию, в соответствии с индивидуальным заданием.
Порядок выполнения работы:
1) Получить у преподавателя индивидуальное задание.
2) Построить схему алгоритма решения задачи.
3) Составить спецификации используемых функций.
4) Составить программу на языке C/С++.
5) Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов.
6) Оформить отчет о лабораторной работе в составе: постановка задачи, математическая модель, схема алгоритма решения, спецификация функций, текст программы, контрольные примеры.
Варианты индивидуальных заданий
Написать программу, содержащую рекурсивную функцию вычисления целой степени вещественного ненулевого числа (степень может быть и отрицательной).
Написать программу, содержащую рекурсивную функцию определения разбиения целых чисел. Разбиениями целого числа называют способы его представления в виде суммы целых чисел. Например, разбиениями числа 4 являются: 4, 3+1, 2+2, 2+1+1, 1+1+1+1.
Написать программу, содержащую рекурсивную функцию вычисления биномиального коэффициента 
по следующей формуле:
ì 1, если m=0, n>0 или m=n>=0;
C(n, m) =í 0, если m>n>=0;
î C(n-1, m-1) + C(n-1, m) в остальных случаях.
Написать программу, содержащую рекурсивную функцию, которая находит с точностью ε корень уравнения f(x)=0 на отрезке [a, b] методом деления отрезка пополам.
Задан одномерный массив вещественных чисел. Написать программу определения минимального элемента массива x, содержащую рекурсивную функцию min(k), находящую минимум среди последних элементов массива х, начиная с k.
Задана строка в виде массива символов. Написать программу, содержащую рекурсивную функцию, проверяющую, является ли симметричной часть строки s, начинающаяся i-м и кончающаяся j-м её элементом.
Дана последовательность ненулевых целых чисел, за которой следует 0. Напечатать сначала все отрицательные числа этой последовательности, а затем все положительные (в любом порядке).
Имеется n населенных пунктов, пронумерованных от 1до n. Некоторые пары пунктов соединены дорогами. Определить, можно ли попасть по этим дорогам из 1-го пункта в n-й. Информация о дорогах задается в виде последовательности пар чисел i и j (i<j), указывающих, что i-й и j-й пункты соединены дорогой.
“Ханойские башни”. Имеются три колышка А, В, С и n дисков разного размера, пронумерованных от 1 до n в порядке возрастания их размеров. Сначала все диски надеты на колышек А меньший на больший. Требуется перенести все диски с колышка А на колышек С, соблюдая при этом следующие условия: диски можно переносить только по одному, больший диск нельзя ставить на меньший. Написать рекурсивную функцию, которая печатает последовательность действий, решающую данную задачу для n дисков, где n – заданное натуральное число.
Пусть t0=1, tk=t0*tk-1+ t1*tk-2+…+ tk-2*t1+ tk-1*t0, k=1, 2,… . Получить tn.
Дано n различных натуральных чисел. Напечатать все перестановки этих чисел.
Задача о восьми ферзях: на шахматной доске расставить 8 ферзей так, чтобы они не “били” друг друга. Напечатать все 92 такие расстановки.
Даны натуральные числа n и m, найти НОД(n, m). Использовать программу, включающую рекурсивную функцию вычисления НОД, основанную на соотношении НОД(n, m)=НОД(m, r), где r – остаток от деления n на m.
Числа Фибоначчи u0, u1, u2,… определяются следующим образом:
u0=0, u1=1, un=un-1+ un-2 (n=2, 3, …). Написать программу вычисления un для заданного неотрицательного целого n, включающую рекурсивную функцию.
Даны натуральные числа a, c, m. Получить f(m), где
ì n, если 0<=n<=9;
f(n)= í
îg(n)f(n-1-g(n))+n в противном случае.
g(n) = остаток от деления a(n+c) на 10.
Использовать программу, включающую рекурсивную функцию вычисления f(n).
Даны неотрицательные целые числа n и m. Вычислить функцию A(n, m) вида:
ìm+1, если n=0;
A(n, m) = íA(n-1, 1), если n<>0, m=0;
îA(n-1, A(n, m-1)), если n>0, m>0.
Использовать программу, включающую рекурсивную функцию.
Треугольником Паскаля называется числовой треугольник 1
в котором по краям стоят 1, а каждое число внутри равно 1 1
сумме двух стоящих над ним в ближайшей строке сверху. 1 2 1
Дано натуральное n. Получить первые nстрок треугольника 1 3 3 1
Паскаля. Использовать рекурсивную функцию. 1 4 6 4 1
Даны натуральные числа m, n1,…, nm (m>=2). Вычислить НОД(n1,…, nm), воспользовавшись для этого соотношением
НОД(n1,…, nк)=НОД(НОД(n1,…, nк-1), nk)
(к=3,…, n) и алгоритмом Евклида.
На квадратном поле размером 4 на 4 случайным образом расставлены 15 фишек с номерами от 1 до 15. Имеется одна свободная позиция. Расставить фишки по возрастанию их номеров. Передвигать фишки можно только на соседнюю свободную позицию. Написать программу, содержащую рекурсивную функцию, которая печатает последовательность действий, решающую данную задачу.
Вдоль доски расположено 2n+1 лунок, в которых лежат n черных и n белых шаров (n черных слева, n белых справа, посередине пустая лунка). Передвинуть черные шары на место белых, а белые на место черных. Шар можно передвинуть либо в соседнюю с ним пустую лунку, либо в пустую лунку, находящуюся непосредственно за ближайшим шаром. Написать программу, содержащую рекурсивную функцию, которая печатает последовательность действий, решающую данную задачу.
Вдоль доски расположено 2n лунок, в которых расставлено n черных и n-1 белых шаров (1,...,n лунки с черными шарами, n+1 лунка пустая, n+2,...,2n лунки с белыми шарами). Поменять местами черные и белые шары. Шар можно передвинуть либо в соседнюю с ним пустую лунку, либо в пустую лунку, находящуюся непосредственно за ближайшим шаром. Черные шары можно передвигать только вправо, а белые только влево. Написать программу, содержащую рекурсивную функцию, которая печатает последовательность действий, решающую данную задачу.
В квадрате размером 4 на 4 клетки расставить 16 букв (четыре а, четыре b, четыре c, четыре d) так, чтобы в каждом горизонтальном и в каждом вертикальном ряду любая буква встречалась только один раз. Напечатать все возможные решения.
В каждой из 9 клеток квадрата размером 3 на 3 клетки поставить одно из чисел 1, 2, 3 так, чтобы сумма чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду, а также по любой диагонали равнялась 6. Решение напечатать.
В квадрате размером 3 на 3 клетки расставить числа 1, 2, 3, 4, 5, 6, 7, 8, 9 так, чтобы суммы чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду, а также на любой диагонали были равны.
Написать программу, содержащую рекурсивную функцию, которая находит с точностью ε корень уравнения f(x)=0 на отрезке [a, b] методом касательных.
Написать программу, содержащую рекурсивную функцию, которая находит с точностью ε корень уравнения f(x)=0 на отрезке [a, b] методом хорд.
Написать программу, содержащую рекурсивную функцию, которая находит с точностью ε корень уравнения f(x)=0 на отрезке [a, b] методом секущих.
Дата добавления: 2015-04-04; просмотров: 203; Мы поможем в написании вашей работы!; Нарушение авторских прав |