O: Сумма последовательности

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

1
7
9
0

17

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

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

При решении этой задачи нельзя пользоваться массивами и прочими динамическими структурами данных. Рекурсия вам поможет.

1
2
3
0

0 3 2 1

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

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

an=(a2)n/2an=(a2)n/2 при четном nn,

an=a⋅an−1an=a⋅an−1 при нечетном nn.

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

1.000000001 1000000000

2.71828

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

Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида.

Он построен на следующем соотношении: НОД(a,b)=НОД(amodb,b)НОД(a,b)=НОД(amodb,b).

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

12 16

4

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

Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из nn дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.

Напишите программу, которая решает головоломку; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск.

Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

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

Указание: подумайте, как переложить пирамидку из одного диска? Из двух дисков? Из трех дисков? Из четырех дисков? Пусть мы научились перекладывать пирамидку из nn дисков с произвольного стержня на любой другой, как переложить пирамидку из n+1n+1 диска, если можно пользоваться решением для nn дисков.

Напишите функцию move (n, x, y), которая печатает последовательнось перекладываний дисков для перемещения пирамидки высоты n со стержня номер x на стержень номер y.

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: Обменные башни

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

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

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

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

1

1 1 3

2

1 1 3
0 1 3
1 1 3

Y: Фишки

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

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

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

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

3

1 2 -1 3 1