|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.09.2010, 07:53 | #1 |
Пользователь
Регистрация: 17.06.2009
Сообщений: 10
|
проблема с задачей
Есть формула которую надо посчитать для числА N, при условии, что N не больше чем 10 в 12 степени. формула следующая - RESULT=n div 1+n div 2 + n div 3 +... n div n.
Сначала стал писать через перебор, но на больших числах программа тратит до 3-4 минут, чтобы посчитать. Затем отбросив первую идею начал писать рекурсией. Времени уходить стало значительно меньше, но в итоге я получил ошибку Stack Overflow и понял что тоже не вариант. Подскажите пожалуйста, каким ещё путем можно решить такую задачу? |
19.09.2010, 09:16 | #2 |
Форумчанин
Регистрация: 08.09.2010
Сообщений: 880
|
Прежде всего уменьшить количество итераций в два раза:
N2 = N div 2 В результате формула примет следующий вид: RESULT=(n div 1+n div 2 + n div 3 +... n div N2) + N2. При больших числах N, когда стек переполняется можно разделить N2 на несколько частей: N3 = N2 div 10 (10 для примера). Рекурсию применить к каждой части отдельно. Результаты рекурсий сложить. Плюс к общему результату N2. |
19.09.2010, 09:58 | #3 |
Пользователь
Регистрация: 17.06.2009
Сообщений: 10
|
большое спасибо, сейчас попробую
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
проблема с задачей | sasha1993 | Помощь студентам | 6 | 21.12.2009 01:04 |
Проблема с задачей | bol2909 | Общие вопросы C/C++ | 2 | 06.12.2009 18:18 |
Проблема с задачей в c# | OnlySergio | Помощь студентам | 4 | 25.11.2009 10:47 |
Проблема с задачей по С++ | TheWanderer | Общие вопросы C/C++ | 4 | 02.10.2008 00:21 |