Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 28
U: Разворот числа
Ни разу не видел более плохого решения, вы хотите получить целое число, но при этом используете логарифмы и экспоненты для такой тривиальной задачи. К тому же у вас по условию только целочисленная арифметика.
public class Solution {
public static int recursion(int n, int i) {
return (n==0) ? i : recursion( n/10, i*10 + n%10 );
}
public static void main(String[] args) {
System.out.println(recursion(158, 0));
}
}
A: От 1 до n — склеивать числа в строку крайне неэффективно, почему бы их прямо из функции не печатать?
B: От A до B — аналогично
D: Точная степень двойки — решение через числа с плавающей точкой просто режет глаза, неужели нельзя было просто делить пополам и проверять остаток от деления?
H: Проверка числа на простоту — в условии решение должно быть за O(logN), ваше же решение O(N) по вычислениям и O(N) по памяти засчет стека рекурсии
I: Разложение на множители — FYI, даже решето Эратосфена не дает O(logN). Ваше решение O(N) по вычислениям и O(N) по памяти
K: Вывести нечетные числа последовательности — пример вообще дикий, при этом зачем-то два рекурсивных вызова вместо одного
S: Заданная сумма цифр — тут хорошо добавить условия ранней остановки рекурсии (sum > s) и меморизацию по (len,sum) чтобы тысячи раз не считать одно и то же
U: Разворот числа — как уже заметили, решение с логарифмами и степенями весьма дико. Код будет такой:
Хорошие задачи на рекурсию:
Задача на BFS/DFS — http://www.careercup.com/question?id=4716965625069568
Задача на аналог qsort — найдите k-ое по величине число в заданной последовательности
B: От A до B — аналогично
D: Точная степень двойки — решение через числа с плавающей точкой просто режет глаза, неужели нельзя было просто делить пополам и проверять остаток от деления?
H: Проверка числа на простоту — в условии решение должно быть за O(logN), ваше же решение O(N) по вычислениям и O(N) по памяти засчет стека рекурсии
I: Разложение на множители — FYI, даже решето Эратосфена не дает O(logN). Ваше решение O(N) по вычислениям и O(N) по памяти
K: Вывести нечетные числа последовательности — пример вообще дикий, при этом зачем-то два рекурсивных вызова вместо одного
S: Заданная сумма цифр — тут хорошо добавить условия ранней остановки рекурсии (sum > s) и меморизацию по (len,sum) чтобы тысячи раз не считать одно и то же
U: Разворот числа — как уже заметили, решение с логарифмами и степенями весьма дико. Код будет такой:
def rev(num,tmp):
res = tmp*10 + num%10
if num > 10:
res = rev(num/10, res)
return res
print rev(123456789,0)
Хорошие задачи на рекурсию:
Задача на BFS/DFS — http://www.careercup.com/question?id=4716965625069568
Задача на аналог qsort — найдите k-ое по величине число в заданной последовательности
Огромное спасибо за замечания!
>>A: От 1 до n — склеивать числа в строку крайне неэффективно, почему бы их прямо из функции не печатать?
>>B: От A до B — аналогично
Согласен, можно было бы и так. Но задача была слишком простой и поэтому данное решение ни чем не пугало.
>>D: Точная степень двойки — решение через числа с плавающей точкой просто режет глаза, неужели нельзя было просто делить пополам и проверять остаток от деления?
Я и делю пополам и проверяю делимость в конце. Алгоритм должен работать за логорифм. А какое именно решение вы предлагаете?
>>H: Проверка числа на простоту — в условии решение должно быть за O(logN), ваше же решение O(N) по вычислениям и O(N) по памяти засчет стека рекурсии
Было бы интересно увидить вариант более эффективный
>>I: Разложение на множители — FYI, даже решето Эратосфена не дает O(logN). Ваше решение O(N) по вычислениям и O(N) по памяти
Абсолютно согласен. Алгоритм за логарифмическое время не пришел в голову. Не знаю почему в условии просили за логорифм.
>>K: Вывести нечетные числа последовательности — пример вообще дикий, при этом зачем-то два рекурсивных вызова вместо одного
Но сработает же всего один вызов, нет? если написать так
или же можно написать алгоритм эффективнее?
>>S: Заданная сумма цифр — тут хорошо добавить условия ранней остановки рекурсии (sum > s) и меморизацию по (len,sum) чтобы тысячи раз не считать одно и то же
Можете написать ваш вариант?
>>U: Разворот числа — как уже заметили, решение с логарифмами и степенями весьма дико. Код будет такой:
Согласен
>>A: От 1 до n — склеивать числа в строку крайне неэффективно, почему бы их прямо из функции не печатать?
>>B: От A до B — аналогично
Согласен, можно было бы и так. Но задача была слишком простой и поэтому данное решение ни чем не пугало.
>>D: Точная степень двойки — решение через числа с плавающей точкой просто режет глаза, неужели нельзя было просто делить пополам и проверять остаток от деления?
Я и делю пополам и проверяю делимость в конце. Алгоритм должен работать за логорифм. А какое именно решение вы предлагаете?
>>H: Проверка числа на простоту — в условии решение должно быть за O(logN), ваше же решение O(N) по вычислениям и O(N) по памяти засчет стека рекурсии
Было бы интересно увидить вариант более эффективный
>>I: Разложение на множители — FYI, даже решето Эратосфена не дает O(logN). Ваше решение O(N) по вычислениям и O(N) по памяти
Абсолютно согласен. Алгоритм за логарифмическое время не пришел в голову. Не знаю почему в условии просили за логорифм.
>>K: Вывести нечетные числа последовательности — пример вообще дикий, при этом зачем-то два рекурсивных вызова вместо одного
Но сработает же всего один вызов, нет? если написать так
if (n % 2 == 1) {
System.out.println(n);
}
recursion();
или же можно написать алгоритм эффективнее?
>>S: Заданная сумма цифр — тут хорошо добавить условия ранней остановки рекурсии (sum > s) и меморизацию по (len,sum) чтобы тысячи раз не считать одно и то же
Можете написать ваш вариант?
>>U: Разворот числа — как уже заметили, решение с логарифмами и степенями весьма дико. Код будет такой:
Согласен
Задача D — можно ограничиться целыми числами:
H — самая очевидная оптимизация — это проверять делимость не до N/2, а до sqrt(N), сложность уже будет O(sqrt(N)). Есть еще вот такой вариант: en.wikipedia.org/wiki/AKS_primality_test, а вообще это сложная проблема: www.math.uni-bonn.de/people/saxena/talks/May2007-Turku.pdf
Задача S — вот оба варианта, реализованные на Python. Рекурсивный начинает тормозить уже при вычислении суммы для 9 символов, а вариант с меморизацией выводит результат и для 50 символов за миллисекунды:
Решение
def ispow2(num):
if num == 1:
return True
if num % 2 == 1:
return False
return ispow2(num/2)
print ispow2(1024)
H — самая очевидная оптимизация — это проверять делимость не до N/2, а до sqrt(N), сложность уже будет O(sqrt(N)). Есть еще вот такой вариант: en.wikipedia.org/wiki/AKS_primality_test, а вообще это сложная проблема: www.math.uni-bonn.de/people/saxena/talks/May2007-Turku.pdf
Задача K
вместо:
написать:
// Шаг рекурсии / рекурсивное условие
if (n % 2 == 1) {
System.out.println(n);
recursion();
} else {
recursion();
}
написать:
// Шаг рекурсии / рекурсивное условие
if (n % 2 == 1) {
System.out.println(n);
}
recursion();
Задача S — вот оба варианта, реализованные на Python. Рекурсивный начинает тормозить уже при вычислении суммы для 9 символов, а вариант с меморизацией выводит результат и для 50 символов за миллисекунды:
Задача S
# Recursive version
def findrec(target, length):
res = 0
if length == 1 and target < 10:
res = 1
elif length > 1:
for i in range(min(10,target)):
res += findrec(target-i, length-1)
return res
# Memorization version
def findmem(target, length, mem):
if mem[target][length] > -1:
return mem[target][length]
res = 0
if length == 1 and target < 10:
res = 1
elif length > 1:
for i in range(min(10,target)):
r = findmem(target-i, length-1, mem)
mem[target-i][length-1] = r
res += r
return res
def find(target, length):
mem = [[-1]*(length+1) for _ in range(target+1)]
return findmem(target, length, mem)
Алгоритм за логарифмическое время не пришел в голову.
Если бы пришёл, было бы круто! Алгоритм Шора для факторизации чисел имеет сложность O((log N)²(log log N)(log log log N)), что похуже логарифма. А вопрос о существовании даже полиномиального алгоритма для обычных компьютерах до сих пор открыт.
Наверное, в условии просто опечатка была.
склеивать числа в строку крайне неэффективно, почему бы их прямо из функции не печатать?
Вот как раз «печатать» и есть очень недешевая операция, если будем говорить о перфомансе рекурсивных решений, то лучше прокинуть StringBuilder аргументом и распечатать буфер один раз.
Решил Вашу задачку из Google. Было интересно, спасибо!
Вот моё решение :)
Вот моё решение :)
Спасибо автору, что все вместе и сразу в одной статье.
И в дополнение
И в дополнение
Рекурсивный поворот строки
источник
public static String reverseRecursively(String str) {
//base case to handle one char string and empty string
if (str.length() < 2) {
return str;
}
return reverseRecursively(str.substring(1)) + str.charAt(0);
}
источник
1. Если рекурсию можно заменить циклом то в большинстве современных языков программирования такое решение окажется более эффективным (память, быстродействие). Поэтому всякие факториалы, числа Фибоначи и т.д. надо искать не рекурсивными, а итеративными алгоритмами.
2. Рекурсивные алгоритмы, это алгоритмы класса «разделяй и властвуй». Есть смысл их применять тогда, когда задачу итеративно решать сложнее. Хорошие примеры: обход графа/дерева, построений кривых Гильберта и Серпинского.
2. Рекурсивные алгоритмы, это алгоритмы класса «разделяй и властвуй». Есть смысл их применять тогда, когда задачу итеративно решать сложнее. Хорошие примеры: обход графа/дерева, построений кривых Гильберта и Серпинского.
Если в компиляторе есть оптимизация хвостовой рекурсии, то он сам превратит рекурсию в цикл.
К тому же потребление памяти — это не какая-то магия. Можно примерно прикинуть потребление памяти на один вызов зная количество и типы локальных переменных, аргументов и т. д., также можно оценить глубину рекурсии. С учётом этой информации уже можно принимать решение о том, стоит рекурсию использовать или нет.
Например, если взять бинарный поиск, то глубина рекурсивных вызовов даже для массива длиной 1024 будет равна всего 10. Если большие массивы гарантированно не используются, то почему бы не написать рекурсивную функцию? С точки зрения быстродействия вызов функции, которая делает что-то значимое, ненамного медленнее цикла.
И наоборот, рекурсию всегда можно превратить в цикл, только потребуется использовать дополнительную память для хранения очереди вызовов.
К тому же потребление памяти — это не какая-то магия. Можно примерно прикинуть потребление памяти на один вызов зная количество и типы локальных переменных, аргументов и т. д., также можно оценить глубину рекурсии. С учётом этой информации уже можно принимать решение о том, стоит рекурсию использовать или нет.
Например, если взять бинарный поиск, то глубина рекурсивных вызовов даже для массива длиной 1024 будет равна всего 10. Если большие массивы гарантированно не используются, то почему бы не написать рекурсивную функцию? С точки зрения быстродействия вызов функции, которая делает что-то значимое, ненамного медленнее цикла.
И наоборот, рекурсию всегда можно превратить в цикл, только потребуется использовать дополнительную память для хранения очереди вызовов.
Java с хвостовой рекурсией не дружит, а пост был явно привязан к ней.
Я бы еще добавил, что рекурсию не редко проще понять(далеко не всегда и, возможно, субъективно). В примере с тем же бинсерчем гораздо легче будет вникнуть в вариант без цикла
Я бы еще добавил, что рекурсию не редко проще понять(далеко не всегда и, возможно, субъективно). В примере с тем же бинсерчем гораздо легче будет вникнуть в вариант без цикла
Именно, когда есть возможность разделить данные на несколько равных частей, рекурсия самое оно, а когда мы входняе данные делим на две части размера 1 и (n-1). То лучше итеративные алгоритмы.
I: Разложение на множители Проверку множителей можно останавливать уже при k > Math.sqrt(n). У числа нет простых множителей, больших корня из него. Ну и про логарифм уже написали.
>> Самый простой вариант увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив.
Вот и выросло поколение, никогда не видевшее зеркал.
Вот и выросло поколение, никогда не видевшее зеркал.
D: Точная степень двойки
Разве не так?
def foo(n):
if n & (n - 1) == 0:
print('YES')
print('NO')
скорее всего вы имели ввиду
не знаком с питоном так сильно но решение работает! отлично! Можете обьяснить что означает n & (n — 1) == 0?
def foo(n):
if n & (n - 1) == 0:
print('YES')
else:
print('NO')
не знаком с питоном так сильно но решение работает! отлично! Можете обьяснить что означает n & (n — 1) == 0?
У степени двойки установлен всего один бит, у n-1 этот бит будет сброшен и их конъюнкция гарантированно даст 0. Условие выполняется только для степени двойки, т.к. при наличии более одного установленного бита будет сброшен только младший.
Отличное решение, но решение не является рекурсивным) Условие задачи требует решить ее с помошью рекурсии
B:
Что-то мне подсказывает что так не бывает:
Хотя бы так
public static String recursion(int a, int b) {
// основное условие задачи
if (a > b) {
// Базовый случай
if (a == b) {
return Integer.toString(a);
}
// Шаг рекурсии / рекурсивное условие
return a + " " + recursion(a - 1, b);
} else {
// Базовый случай
if (a == b) {
return Integer.toString(a);
}
// Шаг рекурсии / рекурсивное условие
return a + " " + recursion(a + 1, b);
}
}Что-то мне подсказывает что так не бывает:
if (a > b) {
// Базовый случай
if (a == b) {Хотя бы так
public static String recursion(int a, int b) {
if (a == b) {
return Integer.toString(a);
}
return a > b
? a + " " + recursion(a - 1, b)
: a + " " + recursion(a + 1, b);
}
какие-то они оторванные от реальности. По-моему, любые задачки на действия с json-объектами или там с графами, имеют куда больший смысл — решать их с помощью рекурсии естественней и проще. А тут «обойдитесь без цикла for» — а зачем мне обходиться без цикла for если есть цикл for?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Рекурсия. Занимательные задачки