Форум программистов, компьютерный форум 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++ Через ООП: Дать для числа наименование: "рубль", "рубля", "рублей";
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
jurok_85
226 / 209 / 70
Регистрация: 21.02.2013
Сообщений: 494
09.07.2013, 18:38     Алгоритм проверки числа на "совершенность" #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
 
void perfect();
 
using namespace std;
 
int main()
{
   perfect();
   
   return 0;
}
 
void perfect()
{
   int sum = 0;
   
   for(int number = 1; number <= 1000; number++)
   {
      for(int j = 1; j < number; j++)
      {
         if(number % j == 0)
            sum += j;
      }
      
      if(number == sum)
      {
         cout << "Chislo " << number << " sovershennoye!!!" << endl;
         cout << "Ego somnoshiteli: ";
         
         for(int i = 1; i < number; i++)
            if(number % i == 0)
               cout << i << "; ";
               
         cout << endl << endl;
      }
      
      sum = 0;
   }
}
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
09.07.2013, 18:54     Алгоритм проверки числа на "совершенность" #3
Цитата Сообщение от Naudiz Посмотреть сообщение
if (x==sum) return 1;
* *return 0;
вот это можешь заменить на
C++
1
return x==summ;
Цитата Сообщение от Naudiz Посмотреть сообщение
for (int i=1; i<x; i++)
* * * if (x%i==0) sum+=i;
количество итераций можешь уменьшить в два раза
больше чем x/2 делителей нет (ну кроме x, а он по условию не проходит)
C++
1
2
for (int i=1; i<=x/2; i++)
  if (x%i==0) sum+=i;
Добавлено через 3 минуты
Цитата Сообщение от Naudiz Посмотреть сообщение
for (int i=1; i<=x; i++)
* * * if (perfect(i)) cout << i << endl;
один два три можешь смело выбрасывать они простые значит не совершенные
начинай с 4
можешь еще добавить проверку на простоту, но вряд ли это ускорит выполнение
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
09.07.2013, 18:55     Алгоритм проверки числа на "совершенность" #4
Naudiz, для начала предложу считать до x/2, так как числа больше половины не могут быть делителями. Сумму можно сразу начинать с 1, а делители искать с 2.

ADD: Чуть опоздал.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 19:28     Алгоритм проверки числа на "совершенность" #5
господа, реализованный алгоритм имеет нотацию O(n*n). то что вы предлагаете сделает нотацию алгоритма O(n*n/2). это не выход. нужно алгоритм другой.

Добавлено через 5 минут
я бы предложил курнуть вики:
http://ru.wikipedia.org/wiki/Совершенное_число
решить в лоб может любой.
так же прочтите тему Определить, является ли заданное натуральное число совершенным сам не читал. но там что то про числа мерсенне - верный путь
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:35     Алгоритм проверки числа на "совершенность" #6
Цитата Сообщение от Toshkarik Посмотреть сообщение
для начала предложу считать до x/2
правильно, но еще лучше до корня из числа
Быстрое нахождение количества делителей натурального числа
посты #4 и #5
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
09.07.2013, 19:37     Алгоритм проверки числа на "совершенность" #7
Thinker, почему же до корня? Ищем ведь не простые числа. К примеру возьмем 100. Корень == 10, но как же 20, 25 и 50?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:38     Алгоритм проверки числа на "совершенность" #8
Цитата Сообщение от Toshkarik Посмотреть сообщение
Thinker, почему же до корня? Ищем ведь не простые числа. К примеру возьмем 100. Корень == 10, но как же 20, 25 и 50?
до 100. корень 10
на 2 делится, значит и на 100/2=50 тоже делится
на 4 делится, значит и на 100/4=25 тоже делится
на 5 делится, значит и на 100/5=20 тоже делится
betline
1 / 1 / 0
Регистрация: 27.06.2013
Сообщений: 26
09.07.2013, 19:40     Алгоритм проверки числа на "совершенность" #9
Цитата Сообщение от Kukurudza Посмотреть сообщение
господа, реализованный алгоритм имеет нотацию O(n*n). то что вы предлагаете сделает нотацию алгоритма O(n*n/2). это не выход. нужно алгоритм другой.

Добавлено через 5 минут
я бы предложил курнуть вики:
http://ru.wikipedia.org/wiki/Совершенное_число
решить в лоб может любой.
так же прочтите тему Определить, является ли заданное натуральное число совершенным сам не читал. но там что то про числа мерсенне - верный путь
Поддерживаю. Уже все давно решено. Вики и поиск - рулит.
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
09.07.2013, 19:41     Алгоритм проверки числа на "совершенность" #10
Цитата Сообщение от Thinker Посмотреть сообщение
правильно, но еще лучше до корня из числа
фиг вам
число 6
делители 1+2+3 =6
корень из числа 6 примерно 2,449
число 28
делители 1+2+4+7+14 =28
корень из числа 28 примерно 5.29
то что предложил это для простоты числа, если делителей меньше корня нет то и больше нет
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:42     Алгоритм проверки числа на "совершенность" #11
Цитата Сообщение от ValeryS Посмотреть сообщение
фиг вам
смотри пост #8
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
09.07.2013, 19:46     Алгоритм проверки числа на "совершенность" #12
Thinker, это то понятно. Но тогда придется делать лишнюю операцию умножения, скорость если и будет чуть больше, но не намного. У меня с самого начала была идея что вроде такой:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isPerfect( unsigned int x ) {
   unsigned int sum = 1;
   unsigned int border = x / 2;
   unsigned int tmp;
   
   for ( unsigned int i = 2; i < border; i++ ) {
      tmp = x / i;
      
      if ( tmp * i == x ) {
         sum += i;
         sum += tmp;
         border = tmp;
      }
   }
   
   return sum == x;
}
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
09.07.2013, 19:47     Алгоритм проверки числа на "совершенность" #13
посмотрел ничего не понял
Цитата Сообщение от Thinker Посмотреть сообщение
на 4 делится, значит и на 100/4=25 тоже делится
что делится ? 10?
и потом покажи как ты сумму делителей считать будешь?
да и 100 не совершенное число
1+2+4+5+10+20+25+50=117
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
09.07.2013, 19:48     Алгоритм проверки числа на "совершенность" #14
ValeryS, Вы не поняли смысла. 6 / 2 == 3. И 2 и 3 являются делителями.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 19:49     Алгоритм проверки числа на "совершенность" #15
Цитата Сообщение от ValeryS Посмотреть сообщение
и потом покажи как ты сумму делителей считать будешь?
Быстрое нахождение количества делителей натурального числа

Цитата Сообщение от Toshkarik Посмотреть сообщение
У меня с самого начала была идея что вроде такой:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isPerfect( unsigned int x ) {
   unsigned int sum = 1;
   unsigned int border = x / 2;
   unsigned int tmp;
   
   for ( unsigned int i = 2; i < border; i++ ) {
      tmp = x / i;
      
      if ( tmp * i == x ) {
         sum += i;
         sum += tmp;
         border = tmp;
      }
   }
   
   return sum == x;
}
попробуйте сравнить по скорости с
сумма делителей
здесь есть небольшие хитрости и делители только нечетные проверяются, степени двойки выделяются с помощью битовых операций и т.д.
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 19:55     Алгоритм проверки числа на "совершенность" #16
Thinker, ваш алгоритм работает за n^0.5, если я не ошибаюсь. нотация снизилась до n^(3/2). если я введу число с 20 нулями, ждать вы будете до второго пришествия
ValeryS
Модератор
6376 / 4842 / 442
Регистрация: 14.02.2011
Сообщений: 16,045
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;
   }
 }

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

Но что касается совершенных чисел, то это понятно, что их по-другому проверяют
Получить совершенные числа
посты #3 и #4
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
09.07.2013, 20:02     Алгоритм проверки числа на "совершенность" #19
Thinker, так скорей всего Ваш код и будет быстрее, так как операция деления довольно дорогая.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 20:04     Алгоритм проверки числа на "совершенность"
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
09.07.2013, 20:04     Алгоритм проверки числа на "совершенность" #20
Toshkarik на самом деле на сегодняшний момент операция деления такая же по стоимости как и умножение. как она реадизована я не в курсе в современных процессорах. я лично проверял на i5 процессоре.
Yandex
Объявления
09.07.2013, 20:04     Алгоритм проверки числа на "совершенность"
Ответ Создать тему
Опции темы

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