Упражнения

A: Медиана трех чисел

Напишите функцию int median(int a, int b, int c), которая получает на вход три числа и возвращает их медиану (среднее из трёх значений).

Сдайте на проверку только тело функции.

median(1, 9, 7)

7

B: Принадлежит ли точка квадрату - 1

Даны два действительных числа \(x\) и \(y\). Проверьте, принадлежит ли точка с координатами \((x,y)\) заштрихованному квадрату (включая его границу). На рисунке сетка проведена с шагом 1.

Решение оформите в виде функции bool is_point_in_square(double x, double y), возвращающую true, если точка принадлежит квадрату и false, если не принадлежит.

Функция is_point_in_square не должна содержать инструкцию if.

Сдайте на проверку только тело функции.

is_point_in_square(0, 0)

true

is_point_in_square(3, -7)

false

C: Принадлежит ли точка квадрату - 2

Решите аналогичную задачу для такого квадрата:

Решение должно соответствовать требованиям для решения задачи C.

Функция должна называться is_point_in_rhombus.

is_point_in_rhombus(0, 0)

true

is_point_in_rhombus(1, 1)

false

D: Принадлежит ли точка кругу

Даны пять действительных чисел: \(x\), \(y\), \(x_c\), \(y_c\), \(r\). Проверьте, принадлежит ли точка \((x,y)\) кругу с центром \((x_c,y_c)\) и радиусом \(r\).

Решение оформите в виде функции bool is_point_in_circle(double x, double y, double xc, double yc, double r).

Решение должно соответствовать требованиям для решения задачи C.

is_point_in_circle(0.5, 0.5, 0, 0, 1)

true

is_point_in_circle(0.5, 0.5, 1, 1, 0.1)

false

E: Принадлежит ли точка области

Проверьте, принадлежит ли точка данной закрашенной области. Область неограничена снизу.

Решение оформите в виде функции bool is_point_in_area(double x, double y).

Решение должно соответствовать требованиям для решения задачи С.

bool is_point_in_area(-1, 2)

true

bool is_point_in_area(0, 0)

false

F: Разверните число

Дано число, получите число, составленное из тех же цифр, записанных в обратном порядке.

Решение оформите в виде функции int reverse(int n), которая получает на вход значение типа int и возвращает значение типа int.

reverse(179)

971

G: Минимальный делитель числа

Дано натуральное число \(n>1\). Найдите его наименьший делитель, отличный от 1.

Решение оформите в виде функции long long min_divisor(long long n). Алгоритм должен иметь сложность \(O(\sqrt{n})\). Обратите внимание на используемый тип данных.

Указание. Если у числа \(n\) нет делителя не превосходящего \(\sqrt{n}\), то число \(n\) — простое и ответом будет само число \(n\).

Сдайте на проверку только тело функции.

min_divisor(4)

2

min_divisor(5)

5

H: Проверка числа на простоту

Дано натуральное число \(n>1\). Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное.

Решение оформите в виде функции bool is_prime(long long n), которая возвращает true для простых чисел и false для составных чисел. Решение должно иметь сложность \(O(\sqrt{n})\).

Сдайте на проверку только тело функции.

is_prime(2)

true

is_prime(4)

false

I: Сократите дробь

Даны два натуральных числа \(n\) и \(m\). Сократите дробь \(\frac{n}{m}\), то есть выведите два других числа \(p\) и \(q\) таких, что \(\frac{n}{m}=\frac{p}{q}\) и дробь \(\frac{p}{q}\) — несократимая.

Решение оформите в виде функции void reduce_fraction(int & n, int & m), получающая значения n и m по ссылке и изменяющая их.

Сдайте на проверку только тело функции.

J: Деление с остатком

Мнение конструкторов ЭВМ и математиков о том, что такое деление с остатком для отрицательных чисел расходится. Напомним, что при делении числа \(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. Это даст такие результаты с точки зрения математики:

26

10

2

6

-26

10

-3

4

26

-10

-3

-4

-26

-10

2

-6

Напишите программу, которая по данным числам \(a\) и \(b\) вычисляет их целочисленное частное и остаток от деления так, как это принято в математике. Программа не должна использовать действительные числа и циклы.

Решение оформите в виде функции void div_mod(int a, int b, int & q, int & r), где a — делимое, b — делитель, q — переменная для записи частного, r — переменная для записи остатка.

Сдайте на проверку только тело функции.

K: Упорядочить четыре числа

Дано четыре целых числа \(a\), \(b\), \(c\), \(d\). Упорядочите эти числа в порядке неубывания, то есть необходимо переставить их значения так, чтобы \(a\le b\le c\le d\). Решение оформите в виде функции void sort(int & a, int & b, int & c, int & d).

Функция должна содержать только операции вида

if (a > b)
    swap(a, b);

Вложенные инструкции if не допускаются. Внутри одной инструкции if может быть только один swap. Ветки else тоже использовать не нужно.

Сдайте на проверку только тело функции.

K+: Минимальное число обменов (задача на подумать)

Какое наименьшее количество обменов может содержать решение предыдущей задачи?

Упражнения на рекурсию

L: Возведение в степень

Дано действительное положительное число \(a\) и целое неотрицательное число \(n\). Вычислите \(a^n\) не используя циклы и стандартную функцию pow, а используя рекуррентное соотношение \(a^n=a\cdot a^{n-1}\).

Решение оформите в виде функции double power(double a, int n).

Сдайте на проверку только тело функции.

2
3

8

M: Числа Фибоначчи

Последовательность Фибоначчи определяется так: \[ \cases{\varphi_0=0, \cr \varphi_1=1, \cr \varphi_{n}=\varphi_{n-1}+\varphi_{n-2} \mbox{, при } n \gt 1.} \]

Напишите функцию int fib(int n), которая по данному целому неотрицательному n возвращает \(n\)-e число Фибоначчи.

Сдайте на проверку только тело функции.

6

8

M+: Полезна ли рекурсия? (задача на подумать)

Запустите программы, вычисляющие числа Фибоначчи при помощи рекурсивного и нерекурсивного алгоритма. Сравните время их работы для n=10, 20, 30, 40, 50. Объясните результат.

N: Рекурсия вместо цикла

Напишите рекурсивную функцию void print(int n), вызов которой приводит к печати на экран натуральных чисел от 1 до \(n\). Циклы использовать нельзя.

Подсказка. Число \(n\) является параметром. Как свести задачу “вывести числа от 1 до \(n\)” к задаче с меньшим значением параметра?

Сдайте на проверку только тело функции.

3

1 2 3

O: Произведение последовательности

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

Решение оформите в виде функции int sum(), не принимающую параметров, которая возвращает (при помощи return) значение суммы считанных со стандартного ввода чисел. Сама функция ничего не выводит, а только возвращает результат.

Подсказка: функция должна считать одно число, после чего сделать рекурсивный вызов для решения меньшей задачи.

Сдайте на проверку только тело функции.

1
7
9
0

17

P: Разворот последовательности

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

Программа должна содержать функцию void reverse(), не принимающую параметров, которая считывает со стандартного ввода последовательность чисел до появления числа 0 и выводит эту же последовательность в обратном порядке. Функция должна считать одно число и, если это число не 0, вызвать себя рекурсивно.

Сдайте на проверку только тело функции.

1
2
3
0

0
3
2
1

Q: Быстрое возведение в степень

Возводить в степень можно гораздо быстрее, чем за \(n\) умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:

\(a^n=(a^2)^{n/2}\) при четном \(n\),

\(a^n=a\cdot a^{n-1}\) при нечетном \(n\).

Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет \(O(\log n)\).

Решение оформите в виде функции double power(double a, int n).

Сдайте на проверку только тело функции.

1.000000001
1000000000

2.718282030814511

R: Алгоритм Евклида

Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: \(НОД(a,b)=НОД(a\bmod b,b)\).

Реализуйте рекурсивный алгоритм Евклида в виде функции int gcd(int a, int b).

Сдайте на проверку только тело функции.

12
16

4

S: Ханойские башни

Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 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\) дисков.

Решение оформите в виде функции void move(int n, int start, int finish), которая печатает последовательность перекладываний дисков для перемещения пирамидки высоты n со стержня номер start на стержень номер finish.

Сдайте на проверку только тело функции.

В примере ниже пирамидка из 2 дисков перекладывается со стержня 1 на стержень 3.

2

1 1 2
2 1 3
1 2 3

T: Ремонт в Ханое

Постановлением ЮНЕСКО оригинал Ханойской башни был подвергнут реставрации. В связи с этим во время пользования головоломкой нельзя было перекладывать кольца с первого стержня сразу на третий и наоборот.

Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.

В этой и последующих задачах на проверку необходимо сдать программу полностью.

Тесты к этой задаче закрытые.

1

1 1 2
1 2 3

2

1 1 2
1 2 3
2 1 2
1 3 2
1 2 1
2 2 3
1 1 2
1 2 3

U: Циклические башни

На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1.

Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.

1

1 1 2
1 2 3

2

1 1 2
1 2 3
2 1 2
1 3 1
2 2 3
1 1 2
1 2 3

V: Несправедливые башни

В Ханое несправедливо запретили класть самый маленький диск (номер 1) на средний колышек (номер 2).

Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.

2

1 1 3
2 1 2
1 3 1
2 2 3
1 1 3

W: Сортирующие башни

Первоначально все диски лежат на стержне номер 1. Переместите диски с нечетными номерами на стержень номер 2, а с четными номерами - на стержень номер 3.

Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.

2

1 1 2
2 1 3

3

1 1 2
2 1 3
1 2 3
3 1 2
1 3 2

X: Обменные башни

Как и в предыдущих задачах, дано три стержня, на первом из которых надето \(n\) дисков различного размера. Необходимо их переместить на стержень 3 по следующим правилам:

Самый маленький диск (номер 1) можно в любой момент переложить на любой стержень. Перемещение диска номер 1 со стержня a на стержень b будем обозначать 1 a b.

Можно поменять два диска, лежащих на вершине двух стержней, если размеры этих дисков отличаются на 1. Например, если на вершине стержня с номером a лежит диск размером 5, а на вершине стержня с номером b лежит диск размером 4, то эти диски можно поменять местами. Такой обмен двух дисков будем обозначать 0 a b (указываются номера стержней, верхние диски которых обмениваются местами).

Для данного числа дисков \(n\), не превосходящего 10, найдите решение головоломки. вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000.

1

1 1 3

2

1 1 3
0 1 3
1 1 3

Y: Фишки

Дана полоска из клеток, пронумерованных от 1 до N слева направо. Разрешено снимать или ставить фишку на клетку с номером 1 или на клетку, следующую за самой левой из установленных фишек. Изначально полоска пуста. Нужно разместить фишки во всех клетках.

Программа получает на вход количество клеток в полоске \(N\) \((1\le N\le 10)\).

Программа должна вывести последовательность номеров клеток, с которыми совершается действие. Если фишка снимается, то номер клетки должен выводиться со знаком минус. Количество действий не должно превышать \(10^4\). Если существует несколько возможных решений задачи, то разрешается вывести любое.

Тесты к этой задаче закрытые.

3

1 2 -1 3 1

Z: Небоскреб

В небоскребе \(n\) этажей. Известно, что если уронить стеклянный шарик с этажа номер \(p\), и шарик разобьется, то если уронить шарик с этажа номер \(p+1\), то он тоже разобьется. Также известно, что при броске с последнего этажа шарик всегда разбивается.

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

Определите, какого числа бросков достаточно, чтобы заведомо решить эту задачу.

Программа получает на вход количество этажей в небоскребе \(n\) и выводит наименьшее число бросков, при котором можно всегда решить задачу.

Тесты к этой задаче закрытые.

4

2

20

6

Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа.

Подсказки.
1. Как следует действовать, если шарик был бы только один?
2. Пусть шариков два и мы бросили один шарик с этажа номер \(k\). Как мы будем действовать в зависимости от того, разобьется ли шарик или нет?
3. Пусть f(n) - это минимальное число бросков, за которое можно определить искомый этаж, если бы в небоскребе было n этажей. Выразите f(n) через значения f(a) для меньших значений a.

ZA: Небоскрёб-2

Аналогично условию первой задачи, в здании \(n\ge2\) этажей, а у вас есть \(k\ge 1\) шариков. Определите минимальное количество бросков, при помощи которого можно определить минимальный номер этажа, при броске с которого шарик разбивается. При броске с этажа \(n\) шарик всегда разбивается.

Программа получает на вход два числа \(n\) и \(k\) и должна вывести одно число — необходимое число бросков.

4
2

2

20
2

6

ZB: Небоскрёб-3

Теперь в небоскрёбе \(n\) этажей, и вам нужно опять-таки определить номер минимального этажа, при броске с которого шарик разбивается, при броске с этажа \(n\) шарик всегда разбивается. Вы успеете сделать не более \(t\) бросков, \(n\le 2^t\). Определите, какое минимальное количество шариков вам нужно иметь для того, чтобы решить эту задачу не более, чем за \(t\) бросков.

20
6

2

ZС: Построение кривой дракона

Рассмотрим кривую дракона на шаге номер \(n\ge 2\). Вы движетесь из точки (0, 0) и выписываете направления поворотов после прохождения каждого отрезка. Поворот направо обозначается буквой R, поворот налево — буквой L. Выведите последовательность поворотов.

Программа получает на вход число \(n\ge 2\) и должна вывести последовательность из букв L и R в одной строке без пробелов.

3

RRL

4

RRLRRLL