Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
#1

Найти все совершенные числа от M до N - C++

02.08.2014, 21:01. Просмотров 1932. Ответов 21
Метки нет (Все метки)

Совершенные числа
(Время: 1 сек. Память: 16 Мб )
Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. Требуется найти все совершенные числа от M до N.

Входные данные

Входной файл INPUT.TXT содержит числа M и N, разделенные пробелом. (1 <= M <= N <= 5*1018)

Выходные данные

В выходной файл OUTPUT.TXT выведите по одному числу в строке в порядке возрастания все совершенные числа, находящихся на отрезке [M, N]. В том случае, когда таких чисел нет следует вывести «Absent».

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
#include <stdio.h>
#include <math.h>
 
int main()
{
    int mas[8]={2, 3, 5, 7, 13, 17, 19, 31};
    long M, N, temp;
    int fl=1, i, fl1=0;
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%ld%ld", &M, &N);
    for(i=0; i<8 && fl; i++)
    {
        temp=long(pow((double)2,(double) mas[i]-1)*(pow((double)2,(double)mas[i])-1));
        if(temp>=M && temp<=N)
        {
            printf("%ld\n", temp);
            fl1=1;
        }
        if(temp>N)
            fl=0;
    }
    if(!fl1){printf("Absent");}
  return 0;
}
Пролетает на 10 тесте, подскажите, где ошибка? Заранее благодарен
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.08.2014, 21:01
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Найти все совершенные числа от M до N (C++):

Найти все совершенные числа (С++)
Найдите все совершенные числа находящиеся в интервале (900;9000)

Найти все совершенные числа, меньшие заданного
Натуральное число называется совершенным, если оно равно сумме своих делителей,...

Найти все совершенные числа меньшие заданного
Натуральное число называется совершенным, если оно равно сумме своих делителей,...

Найти все совершенные числа в заданном интервале
Задача. Натуральное число называется совершенным, если оно равно сумме всех...

Найти и распечатать все совершенные числа в заданном интервале
Чтсло равное сумме всех своих делителей,включая единицу,называется совершенным....

Найти и напечатать все совершенные числа в заданном интервале
Число равно сумме своих делителей включая единицу называется совершенных.Найти...

21
Kuzia domovenok
2218 / 1987 / 448
Регистрация: 25.03.2012
Сообщений: 6,979
Записей в блоге: 1
02.08.2014, 21:11 #2
Я понять не могу, в чём удовольствие решать задачи из какого-то сайта, если решения для них ты копипастишь с форума на другом сайте? Я понимаю, когда школота тут свою домашку спрашивает... Но ведь участие в конкурсах - дело добровольное!
6
_Ivana
3233 / 1861 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
02.08.2014, 21:29 #3
Kuzia domovenok, имхо это хороший вариант освоить язык и методы. Я тоже порой увлекаюсь задачами с сайтов, и если у меня что-то не получается - задаю вопросы на форумах и набираюсь уму-разуму от специалистов.
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
02.08.2014, 22:28 #4
Neoks, 5 * 1018 это 5 * 10^18?
щас загуглил и в википедии там даны эти совершенные числа, короче берешь пихаешь их в массив и отправляешь)
0
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 06:50  [ТС] #5
Kuzia domovenok, решал задачи по нарастающей сложности, а эту решить не смог, лучше узнать решение
у более умных людей, чем не решить вовсе

Добавлено через 22 секунды
SlavaSSU, не интересно же
0
CyberSolver
101 / 74 / 17
Регистрация: 23.07.2014
Сообщений: 852
Записей в блоге: 1
03.08.2014, 07:35 #6
Цитата Сообщение от Neoks Посмотреть сообщение
SlavaSSU, не интересно же
Зато правильно. Есть такой класс задач. Ну либо вспомнить про простые числа Мерсенна. Если вы ещё знаете специальные алгоритмы для них (проверки на простоту) - тогда точно в секунду уложитесь.
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
03.08.2014, 09:34 #7
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/////////////////////////////////////////////////////////////////////////////////////////
//СОВЕРШЕННЫЕ ЧИСЛА
//(Время: 1 сек. Память: 16 Мб )
//Число называется совершенным, если оно равно сумме всех своих делителей, меньших его самого. 
//Требуется найти все совершенные числа от M до N.
//ВХОДНЫЕ ДАННЫЕ
//
//Входной файл INPUT.TXT содержит числа M и N, разделенные пробелом. (1 <= M <= N <= 5*10^18)
//
//ВЫХОДНЫЕ ДАННЫЕ
//
//В выходной файл OUTPUT.TXT выведите по одному числу в строке в порядке возрастания все 
//совершенные числа, находящихся на отрезке [M, N]. В том случае, когда таких чисел нет 
//следует вывести «Absent».
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
typedef long long       T_int;
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::set<T_int>    T_int_set;
/////////////////////////////////////////////////////////////////////////////////////////
void    print_perfect_numbers_from_to
        (
            T_int   min,
            T_int   max
        )
{
    T_int_set  perfect_numbers;
 
    perfect_numbers.insert( 6                   );
    perfect_numbers.insert( 28                  );
    perfect_numbers.insert( 496                 );
 
    perfect_numbers.insert( 8128                );
    perfect_numbers.insert( 33550336            );
    perfect_numbers.insert( 8589869056          );
 
    perfect_numbers.insert( 137438691328        );
    perfect_numbers.insert( 2305843008139952128 );
 
    auto    min_val_it  =   perfect_numbers.lower_bound( min );
    auto    max_val_it  =   perfect_numbers.upper_bound( max );
 
    if  (
            min_val_it  ==  max_val_it
        )
    {
        std::cout   <<  "Absent"
                    <<  std::endl;
    }
    else
    {
        std::copy
            (
                min_val_it,
                max_val_it,
                std::ostream_iterator<T_int>( std::cout, "\n" )
            );
    }//else
}
/////////////////////////////////////////////////////////////////////////////////////////
void    print_prompt_and_input_val_in_segment
            (
                T_str   const   &   prompt,
                double          &   val,
                T_int               left_bound,
                T_int               right_bound
            )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  val;
    }
    while   (
                    val             <   left_bound
                ||  right_bound     <   val
            );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_int     const   MIN_BOUND_VAL   =   1;
    T_int     const   MAX_BOUND_VAL   =   T_int (
                                                    5 * pow( 10.0,  18.0 )
                                                );
 
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl;
 
        std::cout   <<  "Введите границы отрезка ("
                    <<  MIN_BOUND_VAL
                    <<  ".."
                    <<  MAX_BOUND_VAL
                    <<  "):"
                    <<  std::endl;
 
        double     min =   0;
 
        print_prompt_and_input_val_in_segment
            (
                "min = ",
                min,
                MIN_BOUND_VAL,
                MAX_BOUND_VAL
            );
 
        double     max =   0;
 
        print_prompt_and_input_val_in_segment
            (
                "max = ",
                max,
                T_int( min ),
                MAX_BOUND_VAL
            );
 
        print_perfect_numbers_from_to
            (
                T_int( min ),
                T_int( max )
            );
    }//for
}
0
Бендерродригез
Сгибальщик
42 / 42 / 4
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
03.08.2014, 10:17 #8
Цитата Сообщение от Neoks Посмотреть сообщение
не интересно же
А зачем по-твоему на собеседованиях задают задачи про 2 шнура и про круглые люки канализации спрашивают?
Надо ли городить код, если можно просто использовать данные из открытого доступа?
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,211
Завершенные тесты: 3
03.08.2014, 10:29 #9
Цитата Сообщение от Бендерродригез Посмотреть сообщение
Надо ли городить код, если можно просто использовать данные из открытого доступа?
Надо. Если бы это была какая-то олимпиада и полагался бы какой-то приз, то там все методы хороши. А тут задачи чисто для общего развития. А если изменить чуть-чуть условия? Методы решения будут те же, а в инете ответа не найдётся.
0
Бендерродригез
Сгибальщик
42 / 42 / 4
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
03.08.2014, 11:35 #10
Цитата Сообщение от Somebody Посмотреть сообщение
Надо. Если бы это была какая-то олимпиада и полагался бы какой-то приз, то там все методы хороши. А тут задачи чисто для общего развития. А если изменить чуть-чуть условия? Методы решения будут те же, а в инете ответа не найдётся.
Недавно как раз читал об излишнем желании повторного использования кода. К чему писать "универсальный" метод, если есть более простое решение под данное условие?
Вот поменяются условия чуть-чуть, тогда и решай задачу по-другому, с классами и парсерами.
Умение не делать лишнего (которое в будущем подарит радостные часы поиска багов) - это так же общее развитие.
0
zer0mail
2451 / 2085 / 216
Регистрация: 03.07.2012
Сообщений: 7,566
Записей в блоге: 1
03.08.2014, 11:50 #11
Ясно дело, 5*1018 не влезает в long и надо использовать long long
0
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 12:01  [ТС] #12
Бендерродригез, даже если так, то не проходит по времени
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
03.08.2014, 12:35 #13
Neoks, кинь готовый код, я просто не понимаю, как она может не проходить по времени!
И кстати, то что эти числа высиляются по такой формуле, ты же тоже загуглил xD.
Твой код с лонг лонгами работает у меня.
0
Jewbacabra
Эксперт PHP
3096 / 2683 / 1228
Регистрация: 24.04.2014
Сообщений: 8,211
03.08.2014, 12:38 #14
Neoks, Быстрый поиск совершенных чисел
0
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 13:52  [ТС] #15
SlavaSSU,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <fstream>
using namespace std;
int main ()
{
int c[8]={6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128};
int a,b;
cin>>a>>b;
for(int i=0;i<=7;i++)
    for(int j=a;j<=b;j++)
if (j==c[i])
    cout<<c[i]<<endl;
else
    cout<<"absent";
return 0;
}
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
03.08.2014, 13:59 #16
Neoks, ох как. как она вообще до 10 теста доходила.

надо так

C++
1
2
3
for(int i = 0; i < 8; i++)
    if(c[i] >= a && c[i] <= b)
        cout << c[i] << ' ';
0
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 14:22  [ТС] #17
SlavaSSU, пожалуйста, напишите программу полностью, я не понял
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
03.08.2014, 14:30 #18
Neoks,
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
#include <iostream>
#include <fstream>
 
using namespace std;
 
int main ()
{
    long long c[8]={6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128};
    long long a, b;
    cin >> a >> b;
    bool ok = false;
    for(int i = 0; i < 8; i++)
    {
        if(c[i] >= a && c[i] <= b)
        {
            cout << c[i] << ' ';
            ok = true;
        }
    }
 
    if(!ok)
        cout << "Absent" << endl;
    return 0;
}
0
ValeryS
Модератор
7134 / 5401 / 669
Регистрация: 14.02.2011
Сообщений: 18,228
03.08.2014, 14:42 #19
Цитата Сообщение от SlavaSSU Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
    for(int i = 0; i < 8; i++)
    {
        if(c[i] >= a && c[i] <= b)
        {
            cout << c[i] << ' ';
            ok = true;
        }
    }
так ради прикола
другое решение
C++
1
2
3
4
5
6
7
8
int i = 0;
for (; i < 8 && c[i] < a; i++)
    ;
for (; i < 8 && c[i] <= b; i++)
{
    cout << c[i] << ' ';
    ok = true;
}
0
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 15:25  [ТС] #20
SlavaSSU, не проходит по времени
0
03.08.2014, 15:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.08.2014, 15:25
Привет! Вот еще темы с решениями:

Цикл: Вывести все совершенные числа и все пары дружественных чисел из промежутка [2, n].
Число називається досконалим, якщо воно дорівнює сумі всіх своїх дільників,...

Для заданного натурального числа N вывести в столбик все совершенные числа меньшие N c++
Для заданного натурального числа N вывести в столбик все совершенные числа...

Получить все совершенные числа, меньше n
Натуральное число называется совершенным, если оно равно сумме всех своих...

В цикле вывести на экран все совершенные числа
продолжение того же задания, но уже с дополнением... Создать функцию, которая...


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

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

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