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

Быстрый поиск супернатуральных чисел - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
natashka69
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 15
26.09.2013, 16:55     Быстрый поиск супернатуральных чисел #1
Натуральное число будем называть супернатуральным, если в своем десятичном виде оно не содержит единиц, а произведение всех его цифр равно n. Для заданного n выясните, сколько существует супернатуральных чисел.
Технические условия
Входные данные:
Содержит одно целое число n, не превосходящее 2×109.
Выходные данные:
Вывести количество супернатуральных чисел по модулю 101.
Информация о задаче:
Лимит времени: 1 секунда
Лимит памяти: 256 Mб
Пример входных данных 6
Пример выходных данных 3
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Algoritmer
 Аватар для Algoritmer
155 / 95 / 13
Регистрация: 07.03.2013
Сообщений: 477
Записей в блоге: 1
01.10.2013, 12:52     Быстрый поиск супернатуральных чисел #21
Цитата Сообщение от HedgehogLu Посмотреть сообщение
да в программе ya_noob, все очень просто
там рекурсивно находится число комбинаций которым может быть построено число, при этом, чтобы постоянно не спускаться вниз создается индексный массив в котором уже хранится полученное число комбинаций. За счет того, что порядок цифр определяется делением повторов не возникает
Жесть. Хожу в отладчике битый час, никак не раскурю этот код. Можете записать формулу в виде:
calc(n)=f(calc(), n, m) ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2013, 15:25     Быстрый поиск супернатуральных чисел
Еще ссылки по теме:

Быстрый поиск C++
Быстрый подсчет чисел, подходящих под условие C++
C++ Быстрый поиск минимального числа

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

Или воспользуйтесь поиском по форуму:
HedgehogLu
 Аватар для HedgehogLu
146 / 67 / 1
Регистрация: 04.09.2013
Сообщений: 250
01.10.2013, 15:25     Быстрый поиск супернатуральных чисел #22
ya_noob, ну я и дурик. Я забыл поменять возвращаемый тип данных у самой функции калк потому и -105 было

Algoritmer, блин формулу не напишу т.к даже не знаю как это представить, но
изначально получается так.
только дойдя до 1 функция калк вернет 1 в противном случае это будет 0
таким образом
соответственно сalc(n) всегда идет в глубь по рекурсии до 1, переходя глубже только при условии что остаток от деления будет нулевым.
таким образом суммируя количество спусков до 1 и подсчитывается количество комбинаций представления числа разными цифрами.
Для того, чтобы рекурсия постоянно не повторялось. для вычисленных ранее чисел сохраняется результат вот и все
Yandex
Объявления
01.10.2013, 15:25     Быстрый поиск супернатуральных чисел
Ответ Создать тему
Опции темы

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