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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Массивы и перестановка http://www.cyberforum.ru/cpp-beginners/thread920370.html
Помогите пожалуйста с задачей. Дано 2 массива, заполненных случайными числами, размером от 10-20 (рандом). Найти в первом массиве максимальное число и все числа, находящиеся до него записать в 3ий массив. Во втором массиве найти максимальное число и все числа после него записать в 3ий массив (т.е. переместить к тому что получили из 1ого массива). Заранее спасибо!
C++ Создайте класс на основе данной программы Создайте класс на основе данной программы #include <iostream> using namespace std; int main ( ) { const int n=10; int* ap; for(int j=0;j<n;j++) *(ap+j)=new int; http://www.cyberforum.ru/cpp-beginners/thread920338.html
Как определить в каком файле .lib реализована функция? C++
Есть один проект. В нем файл .h с прототипами функций и множество .lib-ов, с их реализациями. Я данные функции пытаюсь использовать в другом проекте, но при попытки построить проект VS2010 выдает ошибку "error LNK2019: ссылка на неразрешенный внешний символ av_log_set_level в функции..." Так вот, вопрос, есть ли какоето средство(желательно в MS VS 2010) для определения, в каком .lib лежит...
Как получить int представление char (русские символ cp1251)? C++
Как получить int представление char (русские символ cp1251)?
C++ решении задачи (по Липпману) http://www.cyberforum.ru/cpp-beginners/thread920326.html
Занимаюсь по книги Стенли Липпмана "C++ Primer" (Язык программирования С++. Вводный курс). Возникла проблема с решением задачи.Текст - прочитайте некоторый текст, сохраняя каждое введенное слово как отдельный элемент вектора. Преобразуйте символы каждого слова в прописные. Свою ошибку понимаю, но не знаю, как решить. #include <iostream> #include <vector> #include <string> #include...
C++ Кошки Здравствуйте! Как в этом коде сделать так чтобы если кошке менее 2 лет, то цена кошки = 0$; Заранее спасибо!!! И еще как можно это часть кода: оптимизировать. Cat Mumu(140); cout<<"Cat's "<<Mumu.Roj()<<" years old."<<endl; cout<<"Cats price is "<<Mumu.Cena()<<"$"<<endl; cout<<"Cat's "<<Mumu.Roj()<<" years old."<<endl; ... подробнее

Показать сообщение отдельно
Naudiz
14 / 12 / 1
Регистрация: 04.11.2011
Сообщений: 137
10.07.2013, 09:36  [ТС]     Алгоритм проверки числа на "совершенность"
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 сначала на удовлетворение этому условию (операция, как я полагаю, менее затратная, если не ошибаюсь) и только проходящие по нему проверять на совершенность.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru