Методические указания к выполнению практических работ

Практические занятия проводятся с целью приобретения практических навыков алгоритмизации, программирования.

Выполнение каждой практической работы включает разработку алгоритма и написание программы, демонстрацию результатов преподавателю, составление отчета о практической работе. Содержание отчета должно полностью соответствовать заданию на эту практическую работу. Форма титульного листа отчета приведена в приложении.

Практическое занятие №1. Рекурсия.

Варианты индивидуальных заданий

Написать рекурсивную подпрограмму вычисления целой степени вещественного ненулевого числа (степень может быть и отрицательной).

Написать рекурсивную подпрограмму для определения разбиения целых чисел. Разбиениями целого числа называют способы его представления в виде суммы целых чисел. Например, разбиениями числа 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] методом деления отрезка пополам.

Задан массив из вещественных чисел. Описать функцию min(x) для определения минимального элемента массива x, введя вспомогательную рекурсивную функцию min1(k), находящую минимум среди последних элементов массива х, начиная с k.

Задана строка в виде массива символов. Описать рекурсивную логическую функцию, проверяющую, является ли симметричной часть строки s, начинающаяся i -м и кончающаяся j -м ее элементом.

Дана последовательность ненулевых целых чисел, за которой следует 0. Напечатать сначала все отрицательные числа этой последовательности, а затем все положительные (в любом порядке).

Заданный вещественный массив из n различных элементов упорядочить по возрастанию следующим методом быстрой сортировки: выбрать какой-нибудь элемент массива (например, средний) и переставить элементы массива так, чтобы слева от выбранного элемента оказались только меньшие элементы, а справа – только большие (тем самым выбранный элемент окажется на своем окончательном месте), после чего рекурсивно применить этот же метод к левой и правой частям массива.

“Ханойские башни”. Имеются три колышка А,В,С и n дисков разного размера, пронумерованных от 1 до n в порядке возрастания их размеров. Сначала все диски надеты на колышек А меньший на больший. Требуется перенести все диски с колышка А на колышек С, соблюдая при этом следующие условия: диски можно переносить только по одному, больший диск нельзя ставить на меньший. Написать рекурсивную подпрограмму, которая печатает последовательность действий, решающую данную задачу для n дисков, где n – заданное натуральное число.

Имеется n населенных пунктов, пронумерованных от 1 до n. Некоторые пары пунктов соединены дорогами. Определить, можно ли попасть по этим дорогам из 1 -го пункта в n -й. Информация о дорогах задается в виде последовательности пар чисел i и j (i < j), указывающих, что i -й и j -й пункты соединены дорогой.

Дано n различных натуральных чисел. Напечатать все перестановки этих чисел.

Задача о восьми ферзях: на шахматной доске расставить 8 ферзей так, чтобы они не “били” друг друга. Напечатать все 92 такие расстановки.

Даны натуральные числа n и m, найти НОД(n,m). Использовать программу, включающую рекурсивную подпрограмму вычисления НОД, основанную на соотношении НОД(n,m)=НОД(m,r), где r – остаток от деления n на m.

u₀=0, u₁=1,u_n=u_n-1+ u_n-2 (n=2,3, …). Написать программу вычисления u_n для заданного неотрицательного целого 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).

A(n,m) = í A(n-1,1), если n<>0, m=0;

î A(n-1,A(n,m-1)), если n>0, m>0.

Использовать программу, включающую рекурсивную подпрограмму.

17 1

Треугольником Паскаля называется числовой треугольник 1 1

в котором по краям стоят 1, а каждое число внутри равно 1 2 1

сумме двух стоящих над ним в ближайшей строке сверху. 1 3 3 1

Дано натуральное n. Получить первые n строк треугольника 1 4 6 4 1

Паскаля. Использовать рекурсивную подпрограмму.

Даны натуральные числа m,n₁,…,n_m (m>=2). Вычислить НОД(n₁,…,n_m), воспользовавшись для этого соотношением

НОД(n₁,…,n_к)=НОД(НОД(n₁,…,n_к-1),n_k)

(к=3,…,n) и алгоритмом Евклида.

Пусть t₀=1, t_k=t₀t_k-1+ t₁t_k-2+…+ t_k-2t₁+ t_k-1t₀, k=1,2,…. Получить t_n.

Вдоль доски расположено 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 так, чтобы суммы чисел, стоящих в каждом вертикальном ряду, в каждом горизонтальном ряду, а также на любой диагонали были равны.

На квадратном поле размером 4 на 4 случайным образом расставлены 15 фишек с номерами от 1 до 15. Имеется одна свободная позиция. Расставить фишки по возрастанию их номеров. Передвигать фишки можно только на соседнюю свободную позицию. Написать рекурсивную подпрограмму, которая печатает последовательность действий, решающую данную задачу.

Не нашли, что искали? Воспользуйтесь поиском: