Функции и рекурсия в C++
Михаил Попов 10.01.2016 13:13 C++ , Алгоритмы 2 комментариев
Ну вот и подошли к концу новогодние каникулы, а с ними и мое обучение по C++. Как говорил, закончил его с отличием. Сегодня рассмотрим задачи с использованием функций. Часть задач будет решаться с использованием рекурсивных функций. Напомню, что эти задачи рассматривались в курсе Введение в программирование (С++) на сайте steptic.org. Сейчас немного поделюсь новостями, а потом приступим к задачам.
Немного доработал сайт
- Сделал рубрикатор, за одно переделал состав рубрик. Добавил ссылку на рубрики на главную страницу.
- Немного доработал лайки. Теперь зарегистрированные пользователи не смогут их накрутить. Пока оставил возможность ставить лайки незарегистрированным пользователям, но теперь без возможности накрутки. Пришлось обнулить все лайки к статьям для функционирования новой механики.
- Сделал еще несколько небольших улучшений и поправил несколько ошибок.
- Регистрацию так и не удалось побороть, так что лучше регистрироваться через социальные сети.
Задача №1
Напишите функцию min(a, b), вычисляющую минимум двух чисел. Затем напишите функцию min4(a, b, c, d), вычисляющую минимум 4 чисел с помощью функции min. Считайте четыре целых числа и выведите их минимум.
Формат входных данных
Вводятся четыре целых числа.
Формат выходных данных
Выведите ответ на задачу.
Sample Input: 4 5 6 7 Sample Output: 4
Решение
Задача №2
Даны четыре действительных числа: x1x1, y1y1, x2x2, y2y2. Напишите функцию distance(x1, y1, x2, y2), вычисляющую расстояние между точкой (x1,y1)(x1,y1) и (x2,y2)(x2,y2). Считайте четыре действительных числа и выведите результат работы этой функции.
Формат входных данных
Вводятся четыре действительных числа.
Формат выходных данных
Выведите ответ на задачу.
Sample Input: 0 0 1 1 Sample Output: 1.41421
Решение
Задача №3
Даны два действительных числа xx и yy. Проверьте, принадлежит ли точка с координатами (x,y)(x,y) заштрихованному квадрату (включая его границу). Если точка принадлежит квадрату, выведите слово YES, иначе выведите слово NO.
На рисунке сетка проведена с шагом 1.
Решение должно содержать функцию IsPointInSquare(x, y), возвращающую true, если точка принадлежит квадрату и false, если не принадлежит. Основная программа должна считать координаты точки, вызвать функцию IsPointInSquare и в зависимости от возвращенного значения вывести на экран необходимое сообщение.
Функция IsPointInSquare не должна содержать инструкцию if.
Формат входных данных
Вводятся два действительных числа.
Формат выходных данных
Выведите ответ на задачу.
Sample Input 1: 0 0 Sample Output 1: YES Sample Input 2: 3 -7 Sample Output 2: NO
Решение
Задача №4
Даны пять действительных чисел: xx, yy, xcxc, ycyc, rr. Проверьте, принадлежит ли точка (x,y)(x,y) кругу с центром (xc,yc)(xc,yc) и радиусом rr. Если точка принадлежит кругу, выведите слово YES, иначе выведите слово NO.
Решение должно содержать функцию IsPointInCircle(x, y, xc, yc, r), возвращающую True, если точка принадлежит кругу и False, если не принадлежит.
Основная программа должна считать координаты точки, вызвать функцию IsPointInCircle и в зависимости от возвращенного значения вывести на экран необходимое сообщение.
Функция IsPointInCircle не должна содержать инструкцию if.
Формат входных данных
Вводятся пять действительных чисел.
Формат выходных данных
Выведите ответ на задачу.
Sample Input 1: 0.5 0.5 0 0 1 Sample Output 1: YES Sample Input 2: 0.5 0.5 1 1 0.1 Sample Output 2: NO
Решение
Задача №5
Проверьте, принадлежит ли точка данной закрашенной области:
Если точка принадлежит области (область включает границы), выведите слово YES, иначе выведите слово NO.
Решение должно содержать функцию IsPointInArea(x, y), возвращающую True, если точка принадлежит области и False, если не принадлежит. Основная программа должна считать координаты точки, вызвать функцию IsPointInArea и в зависимости от возвращенного значения вывести на экран необходимое сообщение.
Функция IsPointInArea не должна содержать инструкцию if.
Формат входных данных
Вводятся два действительных числа.
Формат выходных данных
Выведите ответ на задачу.
Sample Input 1: -4 -4 Sample Output 1: NO Sample Input 2: -4 -3 Sample Output 2: NO
Решение
Задача №6
Дано действительное положительное число aa и целоe число nn. Вычислите anan. Решение оформите в виде функции power(a, n).
Формат входных данных
Вводится действительное положительное число aa и целоe число nn.
Формат выходных данных
Выведите ответ на задачу.
Sample Input 1: 2 1 Sample Output 1: 2 Sample Input 2: 2 2 Sample Output 2: 4
Решение
Задача №7
Дано натуральное число n>1n>1. Выведите его наименьший делитель, отличный от 1.
Решение оформите в виде функции MinDivisor(n). Количество операций в программе должно быть пропорционально sqrtnsqrtn.
Указание
Если у числа nn нет делителя, меньшего nn , то число nn — простое и ответом будет само число nn.
Формат входных данных
Вводится натуральное число.
Формат выходных данных
Выведите ответ на задачу.
Sample Input 1: 4 Sample Output 1: 2 Sample Input 2: 5 Sample Output 2: 5
Решение
Задача №8
Дано натуральное число n>1n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное.
Решение оформите в виде функции IsPrime(n), которая возвращает True для простых чисел и False для составных чисел. Количество операций в программе должно быть пропорционально /sqrtn/sqrtn.
Формат входных данных
Вводится натуральное число.
Формат выходных данных
Выведите ответ на задачу.
Sample Input 1: 2 Sample Output 1: YES Sample Input 2: 4 Sample Output 2: NO
Решение
Задача №9
Возводить в степень можно гораздо быстрее, чем за nn умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:
an=(a2)n/2an=(a2)n/2, при четном nn,
an=a×an−1an=a×an−1, при нечетном nn
Реализуйте алгоритм быстрого возведения в степень с помощью рекурсивной функции.
Формат входных данных
Вводятся действительное число a и целое неотрицательное число nn.
Формат выходных данных
Выведите ответ на задачу.
Sample Input 1: 2.0 1 Sample Output 1: 2 Sample Input 2: 2 2 Sample Output 2: 4
Решение
Задача №10
Дана последовательность чисел, завершающаяся числом 0. Найдите сумму всех этих чисел, не используя цикл.
Формат входных данных
Вводится последовательность целых чисел, оканчивающаяся числом 0 (само число 0 в последовательность не входит, а служит как признак ее окончания).
Формат выходных данных
Выведите ответ на задачу.
Sample Input: 1 7 9 0 Sample Output: 17
Решение
Задача №11
Напишите функцию fib(n), которая по данному целому неотрицательному nn возвращает nn-e число Фибоначчи. В этой задаче нельзя использовать циклы – используйте рекурсию.
Первое и второе числа Фибоначчи равны 1, а каждое следующее равно сумме двух предыдущих.
Формат входных данных
Вводится целое число.
Формат выходных данных
Выведите ответ на задачу.
Sample Input: 1 Sample Output: 1
Решение
Задача №12
Дано число N. Определите, сколькими способами можно расставить на доске N×NN×N NN ферзей, не бьющих друг друга.
Формат входных данных
Задано единственное число NN. (N≤10)(N≤10)
Формат выходных данных
Выведите ответ на задачу.
Sample Input: 8 Sample Output: 92
Решение
#include <iostream>
using namespace std;
int board[10];
bool check(int i, int j, int k) {
if (k == i) return true;
else return board[k] != j && (i - k) != (j - board[k]) && (i - k) != (board[k] - j) && check(i, j, k + 1);
}
int put_queen(int n, int i, int j) {
if (i == n) return 1;
else {
if (j < n) {
int r = 0;
if (check(i, j, 0)) {
board[i] = j;
r = put_queen(n, i + 1, 0);
}
return r + put_queen(n, i, j + 1);
}
else return 0;
}
}
int main() {
int n;
cin >> n;
cout << put_queen(n, 0, 0);
return 0;
}