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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.74
paRadoX-2
0 / 0 / 0
Регистрация: 24.10.2010
Сообщений: 18
29.05.2011, 12:17     Определить, является ли заданное натуральное число совершенным #1
Определить, является ли заданное натуральное число совершенным, т.е. равным сумме всех своих (положительных) делителей, кроме самого этого числа (например, совершенное число 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();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2011, 12:17     Определить, является ли заданное натуральное число совершенным
Посмотрите здесь:

Определить, является ли заданное натуральное число палиндромом C++
Ввести натуральное число N. Определить, является ли оно совершенным C++
Определить, является ли заданное натуральное число простым C++
C++ Определить является ли заданное натуральное число совершенным
C++ Проверить, является ли заданное натуральное число совершенным
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
29.05.2011, 12:26     Определить, является ли заданное натуральное число совершенным #2
paRadoX-2, во-первых, в 8 строке должно быть scanf("%i", &x);
Во-вторых, в 15 строке в условии if'а происходит присваивание, а не сравнение. Результат присваивания всегда истинен (кроме случая, когда присваивается нуль). Следует "=" заменить на "==".
paRadoX-2
0 / 0 / 0
Регистрация: 24.10.2010
Сообщений: 18
29.05.2011, 12:32  [ТС]     Определить, является ли заданное натуральное число совершенным #3
Спасибо, в 15 строке должно было быть
C++
1
while(i<x-1);
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.05.2011, 12:35     Определить, является ли заданное натуральное число совершенным #4
А разве в 15й строке присваивание?
Только я не понимаю этого
C++
1
while(i!=x);
Он же ничего не делает
Пока истинно условие (i!=x) будет выполнятся ; , т.е. ничего не будет выполнятся вообще
Вот вечный цикл будет=)
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
29.05.2011, 12:37     Определить, является ли заданное натуральное число совершенным #5
diagon, кнопка "Правка" творит чудеса
А while здесь не самостоятельный, к нему do в 9 строке относится.
Svetilka666
0 / 0 / 0
Регистрация: 03.07.2011
Сообщений: 12
03.07.2011, 15:10     Определить, является ли заданное натуральное число совершенным #6
а можно эту же программу только на С++?оооочень надо!
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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 менее чем за секунду? -_-
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
03.07.2011, 15:41     Определить, является ли заданное натуральное число совершенным #8
Цитата Сообщение от diagon Посмотреть сообщение
Кстати, никто не подскажет алгоритм, по которому можно найти все совершенные числа до 10^18 менее чем за секунду? -_-
Не знаю. Но учитывая, что таких чисел всего 7, их проще прям из массива и брать
diagon
Higher
 Аватар для diagon
1920 / 1186 / 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), дальше виснет.
Видимо на ДП задачка...
grizlik78
Эксперт С++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,960
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
то есть можно перебирать степени двойки и проверять, получилось ли совершенное число, или нет. Не знаю, насколько это по-читерски.
botasa
3 / 3 / 0
Регистрация: 18.01.2011
Сообщений: 131
03.07.2011, 17:26     Определить, является ли заданное натуральное число совершенным #11
задача из книги Дейтлов, я ее пропустил, бесят меня такие задачи на числа
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.07.2011, 21:38     Определить, является ли заданное натуральное число совершенным #12
diagon, В книге Федора Меньшикова "Олимпиадные задачи по программированию" есть разбор этой задачи. Приведенный там алгоритм укладывается в 1 секунду.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.07.2011, 21:42     Определить, является ли заданное натуральное число совершенным #13
Цитата Сообщение от valeriikozlov Посмотреть сообщение
diagon, В книге Федора Меньшикова "Олимпиадные задачи по программированию" есть разбор этой задачи. Приведенный там алгоритм укладывается в 1 секунду.
Спасибо, не знал что такая есть...
А какую-нибудь еще литературу по олимпиадным задачам посоветовать можете?

Не по теме:

grizlik78, таки я win =)

valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.07.2011, 21:52     Определить, является ли заданное натуральное число совершенным #14
Еще есть книга "Московские олимпиады по информатике" под редакцией Е.В. Андреевой, В.М. Гуровица, В.А. Матюхина.
И в первой книге и в этой есть разборы некоторых задач с ********
Больше не знаю.
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, дальше не пробовал потому что не уверен если можно вывести такое гигантское число
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
20.07.2011, 12:02     Определить, является ли заданное натуральное число совершенным #16
Является ли число совершенным. Вычисление на этапе компиляции.

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
template<int N, int X>
struct is_divide
{
    typedef typename 
    mpl::if_
    <
        mpl::modulus
        <
            mpl::int_<N>, mpl::int_<X>
        >, 
        mpl::false_,
        mpl::true_
    >::type type;
};
 
template<int N>
struct is_divide<N, 0>
{
    typedef mpl::false_ type;
};
 
template<int N, int X>
struct calc_divs
{
    typedef typename
    mpl::plus
    <
        typename calc_divs<N, X - 1>::type,
        typename mpl::if_
        <
            typename is_divide<N, X>::type,
            mpl::int_<X>,
            mpl::int_<0>
        >::type
    >::type type;
 
    static void print()
    {
        if (is_divide<N, X>::type::value)
        {
            std::cout << X << '\n';
        }
        calc_divs<N, X - 1>::print();
    }
};
 
template<int N>
struct calc_divs<N, 0>
{
    typedef typename mpl::int_<0>::type type;
    static void print()
    {
    }
};
 
template<int N>
struct is_perfect
{
    typedef typename 
    mpl::equal_to
    <
        mpl::int_<N>,
        typename calc_divs<N, N/2>::type
    >::type type;
};
 
template<int N>
struct calc_divs_
{
    typedef typename calc_divs<N, N/2>::type type;
 
    static void print()
    {
        calc_divs<N, N/2>::print();
    }
};
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
20.07.2011, 18:35     Определить, является ли заданное натуральное число совершенным #17
ForEveR, шаблонное метапрограммирование? )) Занятная вещь, буквально сегодня с утра познакомился с этим. А что такое mpl::... ?

Добавлено через 6 минут
А, все понял, оно ?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.07.2011, 18:41     Определить, является ли заданное натуральное число совершенным
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
20.07.2011, 18:41     Определить, является ли заданное натуральное число совершенным #18
Kastaneda, оно самое.
Yandex
Объявления
20.07.2011, 18:41     Определить, является ли заданное натуральное число совершенным
Ответ Создать тему
Опции темы

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