Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
#1

Найти количество факторизаций числа - C++

05.04.2011, 22:50. Просмотров 1031. Ответов 12
Метки нет (Все метки)

Мучают меня днем ночью задача:

Найти количество факторизаций числа. Если кто не знает
Факториза́цией натурального числа называется его разложение в произведение на натуральные множителей больше одного.
Например:
число 30
2*3*5
6*5
10*3
15*2
порядок роли не играет.
(диапазон 2 000 000)

Пытался свести к комбинаторике, не получается.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2011, 22:50     Найти количество факторизаций числа
Посмотрите здесь:

C++ Определить количество цифр числа,найти предпоследнюю цифру
Найти количество делителей натурального числа, больших K C++
Для каждого числа последовательности найти количество цифр 5 C++
Найти количество четных цифр заданного натурального числа C++
Найти количество различных цифр данного натурального числа C++
Найти количество элементов массива меньших заданного числа C++
C++ Найти количество участков на которых числа возрастают и вывести их
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Subgrando
40 / 40 / 3
Регистрация: 28.01.2011
Сообщений: 175
05.04.2011, 22:56     Найти количество факторизаций числа #2
Тоже интересно узнать решение.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2011, 07:37     Найти количество факторизаций числа #3
Цитата Сообщение от Overmind024 Посмотреть сообщение
Найти количество факторизаций числа.
Именно количество факторизаций или просто одну любую?
Если все, то это только перебором всех вариантов.
Если одну, то перебором до первого разложения.)

Вообще, насколько мне известно, проблема факторизации больших чисел пока не имеет решения.)

2000000 число маленькое, поэтому тупо перебором.
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
06.04.2011, 09:09     Найти количество факторизаций числа #4
Цитата Сообщение от Deviaphan Посмотреть сообщение
Вообще, насколько мне известно, проблема факторизации больших чисел пока не имеет решения
Слышу звон да не знаю где он. Перебрать простые делители люди пока не додумались чтоли?
На данный момент всего лишь неизвестно, имеет ли задача полиномиальное решение.

2000000 действительно маленькое число - разложение на простые множители находим перебором.
А вот дальше простым перебором нельзя - долго будет. Комбинаторика, думать надо.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2011, 09:44     Найти количество факторизаций числа #5
Цитата Сообщение от Хохол Посмотреть сообщение
Слышу звон да не знаю где он.
Да, именно так. Только краем уха слышал.)
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
06.04.2011, 09:48     Найти количество факторизаций числа #6
Хотя фиг знает, тут простых делителей-то не более 20 штук. Может и простым перебором нормально написать получится.
МаксимМВ
C/C++
90 / 90 / 5
Регистрация: 01.07.2010
Сообщений: 281
06.04.2011, 10:22     Найти количество факторизаций числа #7
ну решу попробую
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
06.04.2011, 13:52     Найти количество факторизаций числа #8
улыбнули =) без обид.
Найти количество факторизаций числа.
я Вам и без компьютера ответ скажу - одна.
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
06.04.2011, 18:40     Найти количество факторизаций числа #9
Vladimir., а вот и нет, в условии было специально дано локальное определение:

Цитата Сообщение от Overmind024 Посмотреть сообщение
Факториза́цией натурального числа называется его разложение в произведение на натуральные множителей больше одного.
Их, понятно, может быть много.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
06.04.2011, 19:26     Найти количество факторизаций числа #10
Факторизацией натурального числа называется его разложение в произведение простых чисел. Она будет уникальной для каждого натурального числа с точностью до порядка следования сомножителей.
Если это не так - пруфлинк пожалуйста.
=========================

как найти то, что хочет посчитать топикстартер:
  1. разложить число http://www.cyberforum.ru/cgi-bin/latex.cgi?N на простые сомножители (пусть n штук, множество простых сомножителей http://www.cyberforum.ru/cgi-bin/latex.cgi?X)
  2. перебрать все наборы из k элементов множества http://www.cyberforum.ru/cgi-bin/latex.cgi?X (иначе http://www.cyberforum.ru/cgi-bin/latex.cgi? C^k_n ) для всех возможных k (произведение элементов входящих в сочетание будет натуральным делителем числа http://www.cyberforum.ru/cgi-bin/latex.cgi?N.)
  3. для каждого такого набора повторить шаг 2 на подмножестве http://www.cyberforum.ru/cgi-bin/latex.cgi?X' простых делителей не вошедших в в данный набор.
silent_1991
Эксперт С++
4952 / 3028 / 149
Регистрация: 11.11.2009
Сообщений: 7,026
Завершенные тесты: 1
06.04.2011, 19:32     Найти количество факторизаций числа #11
Vladimir., да, факторизация - разложение числа на простые сомножители. Но ТСа интересует разложение числа на сомножители вообще, не обязательно на простые, и это разложение он тоже назвал (ошибочно) факторизацией. И вариантов такой факторизации может быть несколько.
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
06.04.2011, 21:49  [ТС]     Найти количество факторизаций числа #12
silent_1991, полностью прав. но назвал не я а тот кто составлял олимпиадное задание.

Добавлено через 1 минуту
Цитата Сообщение от Deviaphan Посмотреть сообщение
Если все, то это только перебором всех вариантов.
не вариант так есть ограничение по времени.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2011, 22:14     Найти количество факторизаций числа
Еще ссылки по теме:

Найти количество положительных делителей натурального числа n C++
Найти количество и сумму цифр заданного натурального числа C++
В массиве найти количество элементов, меньших заданного числа C++
C++ Требуется найти количество делителей n-значного числа (n > 20)
Найти количество делителей натурального числа N. больших К C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
06.04.2011, 22:14     Найти количество факторизаций числа #13
"господа, я свалял большого дурака" (с).
========
Предложеный мной алгоритм ошибочен так как даёт не количество разложений N на натуральные сомножители, а лишь ограничение сверху. Так для числа 8 алгоритм пройдет по разложениям 8 = 2*2*2 = 2*4 = 4*2 и вернёт 3. Хотя очевидно, что второе и третье разложения идентичны и правильный ответ 2.
Yandex
Объявления
06.04.2011, 22:14     Найти количество факторизаций числа
Ответ Создать тему
Опции темы

Текущее время: 02:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru