В предыдущем листке была задача вычисления числа сочетаний из 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) —передаваемые по ссылке параметры должны
быть переменными, а не числами или какими-то более сложными выражениями.
Механизм передачи параметров по ссылке используется также в случае, когда функция должна вернуть не одно значение, а несколько. Тогда в функцию необходимо по ссылке передать несколько переменных, в которые функция запишет результат своей работы.
Напишите функцию int min(int a, int b), вычисляющую минимум двух чисел. Напишите функцию
int min(int a, int b, int c, int d), вычисляющую минимум четырех чисел, которая
не содержит инструкции if. Считайте четыре целых числа и выведите их минимум.
| Ввод | Вывод |
|---|---|
5 1 7 3 |
1 |
Даны четыре действительных числа: \(x_1\), \(y_1\), \(x_2\), \(y_2\). Напишите функцию
double distance(double x1, double y1, double x2, double y2), вычисляющую расстояние
между точкой \((x_1,y_1)\) и \((x_2,y_2)\). Считайте четыре действительных числа
и выведите результат работы этой функции.
| Ввод | Вывод |
|---|---|
0 0 |
1.41421 |
Даны координаты трех точек — вершин треугольника. Вычислите площадь этого треугольника.
| Ввод | Вывод |
|---|---|
0 0 |
0.5 |
Даны два действительных числа \(x\) и \(y\). Проверьте, принадлежит ли точка с координатами
\((x,y)\) заштрихованному квадрату (включая его границу). Если точка принадлежит квадрату, выведите слово YES,
иначе выведите слово NO. На рисунке сетка проведена с шагом 1.
Решение должно содержать функцию bool IsPointInSquare(double x, double y),
возвращающую true, если точка принадлежит квадрату и false, если не принадлежит.
Функция main должна считать координаты точки, вызвать функцию IsPointInSquare
и в зависимости от возвращенного значения вывести на экран необходимое сообщение.
Функция IsPointInSquare не должна содержать инструкцию if.
| Ввод | Вывод |
|---|---|
0 0 |
YES |
3 -7 |
NO |
Решите аналогичную задачу для такого квадрата:
Решение должно соответствовать требованиям для решения задачи D.
| Ввод | Вывод |
|---|---|
0 0 |
YES |
1 1 |
NO |
Даны пять действительных чисел: \(x\), \(y\), \(x_c\), \(y_c\), \(r\). Проверьте, принадлежит ли точка \((x,y)\) кругу с центром \((x_c,y_c)\) и радиусом \(r\).
Решение оформите в виде функции bool IsPointInCircle(double x, double y, double xc, double yc, double r).
Решение должно соответствовать требованиям для решения задачи D.
| Ввод | Вывод |
|---|---|
0.5 0.5 0 0 1 |
YES |
0.5 0.5 1 1 0.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 |
Напишите функцию void Swap(int & a, int & b), обменивающую
значения переменных a и b и не использующую дополнительную вспомогательную переменную.
Сдайте программу, меняющую местами значения двух целочисленных переменных.
| Ввод | Вывод |
|---|---|
1 2 |
2 1 |
Swap без вспомогательной переменнойВозьмите функцию Swap из предыдущей задачи и добавьте к ней функцию main:
int main()
{
int a = 179;
Swap(a, a);
cout << a << endl;
return 0;
}
Запустите программу. Подумайте, почему она вывела такой результат. В тестирующей системе вы должны написать свои пояснения, почему программа выводит такой странный результат.
Даны два натуральных числа \(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 |
Дано натуральное число \(n>1\). Выведите его наименьший делитель, отличный от 1.
Решение оформите в виде функции int MinDivisor(int n). Алгоритм должен
иметь сложность \(O(\sqrt{n})\).
Указание. Если у числа \(n\) нет делителя не превосходящего \(\sqrt{n}\), то число \(n\) — простое и ответом будет само число \(n\).
| Ввод | Вывод |
|---|---|
4 |
2 |
5 |
5 |
Дано натуральное число \(n>1\). Проверьте, является ли оно простым. Программа должна вывести слово
YES, если число простое и NO, если число составное.
Решение оформите в виде функции bool IsPrime(int n), которая возвращает
true для простых чисел и false для составных чисел. Решение
должно иметь сложность \(O(\sqrt{n})\).
| Ввод | Вывод |
|---|---|
2 |
YES |
4 |
NO |
Эпиграф:
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 |
По данным числам \(n\) и \(k\) \((0\le k\le n)\) вычислите \(С_n^k\). Для решения используйте рекуррентное соотношение \(C_n^k=C_{n-1}^{k-1}+C_{n-1}^{k}\).
Решение оформите в виде функции int C(int n, int k).
| Ввод | Вывод |
|---|---|
6 3 |
20 |
Возводить в степень можно гораздо быстрее, чем за \(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 |
Для данного натурального числа \(n\) вычислите сумму всех его натуральных делителей, включая 1 и само число.
Решение оформите в виде функции int SumOfTheDivisors (int n). Решение должно иметь сложность
\(O(\sqrt{n})\).
| Ввод | Вывод |
|---|---|
6 |
12 |
Натуральное число называется совершенным, если оно равно сумме всех своих натуральных делителей, за исключением самого числа. Например, число 6 — совершенное, так как 6=1+2+3.
Напишите программу, которая находит и выводит первые четыре совершенных числа в порядке возрастания. На вход программа не получает ничего.
Тесты к этой задаче закрытые.
Два различных натуральных числа \(n\) и \(m\) называются дружественными, если сумма делителей числа \(n\) (включая 1, но исключая само \(n\)) равна числу \(m\) и наоборот. Например, 220 и 284 – дружественные числа. По данному числу \(k\) ведите все пары дружественных чисел, каждое из которых не превосходит \(k\).
Программа получает на вход одно натуральное число k, не превосходящее \(10^5\).
Программа должна вывести все пары дружественных чисел, каждое из которых не превосходит \(k\). Пары необходимо выводить по одной в строке, разделяя пробелами. Каждая пара должна быть выведена только один раз (перестановка чисел новую пару не дает).
Ограничение по времени работы программы — 1 секунда. Тесты к этой задаче закрытые.
| Ввод | Вывод |
|---|---|
300 |
220 284 |
Мнение конструкторов ЭВМ и математиков о том, что такое деление с остатком для отрицательных чисел расходится. Напомним, что при делении числа \(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 |
Дана последовательность целых чисел, заканчивающаяся числом 0. Выведите эту последовательность в обратном порядке.
При решении этой задачи нельзя пользоваться массивами и прочими динамическими структурами данных. Рекурсия вам поможет.
| Ввод | Вывод |
|---|---|
1 2 3 0 |
0 3 2 1 |
Головоломка “Ханойские башни” состоит из трех колышков, пронумерованных числами 1, 2, 3. На колышек 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного колышка на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку с колышка 1 на колышек 3 за минимальное число перекладываний.
Напишите программу, которая решает головоломку – для данного числа дисков n
печатает последовательность перекладываний в формате
"Disk 1 move from 1 to 2" (диск 1 переложить c колышка 1 на колышек 2), печатая по одной инструкции в строке.
Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.
Программа должна вывести минимальный (по количеству произведенных операций) способ перекладывания пирамидки.
Указание: подумайте, как переложить пирамидку из одного диска? Из двух дисков?
Из трех дисков? Из четырех дисков? Напишите функцию void move (int n, int x, int y), которая
перекладывает пирамидку высоты n с колышка номер x на колышек номер y.
| Ввод | Вывод |
|---|---|
2 |
Disk 1 move from 1 to 2 |
Постановлением ЮНЕСКО оригинал Ханойской башни был подвергнут реставрации. В связи с этим во время пользования головоломкой нельзя было перекладывать кольца с первого стержня сразу на третий и наоборот. Напишите рекурсивную процедуру, которая выводит последовательность перекладываний с учетом таких ограничений.
Программа получает на вход одно натуральное число \(N\) — количество колец на первом стержне \((1\le N\le 7)\).
Программа должна вывести последовательность ходов для перекладывания всех колец на третий стержень в следующем формате: номер кольца, с какого стержня, на какой стержень. Кольца нумеруются от самого маленького до самого большого. Количество ходов не должно превышать \(10^5\).
Тесты к этой задаче закрытые.
| Ввод | Вывод |
|---|---|
1 |
1 1 2 |
Дана полоска из клеток, пронумерованных от 1 до N слева направо. Разрешено снимать или ставить фишку на клетку с номером 1 или на клетку, следующую за самой левой из установленных фишек. Изначально полоска пуста. Нужно разместить фишки во всех клетках.
Программа получает на вход количество клеток в полоске \(N\) \((1\le N\le 10)\).
Программа должна вывести последовательность номеров клеток, с которыми совершается действие. Если фишка снимается, то номер клетки должен выводиться со знаком минус. Количество действий не должно превышать \(10^4\). Если существует несколько возможных решений задачи, то разрешается вывести любое.
Тесты к этой задаче закрытые.
| Ввод | Вывод |
|---|---|
3 |
1 2 -1 3 1 |