Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.61/88: Рейтинг темы: голосов - 88, средняя оценка - 4.61
0 / 0 / 1
Регистрация: 16.03.2010
Сообщений: 17
1

Найти дружественные числа, принадлежащие отрезку [1; 10000]

20.04.2011, 10:14. Показов 18351. Ответов 25
Метки нет (Все метки)

Помогите, сегодня сдавать надо.

Дружественными числами являются два натуральных числа, таких, что каждое из них равно сумме всех натуральных делителей другого, исключая само это другое число. Например: 220 и 284 являются дружественными числами, поскольку сумма делителей числа 220 – это 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284, а сумма делителей числа 284 – это 1 + 2 + 4 + 71 + 142 = 220.
Найти дружественные числа, принадлежащие отрезку [1; 10000].

Заранее благодарен.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.04.2011, 10:14
Ответы с готовыми решениями:

Положительные числа матрицы не принадлежащие заданному отрезку заменить на ноль
Данная целочисленная матрица А (5, 4). В матрице А все положительные числа, которые не принадлежат...

Найти числа, принадлежащие отрезку [a,b], количество делителей у которых является произведением двух простых чисел
Помогите пожалуйста написать коды для след. условий: 3.Найти натуральные числа, принадлежащие...

Дружественные числа до 10000
Здравствуйте. Помогите с задачкой: Найти все пары дружественных чисел до 10 000. Пара дружественных...

Выберите числа, принадлежащие заданному отрезку (блок схема)
Даны три числа. Выберите те из них, которые принадлежат заданному отрезку .

25
567 / 406 / 132
Регистрация: 22.11.2017
Сообщений: 1,043
19.08.2019, 11:03 21
OverClocker, Romiusse, привет!
Вот мой вариант решения через 4 месяца после создания темы.
Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
 
#include <chrono>
#include <ratio>
 
//Выбор типа часов с самым точным периодом в рамках STL
using clock_type = std::chrono::high_resolution_clock;
//Выбор единиц измерения времени
using seconds = std::chrono::duration<double>;
using milliseconds = std::chrono::duration<double, std::ratio_multiply<seconds::period, std::milli>>;
using microseconds = std::chrono::duration<double, std::ratio_multiply<seconds::period, std::micro>>;
 
std::vector<size_t> split_to_divisors(size_t num);
std::vector<std::pair<size_t, size_t>> sum_of_divisors(size_t left, size_t right);
std::vector<std::pair<size_t, size_t>> find_friendly_numbers(std::vector<std::pair<size_t, size_t>>& box);
void remove_duplicates_friendly_numbers(std::vector<std::pair<size_t, size_t>>& friendly_numbers);
 
int main()
{
    setlocale(LC_ALL, "Rus");
    const size_t left = 1u;
    const size_t right = 10000u;
 
    auto start = clock_type::now();
 
    std::vector<std::pair<size_t, size_t>> box = sum_of_divisors(left, right);
    std::vector<std::pair<size_t, size_t>> friendly_numbers = find_friendly_numbers(box);
    remove_duplicates_friendly_numbers(friendly_numbers);
    std::sort(std::begin(friendly_numbers), std::end(friendly_numbers));
 
    auto finish = clock_type::now();
    auto duration = milliseconds(finish - start);
    std::cout << "На поиск дружественных чисел в диапозоне от "
        << left  << " до " << right
        << " затрачено " << duration.count() << " миллисекунд" << std::endl;
 
    for (const auto& p : friendly_numbers)
        std::cout << p.first << " -> " << p.second << "\n";
 
    return 0;
}
 
std::vector<size_t> split_to_divisors(size_t num)
{
    std::vector<size_t> divisors(num);
    size_t idx0 = 0u;
    for (size_t idx = 1u; idx < num; ++idx)
        if (!(num % idx))
            divisors[idx0++] = idx;
    divisors.erase(std::next(std::begin(divisors), idx0), std::end(divisors));
    divisors.shrink_to_fit();
    return divisors;
}
 
std::vector<std::pair<size_t, size_t>> sum_of_divisors(size_t left, size_t right)
{
    std::vector<std::pair<size_t, size_t>> box(right - left + 1u);
    size_t idx = 0u;
    for (size_t num = left; num <= right; ++num)
    {
        std::vector<size_t> divisors = split_to_divisors(num);
        size_t sum = std::accumulate(std::begin(divisors), std::end(divisors), 0u);
        box[idx++] = { num, sum };
    }
    return box;
}
 
std::vector<std::pair<size_t, size_t>> find_friendly_numbers(std::vector<std::pair<size_t, size_t>>& box)
{
    std::vector<std::pair<size_t, size_t>> friendly_numbers;
    for (const auto& p : box)
    {
        if (p.first != p.second)
        {
            auto predicate_find = [p](const std::pair<size_t, size_t>& p_now)
            {
                return p.first == p_now.second && p.second == p_now.first;
            };
            std::vector<std::pair<size_t, size_t>>::iterator it = std::find_if(std::begin(box), std::end(box), predicate_find);
            if (it != std::end(box))
                friendly_numbers.emplace_back((*it).first, (*it).second);
        }
    }
    return friendly_numbers;
}
 
void remove_duplicates_friendly_numbers(std::vector<std::pair<size_t, size_t>>& friendly_numbers)
{
    for (auto it = std::rbegin(friendly_numbers); it != std::rend(friendly_numbers); ++it)
    {
        auto p = *it;
        auto predicate_del = [p](const std::pair<size_t, size_t>& p_now)
        {
            return p.first == p_now.second && p.second == p_now.first;
        };
        std::vector<std::pair<size_t, size_t>>::iterator new_end_it =
            std::remove_if(std::begin(friendly_numbers), std::end(friendly_numbers), predicate_del);
        friendly_numbers.erase(new_end_it, std::end(friendly_numbers));
    }
}

Скрин получен при запуске программы, сделанной в режиме релиза.
У меня несколько вопросов возникло:
1. При запуске программы в режиме дебага она падает. В ходе отладки, было обнаружено, что если закоментить строку 101
C++
1
friendly_numbers.erase(new_end_it, std::end(friendly_numbers));
то программа работает успешно. Это только в режиме дебага такое прослеживается. В режиме релиза программа завершается с кодом 0. В чём причина этого, как устранить ошибку?
2. В строке 51
C++
1
if (!(num % idx))
расположена медленная операция %. Может есть более быстрые аналоги по поиску остатка или определению кратности?
0
Миниатюры
Найти дружественные числа, принадлежащие отрезку [1; 10000]   Найти дружественные числа, принадлежащие отрезку [1; 10000]  
567 / 406 / 132
Регистрация: 22.11.2017
Сообщений: 1,043
19.08.2019, 11:14 22
Цитата Сообщение от SomniPhobia Посмотреть сообщение
1. При запуске программы в режиме дебага она падает. В ходе отладки, было обнаружено, что если закоментить строку 101
friendly_numbers.erase(new_end_it, std::end(friendly_numbers));
то программа работает успешно. Это только в режиме дебага такое прослеживается. В режиме релиза программа завершается с кодом 0. В чём причина этого, как устранить ошибку?
Ошибка была в том, что
C++
1
friendly_numbers.erase(new_end_it, std::end(friendly_numbers));
выполнялся в цикле.
Исправил.
Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
 
#include <chrono>
#include <ratio>
 
//Выбор типа часов с самым точным периодом в рамках STL
using clock_type = std::chrono::high_resolution_clock;
//Выбор единиц измерения времени
using seconds = std::chrono::duration<double>;
using milliseconds = std::chrono::duration<double, std::ratio_multiply<seconds::period, std::milli>>;
using microseconds = std::chrono::duration<double, std::ratio_multiply<seconds::period, std::micro>>;
 
std::vector<size_t> split_to_divisors(size_t num);
std::vector<std::pair<size_t, size_t>> sum_of_divisors(size_t left, size_t right);
std::vector<std::pair<size_t, size_t>> find_friendly_numbers(std::vector<std::pair<size_t, size_t>>& box);
void remove_duplicates_friendly_numbers(std::vector<std::pair<size_t, size_t>>& friendly_numbers);
 
int main()
{
    setlocale(LC_ALL, "Rus");
    const size_t left = 1u;
    const size_t right = 10000u;
 
    auto start = clock_type::now();
 
    std::vector<std::pair<size_t, size_t>> box = sum_of_divisors(left, right);
    std::vector<std::pair<size_t, size_t>> friendly_numbers = find_friendly_numbers(box);
    remove_duplicates_friendly_numbers(friendly_numbers);
    std::sort(std::begin(friendly_numbers), std::end(friendly_numbers));
 
    auto finish = clock_type::now();
    auto duration = milliseconds(finish - start);
    std::cout << "На поиск дружественных чисел в диапозоне от "
        << left  << " до " << right
        << " затрачено " << duration.count() << " миллисекунд" << std::endl;
 
    for (const auto& p : friendly_numbers)
        std::cout << p.first << " -> " << p.second << "\n";
 
    return 0;
}
 
std::vector<size_t> split_to_divisors(size_t num)
{
    std::vector<size_t> divisors(num);
    size_t idx0 = 0u;
    for (size_t idx = 1u; idx < num; ++idx)
        if (!(num % idx))
            divisors[idx0++] = idx;
    divisors.erase(std::next(std::begin(divisors), idx0), std::end(divisors));
    divisors.shrink_to_fit();
    return divisors;
}
 
std::vector<std::pair<size_t, size_t>> sum_of_divisors(size_t left, size_t right)
{
    std::vector<std::pair<size_t, size_t>> box(right - left + 1u);
    size_t idx = 0u;
    for (size_t num = left; num <= right; ++num)
    {
        std::vector<size_t> divisors = split_to_divisors(num);
        size_t sum = std::accumulate(std::begin(divisors), std::end(divisors), 0u);
        box[idx++] = { num, sum };
    }
    return box;
}
 
std::vector<std::pair<size_t, size_t>> find_friendly_numbers(std::vector<std::pair<size_t, size_t>>& box)
{
    std::vector<std::pair<size_t, size_t>> friendly_numbers;
    for (const auto& p : box)
    {
        if (p.first != p.second)
        {
            auto predicate_find = [p](const std::pair<size_t, size_t>& p_now)
            {
                return p.first == p_now.second && p.second == p_now.first;
            };
            std::vector<std::pair<size_t, size_t>>::iterator it = std::find_if(std::begin(box), std::end(box), predicate_find);
            if (it != std::end(box))
                friendly_numbers.emplace_back((*it).first, (*it).second);
        }
    }
    return friendly_numbers;
}
 
void remove_duplicates_friendly_numbers(std::vector<std::pair<size_t, size_t>>& friendly_numbers)
{
    std::vector<std::pair<size_t, size_t>>::iterator new_end_it = std::end(friendly_numbers);
    for (auto it = std::rbegin(friendly_numbers); it != std::rend(friendly_numbers); ++it)
    {
        auto p = *it;
        auto predicate_del = [p](const std::pair<size_t, size_t>& p_now)
        {
            return p.first == p_now.second && p.second == p_now.first;
        };
        new_end_it = std::remove_if(std::begin(friendly_numbers), new_end_it, predicate_del);
    }
    friendly_numbers.erase(new_end_it, std::end(friendly_numbers));
}
0
Эксперт С++
5044 / 3105 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
19.08.2019, 11:20 23
SomniPhobia, падение у вас происходит потому, что вы модифицируете вектор friendly_numbers (а именно, удаляете из него элементы посредством вызова метода erase) в то время, пока итерируетесь по мену (цикл for, в теле которого вы удаляете элементы из вектора). По стандарту, после добавления/удаления элементов вектора все итераторы на него инвалидируются. Именно это в какой-то момент и происходит с итератором it, и на следующей итерации цикла при обращении к нему происходит ошибка сегментирования.
1
567 / 406 / 132
Регистрация: 22.11.2017
Сообщений: 1,043
19.08.2019, 11:34 24
silent_1991, спасибо за ответ!
Я запустил поиск дружественных чисел на интервале [1; 130 000]. Одну пару моя программа не нашла. Мне интересно стало.
Может кто знает в чём причина и почему именно эта пара выпала.
0
Миниатюры
Найти дружественные числа, принадлежащие отрезку [1; 10000]  
Эксперт С++
5044 / 3105 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
19.08.2019, 11:42 25
В коде подробно разбираться лень, но есть предположение, что проблема в том, что второе число из не найденной пары больше 130000 (оно, как видно из списка, равно 139815).
1
567 / 406 / 132
Регистрация: 22.11.2017
Сообщений: 1,043
19.08.2019, 12:23 26
silent_1991, спасибо! Да, я сейчас посмотрел, точно в этом причина.
Вот ещё скрины. Тут эта пара чисел (122 265 и 139 815) уже добавилась, а другой(их) нет, в которой(ых) одно из чисел превышает интервал поиска.
0
Миниатюры
Найти дружественные числа, принадлежащие отрезку [1; 10000]   Найти дружественные числа, принадлежащие отрезку [1; 10000]  
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.08.2019, 12:23

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Вывести на экран все числа, принадлежащие отрезку [m, n] и кратные 7
Доброго времени суток. Возник вопрос с этой задачей. Нужно сделать в форме, однако можно написать...

Вывести на экран все простые числа , принадлежащие числовому отрезку от A до B
Вывести на экран все простые числа , принадлежащие числовому отрезку от A до B

Заменить на нули числа, принадлежащие заданному отрезку, и на единицы - остальные
Помогите, пожалуйста. Даны три действительных числа x, y, z и отрезок . Заменить на нули те из...

Напечатайте на экране монитора числа, принадлежащие отрезку [1; 99] и кратные числу 3
Напечатайте на экране монитора числа, принадлежащие отрезку и кратные числу 3.


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

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

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