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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.74
paRadoX-2
0 / 0 / 0
Регистрация: 24.10.2010
Сообщений: 18
#1

Определить, является ли заданное натуральное число совершенным - C++

29.05.2011, 12:17. Просмотров 3728. Ответов 17
Метки нет (Все метки)

Определить, является ли заданное натуральное число совершенным, т.е. равным сумме всех своих (положительных) делителей, кроме самого этого числа (например, совершенное число 6=1+2+3).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
int main()
{
int s=0,i=0,x;
scanf("&i",x);
do
{
    ++i;
    if(x % i==0)s+=i;
    printf("\n%i",s);
    }
    while(i!=x);
    if(x==s)printf("\nDA"); else printf("\nHET");
getch();
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2011, 12:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Определить, является ли заданное натуральное число совершенным (C++):

Определить, является ли заданное натуральное число совершенным - C++
Помогите пожалуйста с задачей Вот условие: Определить, является ли заданное натуральное число совершенным, т.е. равным сумме всех...

Определить является ли заданное натуральное число совершенным - C++
1) Составьте программу проверяющую,является ли заданное натуральное число совершенным, т. е. равным сумме своих положительных делителей ,...

Проверить, является ли заданное натуральное число совершенным - C++
#include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int main(); { setlocale (LC_ALL,&quot;Russian&quot;); int n; int sum=0; ...

Проверить, является ли заданное натуральное число совершенным - C++
#include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int main(); { setlocale (LC_ALL,&quot;Russian&quot;); cout « &quot; Задача №\n&quot;; ...

Определить, является ли заданное число совершенным - C++
По заданному натуральному число 2&lt;=N&lt;=10^9 требуется определить, является ли оно совершенным.(Число называется совершенным, если оно равно...

Ввести натуральное число N. Определить, является ли оно совершенным - C++
Здравствуйте. Помогите пожалуйста с лабораторной... В 1. Ввести натуральное число N. Определить, является ли оно совершенным (совершенное...

17
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
29.05.2011, 12:26 #2
paRadoX-2, во-первых, в 8 строке должно быть scanf("%i", &x);
Во-вторых, в 15 строке в условии if'а происходит присваивание, а не сравнение. Результат присваивания всегда истинен (кроме случая, когда присваивается нуль). Следует "=" заменить на "==".
1
paRadoX-2
0 / 0 / 0
Регистрация: 24.10.2010
Сообщений: 18
29.05.2011, 12:32  [ТС] #3
Спасибо, в 15 строке должно было быть
C++
1
while(i<x-1);
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.05.2011, 12:35 #4
А разве в 15й строке присваивание?
Только я не понимаю этого
C++
1
while(i!=x);
Он же ничего не делает
Пока истинно условие (i!=x) будет выполнятся ; , т.е. ничего не будет выполнятся вообще
Вот вечный цикл будет=)
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
29.05.2011, 12:37 #5
diagon, кнопка "Правка" творит чудеса
А while здесь не самостоятельный, к нему do в 9 строке относится.
1
Svetilka666
0 / 0 / 0
Регистрация: 03.07.2011
Сообщений: 12
03.07.2011, 15:10 #6
а можно эту же программу только на С++?оооочень надо!
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.07.2011, 15:26 #7
C++
1
2
3
4
5
6
7
8
#include <iostream>
int main(){
    unsigned n, sum = 0;
    std::cin >> n;
    for (int i = n/2; i; --i)
        if (n % i == 0) sum += i;
    std::cout << std::boolalpha << (n == sum);
}
Кстати, никто не подскажет алгоритм, по которому можно найти все совершенные числа до 10^18 менее чем за секунду? -_-
1
grizlik78
Эксперт С++
1964 / 1457 / 119
Регистрация: 29.05.2011
Сообщений: 3,016
03.07.2011, 15:41 #8
Цитата Сообщение от diagon Посмотреть сообщение
Кстати, никто не подскажет алгоритм, по которому можно найти все совершенные числа до 10^18 менее чем за секунду? -_-
Не знаю. Но учитывая, что таких чисел всего 7, их проще прям из массива и брать
1
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.07.2011, 16:41 #9
Цитата Сообщение от grizlik78 Посмотреть сообщение
Не знаю. Но учитывая, что таких чисел всего 7, их проще прям из массива и брать
Так неинтересно, и врядли таким образом можно попасть на первое-второе место на acmp =)
Ничего полезного нагуглить не получилось, максимально быстрый перебор получился таким.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
bool isPerfect(unsigned long long x){
    unsigned long long sum = 0;
    for(unsigned long long i = 1 ; i <= x/2; ++i){
        if (x % i == 0) sum += i;
        if (x < sum) return false;
    }   
    return sum == x;
}
int main(){
    unsigned long long x = 0;
    for (int i = 1; i < 10000; i += 2){
        x += i*i*i;
        if (isPerfect(x)) std::cout << x << std::endl;
    }
    return 0;
}
Это исходя из того, что все они являются суммой кубов нечетных чисел.
Выводит первые 5(считая 6), дальше виснет.
Видимо на ДП задачка...
0
grizlik78
Эксперт С++
1964 / 1457 / 119
Регистрация: 29.05.2011
Сообщений: 3,016
03.07.2011, 17:01 #10
Ну тогда из чисел Мерсенна можно попробовать...
Код
for v in [6, 28, 496, 8128, 33550336, 8589869056, 137438691328]:
    print factor(v)

2 * 3
2^2 * 7
2^4 * 31
2^6 * 127
2^12 * 8191
2^16 * 131071
2^18 * 524287

for p in [2,3,5,7,13,17,19]:
    print 2**(p-1) * (2**p - 1)

6
28
496
8128
33550336
8589869056
137438691328
то есть можно перебирать степени двойки и проверять, получилось ли совершенное число, или нет. Не знаю, насколько это по-читерски.
1
botasa
3 / 3 / 0
Регистрация: 18.01.2011
Сообщений: 131
03.07.2011, 17:26 #11
задача из книги Дейтлов, я ее пропустил, бесят меня такие задачи на числа
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.07.2011, 21:38 #12
diagon, В книге Федора Меньшикова "Олимпиадные задачи по программированию" есть разбор этой задачи. Приведенный там алгоритм укладывается в 1 секунду.
1
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.07.2011, 21:42 #13
Цитата Сообщение от valeriikozlov Посмотреть сообщение
diagon, В книге Федора Меньшикова "Олимпиадные задачи по программированию" есть разбор этой задачи. Приведенный там алгоритм укладывается в 1 секунду.
Спасибо, не знал что такая есть...
А какую-нибудь еще литературу по олимпиадным задачам посоветовать можете?

Не по теме:

grizlik78, таки я win =)

0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.07.2011, 21:52 #14
Еще есть книга "Московские олимпиады по информатике" под редакцией Е.В. Андреевой, В.М. Гуровица, В.А. Матюхина.
И в первой книге и в этой есть разборы некоторых задач с ********
Больше не знаю.
1
azusdex
0 / 0 / 0
Регистрация: 20.07.2011
Сообщений: 6
20.07.2011, 01:51 #15
Всего известных совершенных чисел на апрель 2010 года было 47. Но я думаю столько не нужно.
Самый известный способ это или простые числа Мерсенна(был приведен выше, так что описывать нет смысла) или алгоритм Евклида (тоже основан на простых числах): 2^(p-1) * 2^p-1 так что бы 2^p-1 являлось простым числом, например p=2 => (2^2-1) = 3 простое число, 2^(2-1)*2^2-1 = 6 совершенное число.
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
 
void perfectNumbers(unsigned long long max){
    //с помощью unsigned long long позволяет найти 137 438 691 328
    
    cout << "\nThis numbers is Perfect: " << endl;
    unsigned long long a, b;
    for (long i = 2; i < max; i++){
        a = pow(2,i)-1;
        if (isPrime(a) == 1){  //проверяем если это простое число
            b = pow(2,(i-1));
            if (a > max || a*b > max) //если да то умножаем на вторую часть 
                break;
            cout << b*a << endl;
        }
    }
}
 
 
//функция для нахождения простых чисел
bool isPrime(unsigned long long num){
    for(unsigned long long i = 2; i < (sqrt(num) + 1); i++){
        if(num % i == 0){
            return 0;
            break;
        }
    }
    return 1;
}
Алгоритм сразу откидывает все нечетные числа, так как совершенных нечетных чисел еще не найдено.
Если число p^2-1 простое (это и есть число Мерсенна) то проверки дальше не нужны, просто умножаем на вторую часть. Можно доработать функцию нахождения простых чисел, если не дорабатывать то первые пять чисел находит за секунду, шестое больше минуты, седьмое за минут 20, дальше не пробовал потому что не уверен если можно вывести такое гигантское число
0
20.07.2011, 01:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.07.2011, 01:51
Привет! Вот еще темы с ответами:

Определить, является ли заданное натуральное число простым - C++
Определить, является ли заданное натуральное число простым

Определить, является ли заданное натуральное число палиндромом - C++
Всем доброго времени суток!Подскажите пожалуйста, если для определения является ли строка палиндромом программа выглядит так: #include...

Определить, является ли заданное натуральное число простым - C++
Определить, является ли заданное натуральное число простым. Циклический алгоритм. Блок схема, тест. Кода не надо. Добавлено...

Определить, является ли заданное натуральное число простым - C++
Определить, является ли заданное натуральное число простым. Выходные данные: Вывести YES или NO. Ввод 29 Вывод YES


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

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

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