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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
natashka69
0 / 0 / 0
Регистрация: 26.09.2013
Сообщений: 15
#1

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

26.09.2013, 16:55. Просмотров 1250. Ответов 21
Метки нет (Все метки)

Натуральное число будем называть супернатуральным, если в своем десятичном виде оно не содержит единиц, а произведение всех его цифр равно n. Для заданного n выясните, сколько существует супернатуральных чисел.
Технические условия
Входные данные:
Содержит одно целое число n, не превосходящее 2×109.
Выходные данные:
Вывести количество супернатуральных чисел по модулю 101.
Информация о задаче:
Лимит времени: 1 секунда
Лимит памяти: 256 Mб
Пример входных данных 6
Пример выходных данных 3
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.09.2013, 16:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрый поиск супернатуральных чисел (C++):

Быстрый поиск совершенных чисел - C++
Чтобы легко можно было отсылать вопрошающих по этому вопросу, создаю новую тему. Напомню, что Доказано, что все четные совершенные...

Быстрый поиск - C++
Здравствуйте. Нужно выполнить поиск i-го вхождения заданного элемента в исходном наборе чисел. Написал такой поиск, но работает...

Быстрый поиск в мапе - C++
Есть мапа вида : std::map<size_t, std::string> Нужно найти элемент меньший или равный элементу из rbf с конца мапы. Есть ли быстрый...

Быстрый поиск элемента - C++
Добрый день всем! Такой вопрос - есть у меня строка из 64-х чаров. Мне приходит новый чар и нужно найти какой индекс у такого же чара в...

Быстрый поиск в векторе из pair - C++
Пытаюсь сделать вектор: vector< pair<string, string> > myVect; По идее, проще воспользоваться чем-то вроде map или unordered_map,...

Быстрый поиск минимального числа - C++
подскажите быстрый алгоритм поиска второго минимального числа в массиве?

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
30.09.2013, 20:54 #16
ya_noob, а ваш походу не особо точен если убрать модуль 101 хотя еще не пойму почему
0
Algoritmer
155 / 95 / 13
Регистрация: 07.03.2013
Сообщений: 480
Записей в блоге: 1
01.10.2013, 10:09 #17
ya_noob, объясните, пожалуйста, строки 23 и 27
0
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
01.10.2013, 10:25 #18
да в программе ya_noob, все очень просто
там рекурсивно находится число комбинаций которым может быть построено число, при этом, чтобы постоянно не спускаться вниз создается индексный массив в котором уже хранится полученное число комбинаций. За счет того, что порядок цифр определяется делением повторов не возникает.

Algoritmer
Цитата Сообщение от ya_noob Посмотреть сообщение
if ( m.find( x ) != m.end() ) res += m[ x ];
если в индексированном массиве уже есть результат для данного числа то вернуть добавить уже ранее высчитанный результат
Цитата Сообщение от ya_noob Посмотреть сообщение
m.insert( mypair( n, res % 101 ) );
добавляем в индексный массив результат для числа n[/quote]

Добавлено через 1 минуту
но блин рекурсия штука порой опасная (т.к. размер стека у программы значительно меньше чем пользовательская память. и порой на не очень больших рекурсиях можно споткнутся об ошибку переполнения стека)
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.10.2013, 11:36 #19
Цитата Сообщение от HedgehogLu Посмотреть сообщение
а ваш походу не особо точен если убрать модуль 101 хотя еще не пойму почему
Ести убрать модуль 101, то задача вообще будет работать неправильно. Т.к. результат хранится в переменной типа char, то очень скоро произойдет переполнение и будет считаться всякая ерунда. Да и вообще зачем убирать модуль, ведь в задаче ясно сказано про него.

Цитата Сообщение от HedgehogLu Посмотреть сообщение
но блин рекурсия штука порой опасная (т.к. размер стека у программы значительно меньше чем пользовательская память. и порой на не очень больших рекурсиях можно споткнутся об ошибку переполнения стека)
но не в данной задаче. максимальное количество цифр в числе <= 30 (худший случай: 2*2*2*2*2... (30 штук)), следовательно глубина рекурсии всего 30 (учитывая первый вызов функции). а это пару килобайт.
0
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
01.10.2013, 11:54 #20
cya_noob, странно то, что даже если я сделаю результат типа дабл и произведу все необходимые изменения типов для других переменных у меня все одно программа почему-то возвращает результат -105 если уберу модуль 101

Не по теме:

по поводу рекурсии я просто высказал свое мнение. просто как напоминание,чтобы люди не злоупотребляли рекурсией покупаясь на ее простоту.

0
Algoritmer
155 / 95 / 13
Регистрация: 07.03.2013
Сообщений: 480
Записей в блоге: 1
01.10.2013, 12:52 #21
Цитата Сообщение от HedgehogLu Посмотреть сообщение
да в программе ya_noob, все очень просто
там рекурсивно находится число комбинаций которым может быть построено число, при этом, чтобы постоянно не спускаться вниз создается индексный массив в котором уже хранится полученное число комбинаций. За счет того, что порядок цифр определяется делением повторов не возникает
Жесть. Хожу в отладчике битый час, никак не раскурю этот код. Можете записать формулу в виде:
calc(n)=f(calc(), n, m) ?
0
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
01.10.2013, 15:25 #22
ya_noob, ну я и дурик. Я забыл поменять возвращаемый тип данных у самой функции калк потому и -105 было

Algoritmer, блин формулу не напишу т.к даже не знаю как это представить, но
изначально получается так.
только дойдя до 1 функция калк вернет 1 в противном случае это будет 0
таким образом
соответственно сalc(n) всегда идет в глубь по рекурсии до 1, переходя глубже только при условии что остаток от деления будет нулевым.
таким образом суммируя количество спусков до 1 и подсчитывается количество комбинаций представления числа разными цифрами.
Для того, чтобы рекурсия постоянно не повторялось. для вычисленных ранее чисел сохраняется результат вот и все
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2013, 15:25
Привет! Вот еще темы с ответами:

Быстрый поиск по полям в коллекции - C++
Есть коллекция объектов класса с разными полями. Нужно организовать быстрый поиск первого элемента (может потом множества элементов) по...

Быстрый поиск ip адреса в текстовом файле - C++
Нужно найти конкретный ip-адрес в текстовом файле (он может попасться несколько раз). На каждой строчке по 1 ip-адресу. Всего строк ~300...

Быстрый поиск наиболее близких вершин графа - C++
Всем привет, у меня имеется некая задача и её суть состоит в том, что мне нужно найти расстояние между двумя наиболее близкими вершинами...

Подскажите быстрый поиск количества интервалов в отрезке - C++
Есть массив H Есть отрезок x+dx. Задача найти количество интервалов на которое делится отрезок x+dx массивом H. Наверняка с такой...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
01.10.2013, 15:25
Ответ Создать тему
Опции темы

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