Не получается написать рекурсивную функцию [закрыт]
Закрыт. Этот вопрос не по теме. Ответы на него в данный момент не принимаются.
Учебные задания допустимы в качестве вопросов только при условии, что вы пытались решить их самостоятельно перед тем, как задать вопрос. Пожалуйста, отредактируйте вопрос и укажите, что именно вызвало у вас трудности при решении задачи. Например, приведите код, который вы написали, пытаясь решить задачу
Закрыт 4 года назад .
Помогите написать рекурсивную функцию, которая раскладывает число на простые сомножители. Например, 378 = 2*3*3*3*7
Рекурсивная функция, язык Python.
опять мудрите? 🙂
F = lambda n, k=2: [n] if k * k > n else F(n, k + 1) if n % k else [k] + F(n // k, k)
правда оба варианта рухнут с переполнением стека на числе с большими делителями. разве что мой чуть позже. вообще глупая идея делать такое рекурсивно.
Аглая Шниц Искусственный Интеллект (135030) да, старая вредная привычка >_< идея, конечно, глупая, но с академической точки зрения представляет интерес как иллюстрация к теории вычислимости с её заменами циклов на рекурсии
Напишите рекурсивную функцию которая раскладывает число на простые сомножители
Дорогие девчонки! Поздравляем вас с праздником 8 Марта!
Нравится ресурс?
- FAQ по С++
- Онлайн справочник по STL (перевод)
- Онлайн компилятор (С++ и много других языков)
- Онлайн компилятор (широкий выбор версий компиляторов С++)
- Онлайн дизассеблер для x86, ARM/ARM64, PowerPC
- Онлайн дизассеблер с широким выбором настроек
- Онлайн IEEE 754 Converter
- Онлайн тестирование регулярных выражений
Модераторы: Qraizer, Hsilgos
‘> Простые множители через рекурсию , рекурсия
- Подписаться на тему
- Сообщить другу
- Скачать/распечатать тему
Сообщ. #1 , 03.11.10, 20:16
Unregistered
Здравствуйте. Есть вот такое задание:
Дано натуральное число. Разложите его на простые множители. Написать рекурсивную функцию.
Сделал без рекурсии, с рекурсией уже долго ломаю голову но не получается, подскажите пожалуйста
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) <
int num = Convert::ToInt32(textBox1->Text), simple[100] = <1,2>, temp = 2;
bool flag = false;
MessageBox::Show(«Вы ввели не натуральное число»,»Внимание!»);
label2->Text = «»;
for (int i = 1; i <= num; i++)<
flag = false;
for (int j = (i — 1); j > 1; j—)<
if (i % j == 0)
flag = true;
if (j == 2 && !flag)
simple[temp] = i;
//label2->Text = label2->Text + » » + Convert::ToString(simple[temp]);
Recur(temp, num, simple);
int Recur( int temp, int num, int simple[100] )
for (int i = 1; i < temp; i++)
if (num % simple[i] == 0)<
label2->Text = label2->Text + » » + Convert::ToString(simple[i]);
num /= simple[i];
Сообщ. #2 , 03.11.10, 21:51
Рейтинг (т): 22
MessageBox::Show(«Внимание!», «Вы не натурал!» );
Разложить число на простые множители
Да и для while никакого условия не нужно, т.е. просто while true (ну или do , если такое есть в питоне). Иначе этот код на обычную тройку ничего не выведет.
30 мар 2017 в 9:32
5 ответов 5
Сортировка: Сброс на вариант по умолчанию
Одна из реализаций(взято с OEIS#A238724):
def primfacs(n): i = 2 primfac = [] while i * i 1: primfac.append(n) return primfac Отслеживать
ответ дан 28 мар 2017 в 13:44
27.2k 2 2 золотых знака 45 45 серебряных знаков 76 76 бронзовых знаков
29 мар 2017 в 3:38
В коде есть два существенных момента, из-за которых он ищет все делители вместо факторизации. Добавлю ещё одно изменение ради оптимизации и получится такой код:
import math number=int(input()) for i in range(2, int(math.sqrt(number)) + 1): # обычно делитель не будет больше корня while (number % i == 0): # while, а не if print(i) number //= i # убираем множитель из числа if (number != 1): # но один делитель может быть больше корня print (number) PS: Но вообще вариант с циклом из соседнего ответа лучше.
Отслеживать
ответ дан 31 мар 2017 в 11:25
123k 24 24 золотых знака 128 128 серебряных знаков 307 307 бронзовых знаков
«случай, что само число было простым» В number всегда будет последний простой делитель(кроме случая, когда на входе была единица).
31 мар 2017 в 11:49
@vp_arth, нет, во всех остальных случаях там 1. Мы же делим на каждый простой делитель до корня, пока они не кончатся.
31 мар 2017 в 11:50
ок, не всегда, иногда там 1. Однако, 51 => range(2, 8) => 3, 17!
31 мар 2017 в 12:00
@vp_arth, да, понял. Поменял комментарий. Если хочешь, можешь ещё сам поправить что-нибудь. Но код-то верный во втором варианте.
31 мар 2017 в 14:02
Посмотрите, например, как сделано здесь. Существуют более сложные и эффективные методы. А также обратите внимание на решето Эратосфена (тут). Если вы хотите получать факторизацию не для одного числа, а для большого набора числел, то выгоднее использовать перебор по простым. Об этом я расскажу чуть ниже.
Кроме того, я думаю, что Вы имели ввиду, что хотите разложить число на простые множители, ведь так? Я сужу по Вашему замечанию, насчёт правильного ответа:
7 = [63, 3, 21, 3, 7] А должно: 63 = 3 * 3 * 7 if n > 1: factors.append(n) else: break говорят о том, что Вы пытаетесь искать все делители.
В таком случае, нужно писать правильно заголовок вопроса, чтобы не смущать людей.
Насчёт Вашего решения. Я не понимаю, зачем Вы добавляете в итоговый список текущий делитель. Это неверно, так как добавлять в итоговый список следует лишь простые числа, а текущий делитель, очевидно, не простой. Так что строки:
if n > 1: factors.append(n) else: break Для того, чтобы получить все делители, вам нужно слегка модифицировать Ваш алгоритм:
#!/usr/bin/env python3 n = int(input("Integer: ")) factors = [] d = 2 m = n # Запомним исходное число while d * d = <>' .format(m, factors)) # Выводим исходное число и все простые множители. Теперь о предподсчёте с простыми числами. Легко понять, что коль скоро мы знаем все простые числа, то выгоднее не перебирать те элементы, которые являются сами по себе произведением простых. Т.е. будем перебирать только числа:
2, 3, 5, 7, 11, 13 . 4, 6, 8, 9, 10, 12 . оставим в покое, так как они являются произведением простых. Для этого, с помощью решета Эратосфена вычислим заранее все простые до некоторого предела ( 2 ^ 64 ). После этого полученное со входной строки число для факторизации будем раскладывать по простым следующим образом. Делим число n до тех пор, пока оно делится на i -ое простое. Все простые будем записывать в factors . Как только число перестаёт делиться на i -ое, берём i+1 -ое число. И так до тех пор, пока n != 1 .
Спешу заметить, что хранение простых чисел, разумеется, является затратным. НО! Для большинства задач очень подходит, так как не требуется вычислять простые числа свыше 100000000 . Оперативная память современных ПК более чем позволяет хранить 1ГБ и более данных. Простых чисел оказывается не слишком много. Согласно одной довольно известной теореме о простых числах, их оказывается порядка n/ln(n) при возрастании n . Это означает, что для 100000000 их будет примерно 5,3 млн , что является вполне себе допустимым. Более того, даже 1 млрд. чисел выдержит среднестатистический ПК, так как простых числе окажется не более 50 млн . А значит, для памяти это будет 50 млн . 4-байтовых чиселок, т.е. 200000000 байт . В мегабайтах это всего лишь 200 . Так что большой проблемы в хранении нет.