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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Naudiz
 Аватар для Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
09.07.2013, 17:31     Алгоритм проверки числа на "совершенность" #1
Приветствую всех!

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

"Натуральное число называется совершенным, если оно равно сумме всех своих делителей, за исключением себя самого. Число 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;
}
Ссылки на литературу по сабжу приветствуются.

Заранее всем благодарен))
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.07.2013, 17:31     Алгоритм проверки числа на "совершенность"
Посмотрите здесь:

Дано натуральное число. Найти сумму последних "n" цифр "n" числа, не применяя переменых значений C++
C++ 2 Программы. На "целые числа и системы счисления" и на "метод деления отрезка пополам"
C++ Наследуемым классом для комплексного числа объявить класс "радиус-вектор", имеющий данные "длина" и "угол"
Два числа, действительное "a" и натуральное "n" вводятся с клавиатуры C++
C++ Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей";
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 20:04     Алгоритм проверки числа на "совершенность" #21
Цитата Сообщение от Toshkarik Посмотреть сообщение
Thinker, так скорей всего Ваш код и будет быстрее, так как операция деления довольно дорогая.
Спасибо, что понимаете в том алгоритме по сути не используется свойство:
если a делитель n, то и n/a тоже делитель, там еще более крутые моменты (мультипликативные функции), поэтому быстро работает
P.S. а то бы не выставлял бы тот алгоритм. интересно было поработать с мульт.функциями, после чего пришла идея такого алгоритма.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6374 / 4840 / 441
Регистрация: 14.02.2011
Сообщений: 16,043
09.07.2013, 20:18     Алгоритм проверки числа на "совершенность" #22
Цитата Сообщение от Kukurudza Посмотреть сообщение
Toshkarik на самом деле на сегодняшний момент операция деления такая же по стоимости как и умножение.
не совсем уверен i5 нет проверить не могу
но до него div достаточно дорогая операция была
Цитата Сообщение от Kukurudza Посмотреть сообщение
как она реадизована я не в курсе
очень часто деление заменяется на умножение и сдвиг
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
09.07.2013, 20:23     Алгоритм проверки числа на "совершенность" #23
Kukurudza, я что то разве говорил об умножении? Я сравнивал с битовыми операциями.
Naudiz
 Аватар для 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 сначала на удовлетворение этому условию (операция, как я полагаю, менее затратная, если не ошибаюсь) и только проходящие по нему проверять на совершенность.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.07.2013, 09:39     Алгоритм проверки числа на "совершенность" #25
Цитата Сообщение от Naudiz Посмотреть сообщение
Thinker, Ваш алгоритм нахождения делителей числа действительно очень быстро работает. Еще не разобрался как он работает...
Спасибо, всякую фигню бы не стал выставлять на показ Возможно, оптимизирую его как-нибудь.
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
10.07.2013, 10:02     Алгоритм проверки числа на "совершенность" #26
Цитата Сообщение от Naudiz Посмотреть сообщение
Это оценка скорости выполнения или количества операций алгоритма? Можно подробнее?
ей богу, у меня иногда складывается мнение что только у меня гугл разбанен:
http://ru.wikipedia.org/wiki/%D0%9E-...86%D0%B8%D1%8F
а вообще это у вас академическая задача или какая-то практическая? решили нобеля получить поди?
Stereotip
 Аватар для Stereotip
2 / 2 / 0
Регистрация: 17.04.2012
Сообщений: 22
10.07.2013, 10:17     Алгоритм проверки числа на "совершенность" #27
если интересно разобраться с О( ) и с другими её друзьями - "Алгоритмы построения и анализ" авторы: Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн)
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.07.2013, 12:31     Алгоритм проверки числа на "совершенность" #28
Naudiz,
Быстрый поиск совершенных чисел
Naudiz
 Аватар для 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
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 20:53     Алгоритм проверки числа на "совершенность" #30
Цитата Сообщение от Naudiz Посмотреть сообщение

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

Эта запись в дальнейшем фигурирует в выражениях в main
везде llu замените на ull это константа типа unsigned long long
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 20:57     Алгоритм проверки числа на "совершенность" #31
Самый быстрый поиск совершенных чисел. Берем гугл. Сбиваем "OEIS совершенные числа". Находим эту страницу - http://oeis.org/A000396 Копируем все числа в константы (хоть в строковые). Организуем поиск по константам. Радуемся сложности O(1)
Naudiz
 Аватар для Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
12.07.2013, 21:03  [ТС]     Алгоритм проверки числа на "совершенность" #32
Thinker, не понял. В Вашем коде именно llu и он компилируется и работает))

Добавлено через 45 секунд
Dani, не смешно.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 21:04     Алгоритм проверки числа на "совершенность" #33
Цитата Сообщение от Naudiz Посмотреть сообщение
Thinker, не понял. В Вашем коде именно llu и он компилируется и работает))
тогда оставьте. ull нужно для работы с огромными типизированными константами, в противном случае число 50...0 просто урежется.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 21:07     Алгоритм проверки числа на "совершенность" #34
Цитата Сообщение от Naudiz Посмотреть сообщение
Dani, не смешно.
Никто шутить и не собирался. Работает быстро и правильно.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <string>
#include <algorithm>
 
int main()
{
    const std::string arr[] = {"6","28","496","8128","33550336","8589869056","137438691328","2305843008139952128","2658455991569831744654692615953842176",
        "191561942608236107294793378084303638130997321548169216"}; //совершенные числа
    const int len = 10; //количество совершенных чисел
    std::string inp_number;
    std::cin >> inp_number;
    std::cout << ( std::find(arr, arr+len, inp_number) != arr+len ? "It is perfect number" : "It is not perfect number") << std::endl;
    return 0;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 21:12     Алгоритм проверки числа на "совершенность" #35
Dani, программа дает иллюзию, что что ты сам их находишь
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 21:13     Алгоритм проверки числа на "совершенность" #36
Thinker, Зато 10 чисел найдет В отличии от других программ.
Naudiz
 Аватар для Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
12.07.2013, 21:15  [ТС]     Алгоритм проверки числа на "совершенность" #37
Dani, речь идёт именно об "алгоритме проверки числа на совершенность", а не о выводе совершенных чисел на экран.

Thinker, а что происходит в 57 строке? Заранее извиняюсь, мне еще не по зубам такой код(
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 21:16     Алгоритм проверки числа на "совершенность" #38
Naudiz, здесь и проверяется число на совершенность, как ты мог заметить.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.07.2013, 21:19     Алгоритм проверки числа на "совершенность" #39
Dani, программа дает иллюзию, что если вдруг ОЗУ позволит хранить очень большие числа, то с ее помощью можно найти еще несколько дополнительных чисел, не вошедших в ТОП10

Добавлено через 2 минуты
Цитата Сообщение от Naudiz Посмотреть сообщение
Thinker, а что происходит в 57 строке?
это просто. с помощью побитовых операций вычисляем значение
http://www.cyberforum.ru/cgi-bin/latex.cgi?2^{i-1}(2^i-1)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2013, 21:23     Алгоритм проверки числа на "совершенность"
Еще ссылки по теме:

C++ Разработать класс "Массив больших чисел", который состоит из объектов класса "Большие целые числа". Найти сумму элементов массива.
C++ В массиве структур студент с полями "ИМЯ" "ВОЗРАСТ" "УСПЕВАЕМОСТЬ" выполнить сортировку по успеваемости по возрастанию
Нужно сделать так, чтобы при вводе числа, выводило "рублей" или "рубль" C++

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

Или воспользуйтесь поиском по форуму:
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
12.07.2013, 21:23     Алгоритм проверки числа на "совершенность" #40
Цитата Сообщение от Thinker Посмотреть сообщение
программа дает иллюзию
но она ведь правильно проверяет число на совершенность. что и требовалось
Цитата Сообщение от Naudiz Посмотреть сообщение
нужно чтобы программа требовала, как можно меньше памяти и работала быстрее.
Что ТС просил - все условия выполняются.
Если нужно научиться находить совершенные числа или в учебных целях - то с твоим кодом никто не конкурирует, но пусть большие числа считает, например, этот сайт http://oddperfect.org/
Да и BigInt юзать как-то неохота в связи с затратами и повышением сложности кода.
Yandex
Объявления
12.07.2013, 21:23     Алгоритм проверки числа на "совершенность"
Ответ Создать тему
Опции темы

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