Не получается написать рекурсивную функцию [закрыт]
Учебные задания допустимы в качестве вопросов только при условии, что вы пытались решить их самостоятельно перед тем, как задать вопрос. Пожалуйста, отредактируйте вопрос и укажите, что именно вызвало у вас трудности при решении задачи. Например, приведите код, который вы написали, пытаясь решить задачу
Закрыт 3 года назад .
Помогите написать рекурсивную функцию, которая раскладывает число на простые сомножители. Например, 378 = 2*3*3*3*7
Напишите рекурсивную функцию, которая раскладывает число на простые сомножители. Пример: Введите натуральное число: 378 378 = 2*3*3*3*7
function factorization ( numeric: integer ): integer;
var d: integer;
begin
write(numeric, ‘ = 1’);
d := 2;
while numeric > 1 do
begin
if numeric mod d = 0 then
begin
write (‘ * ‘, d);
numeric := numeric div d;
end
else inc(d);
end;
end;
var x: integer;
begin
write(‘Введите число: ‘);
readln(x);
factorization(x);
end.
Разложение на множители и простые числа.
В задачах ЕГЭ по информатике часто требуется находить множители числа и проверять, является ли данное число простым. Рассмотрим способы делать это достаточно быстро.
Разложение на множители.
Самый простой способ разложения числа на множители: проверить его делимость на все числа, начиная с 2 и кончая числом, равным половине исходного. Но этот способ — слишком медленный.
Ускорить процедуру можно, если учесть тот факт, что если число n делится на число k, то оно делится и на n//k. Тогда можно проверить лишь числа от 2 до квадратного корня из n. Когда мы находим число k, на которое делится число n, то добавляем в список делителей два делителя: k и n//k. Один тонкий момент: если число n является точным квадратом числа k, то и k, и n//k — это одинаковые числа. Поэтому нужно ввести проверку и добавлять в список делителей n//k только в том случае, если это число не равно k. Тем самым мы избежим включения в массив делителей двух одинаковых чисел.
Приведем текст функции на Питоне, которая вычисляет все делители числа n, кроме единицы и самого числа n (так называемые нетривиальные делители) и возвращает массив, содержащий эти делители.
def divisors(n):
d=[]
k=2
while k*k <= n:
if n%k == 0:
d.append(k)
k2 = n//k
if k2 > k: d.append(k2)
k += 1
return d
Условие k*k <= n прекращает выполнение цикла поиска делителей, когда k станет больше, чем квадратный корень из n. Почему мы записали его так, а не в виде k<=sqrt(n)? На это есть две причины.
Во-первых, операция умножения выполняется гораздо быстрее, чем извлечение корня. Во-вторых, функция извлечения корня возвращает вещественный результат. А операции над вещественными числами выполняются лишь приближенно, и квадратный корень из 4 при вычислениях может оказаться равным 2.0000000001, а может и 1.9999999999. Понятно, что это может сказаться на результате сравнения самым пагубным образом.
Делители в массиве не упорядочены по возрастанию. Так, для числа 60 получается следующий результат:
[2, 30, 3, 20, 4, 15, 5, 12, 6, 10]
Если требуется упорядоченность, то нужно либо отсортировать полученный массив, либо вставлять делители в массив, поддерживая его упорядоченность (например, с помощью функции insort из модуля bisect).
Проверка числа на простоту.
Проверка, является ли данное число простым, имеет много общего с поиском делителей. Если число простое, то оно не имеет нетривиальных делителей. Поэтому для данной цели можно использовать приведенную выше функцию: если результатом ее является пустой массив, то число простое.
Но можно написать для этой цели и отдельную функцию. Приведем её текст:
def isprime(n):
k=2
while k*k <= n:
if n%k == 0: return False
k += 1
return True
Функция возвращает True, если число n — простое.
Данная функция работает несколько быстрее, чем функция divisors, т.к. она завершает работу после того, как найден первый делитель, а не ищет все делители.
Существуют и более быстрые алгоритмы для решения данных задач, но они достаточно сложны, и на ЕГЭ их не имеет смысла применять.
рекурсивная функция для нахождения простых множителей
Вам нужно установить флаг = 1 в prime , и верните его в конце. Или, лучше, когда вы найдете множитель, верните 0; если вы опустите конец цикла, верните 1. Обратите внимание, что вам действительно нужно дойти до квадратного корня из числа, чтобы найти множители. Это не имеет большого значения, если в вашем номере менее 10 цифр, но действительно имеет значение, если цифр намного больше. — Jonathan Leffler
@James: Turbo C активно использовался в академическом мире как минимум до 2003 года 🙂 — neal aise
11 ответы
(слишком сонный, чтобы писать хороший код .. поэтому заранее извиняюсь за любые ошибки: p)
более простая нерекурсивная версия
если вам нужно использовать рекурсию
ответ дан 02 апр.
скоро будет какое-то объяснение. Извини за это — Нил Эйс
ты все еще сонный? или вы уже должны были исправить этот код — СувикМаджи
Как вы думаете, какая ценность i будет в (*) ?
Не уверен, что ты хочешь i для начала как, но я почти уверен, что вы не хочу, чтобы это было что-то случайное. Если вы хотите, чтобы он начинался со значения num , вам нужно назначить num к нему после прочтения:
Создан 11 июля ’10, 00:07
я изо всех сил старался выбраться из void main, но это то, чему меня учат 🙁 int main() во много раз лучше — user379888
@fahad это и чтобы быть int main(void) в вашем случае (другой случай, когда у вас есть параметры командной строки), обучите своих учителей этому: en.wikipedia.org/wiki/Main_function_(programming)#C_and_C.2B.2B — Нил Эйс
Полное рекурсивное решение на С++ (для c заменить строки cout на printf):
Почему static обязательно в этом случае? — Синдзо
Лучший способ реализовать простую факторизацию с низкими накладными расходами на вызовы функций — это . . .
Количество вызовов функции (рекурсии) равно количеству простых множителей, включая 1.
ответ дан 24 окт ’13, 17:10
Я сделал это на C. В зависимости от компилятора могут потребоваться небольшие изменения в программе.
Согласен с IVlad — также, что происходит в случае, когда num простое число? Сколько раз будет вызываться рекурсивная функция, например, для num = 7?
Создан 11 июля ’10, 00:07
. и — как Prime возвращает свое значение вызывающей стороне? — Будет А
я использовал свою концепцию расчета простого множителя и программу простого множителя, сделанную без рекурсии, для помощи. pastebin.com/fVbjFGzQ — пользователь379888
Я не вижу оператора возврата нигде в вашей основной функции. Кроме того, попробуйте выполнить код с num = 7 (и присваиванием i = num в нужном месте) и посмотрите, что произойдет. — Будет А
Создан 04 июля ’14, 18:07
Я предлагаю вам не включать исправленный код, а только объяснение рассматриваемой ошибки и общее руководство по ее устранению. — Теохарис К.
Нет необходимости добавлять ответ на уже правильно отвеченный вопрос. И как @TheocharisK. сказал, пожалуйста, добавьте также объяснение к вашему ответу в следующий раз. И кстати. Добро пожаловать в SO. — Пр0гр4мм3р
Хотя этот код может ответить на вопрос, предоставление дополнительного контекста относительно того, как и / или почему он решает проблему, улучшит долгосрочную ценность ответа. — Дональд Дак
Это старый вопрос, но все же я хотел бы дать на него ответ. [Не голосуйте против, не попробовав мой код. Оно работает! ]
Нам не нужно писать функцию для вычисления следующего простого числа. Если, например, число равно 24, и мы непрерывно делим его на 2, пока оно не перестанет делиться на 2, то никакие другие числа, кратные 2, также не могут делить это число. Таким образом, в конечном итоге только (вероятно) простые числа могут точно делить любое положительное целое число.
Вот мой код: (я написал исходный код как для итеративной, так и для рекурсивной логики)
ответ дан 13 мая ’20, 21:05
Просто к вашему сведению: голосование против исключительно раньше говорил «этот ответ не работает». Это может означать «это не лучший подход» или «это не очень хорошее объяснение» или даже «это ничего не добавляет к существующим ответам». Чтобы написать хороший ответ о переполнении стека, нужно многое! К сожалению, многие участники голосуют против, не оставляя комментариев, что не является особенно четким сигналом того, на что они реагируют. — Джереми Кейни
Однако для чего бы это ни стоило, для этого ответа я ценю, что вы предлагаете объяснение кода, предоставляете пример работающего кода, а затем предоставляете ссылку для получения дополнительной информации. Единственный дополнительный момент, который я бы порекомендовал, — это краткое объяснение того, почему это отличается от существующих ответов. — Джереми Кейни
Спасибо, что сообщили мне обо всем этом. С этого момента я буду помнить обо всем этом при публикации на StackOverFlow. — Сатиш