Возводить в степень можно гораздо быстрее, чем за \(n\) умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:
\(a^n=(a^2)^{n/2}\) при четном \(n\),
\(a^n=a\cdot a^{n-1}\) при нечетном \(n\).
Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет \(O(\log n)\).
Вводится действительное число a и целое неотрицательное число n.
Выведите ответ на задачу.
Нельзя использовать стандартное возведение в степень.
2 7
128
1.00001 100000
2.71827
Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: \(НОД(a, b)=НОД(b, a\bmod b)\).
Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b)
.
Вводится два целых числа.
Выведите ответ на задачу.
12 14
2
256 48
16
Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 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 2 1 3 1 2 3
Постановлением ЮНЕСКО оригинал Ханойской башни был подвергнут реставрации. В связи с этим во время пользования головоломкой нельзя было перекладывать кольца с первого стержня сразу на третий и наоборот.
Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.
Вводится натуральное число - количество колец.
Выведите ответ на задачу.
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
На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1.
Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.
Вводится натуральное число - количество дисков.
Выведите ответ на задачу. Башню необходимо переместить со стержня 1 на стержень 3.
2
1 1 2 1 2 3 2 1 2 1 3 1 2 2 3 1 1 2 1 2 3