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

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

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

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

02.08.2014, 21:01. Просмотров 1506. Ответов 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 тесте, подскажите, где ошибка? Заранее благодарен
http://********/index.asp?main=task&id_task=364
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.08.2014, 21:01     Найти все совершенные числа от M до N
Посмотрите здесь:
C++ Найти все совершенные числа (С++)
C++ Найти все совершенные числа в заданном интервале
C++ Найти все совершенные числа, меньшие заданного
Найти все совершенные числа меньшие заданного C++
Найти и распечатать все совершенные числа в заданном интервале C++
C++ Найти и напечатать все совершенные числа в заданном интервале
C++ Для заданного натурального числа N вывести в столбик все совершенные числа меньшие N c++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
02.08.2014, 21:11     Найти все совершенные числа от M до N #2
Я понять не могу, в чём удовольствие решать задачи из какого-то сайта, если решения для них ты копипастишь с форума на другом сайте? Я понимаю, когда школота тут свою домашку спрашивает... Но ведь участие в конкурсах - дело добровольное!
_Ivana
3042 / 1729 / 150
Регистрация: 01.03.2013
Сообщений: 4,908
Записей в блоге: 2
02.08.2014, 21:29     Найти все совершенные числа от M до N #3
Kuzia domovenok, имхо это хороший вариант освоить язык и методы. Я тоже порой увлекаюсь задачами с сайтов, и если у меня что-то не получается - задаю вопросы на форумах и набираюсь уму-разуму от специалистов.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
02.08.2014, 22:28     Найти все совершенные числа от M до N #4
Neoks, 5 * 1018 это 5 * 10^18?
щас загуглил и в википедии там даны эти совершенные числа, короче берешь пихаешь их в массив и отправляешь)
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 06:50  [ТС]     Найти все совершенные числа от M до N #5
Kuzia domovenok, решал задачи по нарастающей сложности, а эту решить не смог, лучше узнать решение
у более умных людей, чем не решить вовсе

Добавлено через 22 секунды
SlavaSSU, не интересно же
CyberSolver
101 / 74 / 17
Регистрация: 23.07.2014
Сообщений: 686
Записей в блоге: 1
03.08.2014, 07:35     Найти все совершенные числа от M до N #6
Цитата Сообщение от Neoks Посмотреть сообщение
SlavaSSU, не интересно же
Зато правильно. Есть такой класс задач. Ну либо вспомнить про простые числа Мерсенна. Если вы ещё знаете специальные алгоритмы для них (проверки на простоту) - тогда точно в секунду уложитесь.
Mr.X
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
03.08.2014, 09:34     Найти все совершенные числа от M до N #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
}
Бендерродригез
Сгибальщик
42 / 42 / 3
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
03.08.2014, 10:17     Найти все совершенные числа от M до N #8
Цитата Сообщение от Neoks Посмотреть сообщение
не интересно же
А зачем по-твоему на собеседованиях задают задачи про 2 шнура и про круглые люки канализации спрашивают?
Надо ли городить код, если можно просто использовать данные из открытого доступа?
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,190
Завершенные тесты: 1
03.08.2014, 10:29     Найти все совершенные числа от M до N #9
Цитата Сообщение от Бендерродригез Посмотреть сообщение
Надо ли городить код, если можно просто использовать данные из открытого доступа?
Надо. Если бы это была какая-то олимпиада и полагался бы какой-то приз, то там все методы хороши. А тут задачи чисто для общего развития. А если изменить чуть-чуть условия? Методы решения будут те же, а в инете ответа не найдётся.
Бендерродригез
Сгибальщик
42 / 42 / 3
Регистрация: 18.05.2013
Сообщений: 220
Завершенные тесты: 1
03.08.2014, 11:35     Найти все совершенные числа от M до N #10
Цитата Сообщение от Somebody Посмотреть сообщение
Надо. Если бы это была какая-то олимпиада и полагался бы какой-то приз, то там все методы хороши. А тут задачи чисто для общего развития. А если изменить чуть-чуть условия? Методы решения будут те же, а в инете ответа не найдётся.
Недавно как раз читал об излишнем желании повторного использования кода. К чему писать "универсальный" метод, если есть более простое решение под данное условие?
Вот поменяются условия чуть-чуть, тогда и решай задачу по-другому, с классами и парсерами.
Умение не делать лишнего (которое в будущем подарит радостные часы поиска багов) - это так же общее развитие.
zer0mail
2330 / 1956 / 192
Регистрация: 03.07.2012
Сообщений: 7,013
Записей в блоге: 1
03.08.2014, 11:50     Найти все совершенные числа от M до N #11
Ясно дело, 5*1018 не влезает в long и надо использовать long long
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 12:01  [ТС]     Найти все совершенные числа от M до N #12
Бендерродригез, даже если так, то не проходит по времени
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
03.08.2014, 12:35     Найти все совершенные числа от M до N #13
Neoks, кинь готовый код, я просто не понимаю, как она может не проходить по времени!
И кстати, то что эти числа высиляются по такой формуле, ты же тоже загуглил xD.
Твой код с лонг лонгами работает у меня.
Jewbacabra
Эксперт PHP
2261 / 1925 / 722
Регистрация: 24.04.2014
Сообщений: 5,613
03.08.2014, 12:38     Найти все совершенные числа от M до N #14
Neoks, Быстрый поиск совершенных чисел
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.08.2014, 13:52     Найти все совершенные числа от M до N
Еще ссылки по теме:
C++ Получить все совершенные числа, меньше n
C++ В цикле вывести на экран все совершенные числа
Функции. Получить все совершенные числа меньше заданного C++
В линейном динамическом массиве уничтожить все совершенные числа C++
C++ Из заданного интервала натуральных чисел выбрать все совершенные числа

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

Или воспользуйтесь поиском по форуму:
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
03.08.2014, 13:52  [ТС]     Найти все совершенные числа от M до N #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;
}
Yandex
Объявления
03.08.2014, 13:52     Найти все совершенные числа от M до N
Ответ Создать тему
Опции темы

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