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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
#1

Алгоритм проверки числа на "совершенность" - C++

09.07.2013, 17:31. Просмотров 2225. Ответов 42
Метки нет (Все метки)

Приветствую всех!

Прошу помочь со следующей задачей:

"Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением себя самого. Число 6 – совершенное, так как 6 = 1+2+3. Число 8 – не совершенное, так как 8 ≠ 1+2+4.Дано натуральное число n. Получить все совершенные числа, меньшие n."

Задачу я решил (код ниже), но работает программа слишком медленно. Пожалуйста помогите оптимизировать код, нужно чтобы программа требовала, как можно меньше памяти и работала быстрее.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
using namespace std;
 
bool perfect(int x)
{
   int sum=0;
   for (int i=1; i<x; i++)
      if (x%i==0) sum+=i;
   if (x==sum) return 1;
   return 0;
}
 
int main()
{
   int x;
   cin >> x;
   for (int i=1; i<=x; i++)
      if (perfect(i)) cout << i << endl;
   return 0;
}
Ссылки на литературу по сабжу приветствуются.

Заранее всем благодарен))
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.07.2013, 17:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм проверки числа на "совершенность" (C++):

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года &quot;весна&quot;, &quot;лето&quot;, &quot;осень&quot;, &quot;зима&quot; определить погоду &quot;тепло&quot;, &quot;жарко&quot;, &quot;холодно&quot;, &quot;очень холодно&quot;. Я так...

Наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные "длина" и "угол" - C++
кто то напишите пожалуйста, вот программа: наследуемым классом для комплексного числа объявить класс &quot;радиус-вектор&quot;, имеющий данные...

Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей"; - C++
Помогите пожалуйста с задачей. Могу сделать ее просто, но надо через ООП и у меня не получается. Дано натуральное число N (N&lt;20),...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

42
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 19:55 #16
Thinker, ваш алгоритм работает за n^0.5, если я не ошибаюсь. нотация снизилась до n^(3/2). если я введу число с 20 нулями, ждать вы будете до второго пришествия
0
ValeryS
Модератор
6794 / 5202 / 499
Регистрация: 14.02.2011
Сообщений: 17,453
09.07.2013, 19:58 #17
тут можно добавить еще одно условие и изменить направление
C++
1
2
3
4
5
for (int i= x/2; i>0; i--)
{
  if (x%i==0) sum+=i;
 if (sum>x) break;
}
при больших количествах делителей цикл будет работать не до конца
например для 100
50+25+20+10 вылетит
можно до корня ну тогда цикл будет сложный
что то типа
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sum=1;
int n=sqrt(x);
for(int i=2;i<=n;i++)
{
if(x%i==0)
 {
  if(i==n)
    sum+=i;
  else
   {
      sum+=i;
      sum+=x/i;
   }
 }

}
0
Thinker
Эксперт С++
4230 / 2204 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:59 #18
Kukurudza, мы немного абстрагировались от совершенных чисел, речь о сумме делителей натурального числа. и Вы правильно поняли сложность алгоритма.

Но что касается совершенных чисел, то это понятно, что их по-другому проверяют
Получить совершенные числа
посты #3 и #4
0
Toshkarik
1148 / 865 / 51
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
09.07.2013, 20:02 #19
Thinker, так скорей всего Ваш код и будет быстрее, так как операция деления довольно дорогая.
0
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 20:04 #20
Toshkarik на самом деле на сегодняшний момент операция деления такая же по стоимости как и умножение. как она реадизована я не в курсе в современных процессорах. я лично проверял на i5 процессоре.
0
Thinker
Эксперт С++
4230 / 2204 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 20:04 #21
Цитата Сообщение от Toshkarik Посмотреть сообщение
Thinker, так скорей всего Ваш код и будет быстрее, так как операция деления довольно дорогая.
Спасибо, что понимаете в том алгоритме по сути не используется свойство:
если a делитель n, то и n/a тоже делитель, там еще более крутые моменты (мультипликативные функции), поэтому быстро работает
P.S. а то бы не выставлял бы тот алгоритм. интересно было поработать с мульт.функциями, после чего пришла идея такого алгоритма.
0
ValeryS
Модератор
6794 / 5202 / 499
Регистрация: 14.02.2011
Сообщений: 17,453
09.07.2013, 20:18 #22
Цитата Сообщение от Kukurudza Посмотреть сообщение
Toshkarik на самом деле на сегодняшний момент операция деления такая же по стоимости как и умножение.
не совсем уверен i5 нет проверить не могу
но до него div достаточно дорогая операция была
Цитата Сообщение от Kukurudza Посмотреть сообщение
как она реадизована я не в курсе
очень часто деление заменяется на умножение и сдвиг
0
Toshkarik
1148 / 865 / 51
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
09.07.2013, 20:23 #23
Kukurudza, я что то разве говорил об умножении? Я сравнивал с битовыми операциями.
0
Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
10.07.2013, 09:36  [ТС] #24
ValeryS, спасибо за замечания)) Сразу как-то и не подумал над х/2.
Чуть-чуть причесал код:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
 
bool perfect(unsigned int x)
{
   unsigned int sum=0;
   for (int i=1; i<=x/2; i++)
      if (x%i==0) sum+=i;
   return x==sum;
}
 
int main()
{
   unsigned int x;
   std::cin >> x;
   for (unsigned int i=4; i<=x; i++)
      if (perfect(i)) std::cout << i << std::endl;
   return 0;
}

Kukurudza, благодарю за вики, появились кое какие мысли) Использование последовательности чисел Мерсенне способ весьма годный на практике, но когда речь идёт об алгоритмизации думаю не совсем уместен.

Цитата Сообщение от Kukurudza Посмотреть сообщение
реализованный алгоритм имеет нотацию O(n*n)
Это оценка скорости выполнения или количества операций алгоритма? Можно подробнее?

Thinker, Ваш алгоритм нахождения делителей числа действительно очень быстро работает. Еще не разобрался как он работает...

Вообщем по алгоритму проверки числа на совершенность пока идей больше нет, а вот как сократить количество итераций проверки самих чисел меньше заданного n (по условию) есть. Заинтересовало сл. св-во совершенных чисел в вики:
"Все чётные совершенные числа в двоичной записи содержат сначала p единиц, за которыми следует p—1 нулей (следствие из их общего представления)."

Таким образом можно было бы проверять все числа от 4 до n сначала на удовлетворение этому условию (операция, как я полагаю, менее затратная, если не ошибаюсь) и только проходящие по нему проверять на совершенность.
0
Thinker
Эксперт С++
4230 / 2204 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.07.2013, 09:39 #25
Цитата Сообщение от Naudiz Посмотреть сообщение
Thinker, Ваш алгоритм нахождения делителей числа действительно очень быстро работает. Еще не разобрался как он работает...
Спасибо, всякую фигню бы не стал выставлять на показ Возможно, оптимизирую его как-нибудь.
0
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
10.07.2013, 10:02 #26
Цитата Сообщение от Naudiz Посмотреть сообщение
Это оценка скорости выполнения или количества операций алгоритма? Можно подробнее?
ей богу, у меня иногда складывается мнение что только у меня гугл разбанен:
http://ru.wikipedia.org/wiki/%D0%9E-...86%D0%B8%D1%8F
а вообще это у вас академическая задача или какая-то практическая? решили нобеля получить поди?
0
Stereotip
2 / 2 / 0
Регистрация: 17.04.2012
Сообщений: 22
10.07.2013, 10:17 #27
если интересно разобраться с О( ) и с другими её друзьями - "Алгоритмы построения и анализ" авторы: Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн)
1
Thinker
Эксперт С++
4230 / 2204 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.07.2013, 12:31 #28
Naudiz,
Быстрый поиск совершенных чисел
0
Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
12.07.2013, 20:50  [ТС] #29
Thinker, благодарю, то что нужно. Можно вопрос по Вашему коду?

C++
1
const unsigned long long N = 5000000000000000000llu; //3я строка
Что значит "llu"?

Эта запись в дальнейшем фигурирует в выражениях в main
0
Thinker
Эксперт С++
4230 / 2204 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 20:53 #30
Цитата Сообщение от Naudiz Посмотреть сообщение

Что значит "llu"?

Эта запись в дальнейшем фигурирует в выражениях в main
везде llu замените на ull это константа типа unsigned long long
0
12.07.2013, 20:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2013, 20:53
Привет! Вот еще темы с ответами:

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...

Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя переменых значений - C++
Здравствуйте, помогите написать две программы. 1) Дано натуральное число. Найти сумму последних &quot;n&quot; цифр &quot;n&quot; числа, не применяя...

Нужно сделать так, чтобы при вводе числа, выводило "рублей" или "рубль" - C++
Начал решать задачу и засох на средине, не выходить формулу написать,если не сложно,подскажите) с с++ знаю пока что if,else и swith) //...

2 Программы. На "целые числа и системы счисления" и на "метод деления отрезка пополам" - C++
1)Дано натурально число n. Среди чисел 1, ... ,n найти все такие, запись которых совпадает с последними цифрами их квадрата ( как,...


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

Или воспользуйтесь поиском по форуму:
30
Ответ Создать тему
Опции темы

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