Рассмотрим задачу вычисления числа сочетаний из n элементов по k, для чего необходимо вычисление факториалов трех величин: n, k и n-k. Для этого можно сделать три цикла, что приводит к увеличению размера программы за счет трехкратного повторения похожего кода. Вместо этого лучше сделать одну функцию, вычисляющую факториал любого данного числа n и трижды использовать эту функцию в своей программе. Соответствующая функция может выглядеть так:
int factorial(int n) { int f = 1, i; for (i = 2; i <= n; ++i) { f = f * i; } return f; }
Этот текст должен идти до основной программы, то есть до функции main()
.
Первая строчка этого примера является описанием нашей функции. factorial
– идентификатор,
то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров,
которые получает наша функция. Список состоит из перечисленных через запятую типов параметров и их
идентификаторов. В нашем случае список состоит из одной величины n
, имеющей тип int
:
наша функция вычисляет факториал целого числа. Функция вычисляет целочисленную величину,
поэтому функция будет возвращать значение типа int
, что указывается до идентификатора функции.
Функция может не возвращать никакого значения, тогда в качестве типа возвращаемого значения должно быть
указано слово void
.
Далее идет тело функции в фигурных скобках. Внутри функции вычисляется значение факториала числа n
и оно сохраняется в переменной f
. Функция завершается инструкцией return f
, которая
завершает работу функции и возвращает значение переменной f
. Инструкция return
может встречаться
в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова.
Если функция не возвращает значения, то инструкция return
используется без возвращаемого значения, также
в функциях, не возвращающих значения, инструкция return
может отсутствовать.
Функция должна быть описана до начала основной программы. Сама же основная программа, как можно догадаться,
также является функцией с именем main
, не получающая никаких параметров и возвращающее значение типа int
.
Теперь мы можем использовать нашу функцию factorial
в основной программе нахождения числа сочетаний:
int main() { int n, k; cin >> n >> k; cout << factorial(n) / (factorial(k) * factorial(n-k)) << endl; return 0; }
В этом примере мы трижды вызываем функцию factorial
для вычисления трех факториалов:
factorial(n)
, factorial(k)
, factorial(n-k)
.
Мы также можем объявить функцию binomial
, которая принимает два целочисленных параметра
n
и k
и вычисляет число сочетаний из n
по k
:
int binomial(int n, int k) { return factorial(n) / (factorial(k) * factorial(n-k)); }
Тогда в нашей основной программе мы можем вызвать функцию binomial
для нахождения числа сочетаний:
cout << binomial(n,k) << endl;
Поскольку в этом случае функция main
вызывает функцию binomial
, а функция binomial
вызывает функцию factorial
, а каждая функция должна быть описана до ее вызова из другой функции,
то порядок описания функций в программе должен быть такой:
int factorial(int n)
int binomial(int n, int k)
int main()
Вернемся к задаче нахождения наибольшего из двух или трех чисел. Напишем функцию, находящую максимум из двух данных чисел:
int max(int a, int b) { if (a > b) { return a; } else { return b; } }
Теперь мы можем реализовать функцию max
, находящую максимум трех чисел:
int max(int a, int b, int c) { return max(max(a, b), c); }
В данном примере написаны две различные функции max
: первая с двумя параметрами,
вторая с тремя параметрами. Несмотря на то, что функции имеют одинаковые имена, по количеству
передаваемых параметров ясно, какая из них имеется в виду. В нашем случае функция
max (int a, int b, int c)
дважды вызывает функцию max
для двух чисел:
сначала, чтобы найти максимум из a
и b
, потом чтобы найти максимум из этой
величины и c
.
В каждой функции объявляется свой набор переменных. Переменные, определенные внутри каждой из функций, называются локальными переменными данной функции. Если в двух разных функциях есть локальные переменные с одинаковыми именами, то это — различные переменные. Если в одной из функций поменять значение этой переменной, то в другой функции оно останется неизменным. Пример:
void f1() { int a; a = 1; return; } int main() { int a; a = 2; f1(); cout << a << endl; return 0; }
На экран будет выведено значение 2, т.к. изменение локальной переменной a
внутри функции f1
не приводит
к изменению значения локальной переменной a
для функции main
.
Переменная может быть объявлена и вне всякой функции, тогда она будет доступной из всех функций и в каждой функции это будет одна и та же переменная. Такие переменные называются глобальными.
int a; void f1() { a = 1; return; } int main() { a = 2; f1(); cout << a << endl return 0; }
В этом примере на экран будет выведено значение 1, поскольку вызов функции f1
изменил значение глобальной переменной a
.
Одно из свойств глобальных переменных — их значения по умолчанию проинициализированы нулем, в отличии от локальных переменных, чьи значения по умолчанию инициализируются мусором.
Широкое использование глобальных переменных не принято в современном программировании, вместо глобальных переменных лучше использовать локальные переменные, а для обмена информацией между функциями нужно использовать передаваемые по ссылке параметры.
Раньше у нас была задача, в которой требовалось поменять значения двух переменных. Поскольку такое нужно будет довольно часто, попробуем написать для этого функцию.
void Swap(int a, int b) { int t = a; a = b; b = t; return; } int main() { int a = 1, b = 2; Swap(a, b); cout << a << " " << b << endl; return 0; }
Эта программа выведет 1 2
, то есть значения переменных a
и b
не поменяются. Причина в том, что передаваемые
в функцию параметры являются локальными переменными, когда вызывается функция, то создаются две локальные переменные
a
и b
для этой функции, в них записываются значения локальных переменных
a
и b
функции main
, затем запускается функция Swap
,
которая меняет значения своих локальных переменных, при этом значения локальных переменных функции main
не меняются. Такая передача параметров функции называется передачей параметров по значению.
Можно было бы объявить a
и b
глобальными переменными, но тогда мы не смогли бы использовать
функцию для обмена значений двух переменных, отличных от a
и b
.
Для того, чтобы функция могла изменять значение переменной, переданной в качестве параметра при вызове, используется механизм передачи параметров по ссылке. Если переменная передается в функцию по ссылке, то функция работает с самой переменной, а не с ее локальной копией и может изменять ее значения. Для обозначения того, что параметр передается по ссылке, перед идентификатором переменной-параметра, в описании функции, необходимо поставить знак амперсанда &:
void Swap(int & a, int & b) { int t = a; a = b; b = t; return; }Теперь функцию
Swap
можно использовать для обмена значений любых двух переменных типа int
,
при этом называться они могут как угодно, например, можно вызывать функцию так: Swap(x, y)
.
Но нельзя вызывать функцию так: Swap(1, 2)
—передаваемые по ссылке параметры должны
быть переменными, а не числами или какими-то более сложными выражениями.
Механизм передачи параметров по ссылке используется также в случае, когда функция должна вернуть не одно значение, а несколько. Тогда в функцию необходимо по ссылке передать несколько переменных, в которые функция запишет результат своей работы.
Даны два действительных числа \(x\) и \(y\). Проверьте, принадлежит ли точка с координатами
\((x,y)\) заштрихованному квадрату (включая его границу). Если точка принадлежит квадрату, выведите слово YES
,
иначе выведите слово NO
. На рисунке сетка проведена с шагом 1.
Решение должно содержать функцию bool IsPointInSquare(double x, double y)
,
возвращающую true
, если точка принадлежит квадрату и false
, если не принадлежит.
Функция main
должна считать координаты точки, вызвать функцию IsPointInSquare
и в зависимости от возвращенного значения вывести на экран необходимое сообщение.
Функция IsPointInSquare
не должна содержать инструкцию if
и должна иметь
следующий вид:
bool IsPointInSquare(double x, double y) { return ...; }
Ввод | Вывод |
---|---|
0 0 |
YES |
3 -7 |
NO |
Решите аналогичную задачу для такого квадрата:
Решение должно соответствовать требованиям для решения предыдущей задачи.
Ввод | Вывод |
---|---|
0 0 |
YES |
1 1 |
NO |
Проверьте, принадлежит ли точка данной закрашенной области:
Решение оформите в виде функции bool IsPointInArea(double x, double y)
.
Решение должно соответствовать требованиям для решения задачи D.
Ввод | Вывод |
---|---|
-1 2 |
YES |
0 0 |
NO |
Дано действительное положительное число \(a\) и целоe число \(n\).
Вычислите \(a^n\). Решение оформите в виде функции double power(double a, int n)
.
Стандартной функцией возведения в степень пользоваться нельзя.
Ввод | Вывод |
---|---|
2 3 |
8 |
2 -3 |
0.125 |
Даны два натуральных числа \(n\) и \(m\). Сократите дробь \(\frac{n}{m}\), то есть выведите два других числа \(p\) и \(q\) таких, что \(\frac{n}{m}=\frac{p}{q}\) и дробь \(\frac{p}{q}\) — несократимая.
Решение оформите в виде функции
void ReduceFraction(int & n, int & m)
,
получающая значения n
и m
по ссылке и изменяющая их.
Ввод | Вывод |
---|---|
12 16 |
3 4 |
Мнение конструкторов ЭВМ и математиков о том, что такое деление с остатком для отрицательных чисел расходится. Напомним, что при делении числа \(a\) на число \(b\) с остатком находятся такие числа \(q\) (частное) и \(r\) (остаток), что \(a=qb+r\). При этом \(|r|<|b|\). Если числа \(a\) и \(b\) — положительные, то выполняется более сильное неравенство: \(0 \le r < b\) и тогда деление с остатком определяется однозначно. Но если числа — отрицательные то деление с остатком на компьютере выполняется не так, как это кажется правильным математикам.
Вот как выполняется деление с остатком на компьютере для отрицательных чисел:
a |
b |
a / b |
a % b |
---|---|---|---|
26 |
10 |
2 |
6 |
-26 |
10 |
-2 |
-6 |
26 |
-10 |
-2 |
6 |
-26 |
-10 |
2 |
-6 |
Таким образом, в компьютере целочисленное частное является результатом округления действительного частного
в сторону нуля, как это делает функция trunc
. Между тем, математик считает, что целочисленное
частное — это целая часть от частного \((q=\lfloor a/b\rfloor)\), то есть результат использования функции floor
.
Это даст такие результаты с точки зрения математики:
\(a\) | \(b\) | \(\lfloor a / b\rfloor\) | \(a \bmod b\) |
---|---|---|---|
26 |
10 |
2 |
6 |
-26 |
10 |
-3 |
4 |
26 |
-10 |
-3 |
-4 |
-26 |
-10 |
2 |
-6 |
Напишите программу, которая по данным числам \(a\) и \(b\) вычисляет их целочисленное частное и остаток от деления так, как это принято в математике. Программа не должна использовать действительные числа и циклы.
Решение оформите в виде функции void DivMod(int a, int b, int & q, int & r)
, где
a
— делимое, b
— делитель,
q
— переменная для записи частного, r
— переменная
для записи остатка.
Ввод | Вывод |
---|---|
-26 10 |
-3 4 |
26 -10 |
-3 -4 |
Эпиграф: void ShortStory() { cout << "У попа была собака, он ее любил." << endl; cout << "Она съела кусок мяса, он ее убил," << endl; cout << "В землю закопал и надпись написал:" << endl; ShortStory(); }
Как мы видели выше, функция может вызывать другую функцию. Но функция также может вызывать и саму себя! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что \(0!=1\), \(1!=1\). А как вычислить величину \(n!\) для большого \(n\)? Если бы мы могли вычислить величину \((n-1)!\), то тогда мы легко вычислим \(n!\), поскольку \(n!=n(n-1)\)!. Но как вычислить \((n-1)!\)? Если бы мы вычислили \((n-2)!\), то мы сможем вычисли и \((n-1)!=(n-1)(n-2)!\). А как вычислить \((n-2)!\)? Если бы... В конце концов, мы дойдем до величины \(0!\), которая равна \(1\). Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на C++:
int factorial(int n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); } }
Подобный прием (вызов функцией самой себя) называется рекурсией, а сама функция называется рекурсивной.
Рекурсивные функции являются мощным механизмом в программировании. К сожалению, они не всегда эффективны (об этом речь пойдет позже). Также часто использование рекурсии приводит к ошибкам, наиболее распространенная из таких ошибок – бесконечная рекурсия, когда цепочка вызовов функций никогда не завершается и продолжается, пока не кончится свободная память в компьютере. Пример бесконечной рекурсии приведен в эпиграфе к этому разделу. Две наиболее распространенные причины для бесконечной рекурсии:
if (n == 0)
, то factorial(0)
вызовет factorial(-1)
,
тот вызовет factorial(-2)
и т.д.
factorial(n)
будет
вызывать factorial(n)
, то также получиться бесконечная цепочка.
Поэтому при разработке рекурсивной функции необходимо прежде всего оформлять условия завершения рекурсии и думать, почему рекурсия когда-либо завершит работу.
Дано действительное положительное число \(a\) и целое неотрицательное число \(n\).
Вычислите \(a^n\) не используя циклы и стандартную функцию pow
, а используя
рекуррентное соотношение \(a^n=a\cdot a^{n-1}\).
Решение оформите в виде функции double power(double a, int n)
.
Ввод | Вывод |
---|---|
2 3 |
8 |
Напишите рекурсивную функцию int sum(int a, int b)
, возвращающую
сумму двух целых неотрицательных чисел. Из всех арифметических операций допускаются
только +1
и -1
. Также нельзя использовать циклы.
Ввод | Вывод |
---|---|
2 2 |
4 |
Последовательность Фибоначчи определена следующим образом: \(\varphi_0=1\), \(\varphi_1=1\), \(\varphi_n=\varphi_{n-1}+\varphi_{n-2}\), при \(n>1\).
Начало ряда Фибоначчи выглядит следующим образом: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Напишите функцию int phi(int n)
, которая по данному целому неотрицательному n
возвращает \(\varphi_n\).
Ввод | Вывод |
---|---|
6 |
13 |
Дана последовательность чисел, завершающаяся числом 0. Найдите сумму всех этих чисел, не используя цикл.
Ввод | Вывод |
---|---|
1 |
17 |
Дана последовательность целых чисел, заканчивающаяся числом 0. Выведите эту последовательность в обратном порядке.
При решении этой задачи нельзя пользоваться массивами и прочими динамическими структурами данных. Рекурсия вам поможет.
Ввод | Вывод |
---|---|
1 |
0 3 2 1 |
Возводить в степень можно гораздо быстрее, чем за \(n\) умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:
\(a^n=(a^2)^{n/2}\) при четном \(n\),
\(a^n=a\cdot a^{n-1}\) при нечетном \(n\).
Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет \(O(\log n)\).
Ввод | Вывод |
---|---|
1.000000001 1000000000 |
2.71828 |
Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: \(НОД(a,b)=НОД(a\bmod b,b)\).
Реализуйте рекурсивный алгоритм Евклида в виде функции int gcd(int a, int b)
.
Ввод | Вывод |
---|---|
12 16 |
4 |
Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из \(n\) дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.
Напишите программу, которая решает головоломку; для данного числа дисков n
печатает последовательность перекладываний в формате
a b c
, где a
— номер перекладываемого диска,
b
— номер стержня с которого снимается данный диск,
c
— номер стержня на который надевается данный диск.
Например, строка 1 2 3
означает перемещение диска номер 1 со стержня
2 на стержень 3. В одной строке печатается одна команда.
Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.
Программа должна вывести минимальный (по количеству произведенных операций) способ перекладывания пирамидки из данного числа дисков.
Указание: подумайте, как переложить пирамидку из одного диска? Из двух дисков? Из трех дисков? Из четырех дисков? Пусть мы научились перекладывать пирамидку из \(n\) дисков с произвольного стержня на любой другой, как переложить пирамидку из \(n+1\) диска, если можно пользоваться решением для \(n\) дисков.
Напишите функцию move (n, x, y)
,
которая печатает последовательнось перекладываний дисков для перемещения
пирамидки высоты n
со стержня номер x
на стержень номер y
.
Ввод | Вывод |
---|---|
2 |
1 1 2 |
Постановлением ЮНЕСКО оригинал Ханойской башни был подвергнут реставрации. В связи с этим во время пользования головоломкой нельзя было перекладывать кольца с первого стержня сразу на третий и наоборот.
Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.
Тесты к этой задаче закрытые.
Ввод | Вывод |
---|---|
1 |
1 1 2 |
2 |
1 1 2 |
На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1.
Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.
Ввод | Вывод |
---|---|
1 |
1 1 2 |
2 |
1 1 2 |
В Ханое несправедливо запретили класть самый маленький диск (номер 1) на средний колышек (номер 2).
Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.
Ввод | Вывод |
---|---|
2 |
1 1 3 |
Первоначально все диски лежат на стержне номер 1. Переместите диски с нечетными номерами на стержень номер 2, а с четными номерами - на стержень номер 3.
Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.
Ввод | Вывод |
---|---|
2 |
1 1 2 |
3 |
1 1 2 |
Дана полоска из клеток, пронумерованных от 1 до N слева направо. Разрешено снимать или ставить фишку на клетку с номером 1 или на клетку, следующую за самой левой из установленных фишек. Изначально полоска пуста. Нужно разместить фишки во всех клетках.
Программа получает на вход количество клеток в полоске \(N\) \((1\le N\le 10)\).
Программа должна вывести последовательность номеров клеток, с которыми совершается действие. Если фишка снимается, то номер клетки должен выводиться со знаком минус. Количество действий не должно превышать \(10^4\). Если существует несколько возможных решений задачи, то разрешается вывести любое.
Тесты к этой задаче закрытые.
Ввод | Вывод |
---|---|
3 |
1 2 -1 3 1 |