Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Футбол. Какая команда покинет высшую лигу? сделате! https://www.cyberforum.ru/ cpp-beginners/ thread279903.html
Помогите пожалуйста. 1. Даны список футбольных команд высшей лиги России и количество очков, набранных каждой командой в чемпионате России. Известно, что нет команд с равным числом очков, а две...
Использование функций и структур C++
Имеется две задачки, скажу честно , еще не решал...не успеваю...пожалуйста, уважаемые программисты помогите..буду очень признателен... Использование функций. 3. Описать функцию NMin(A,N) целого...
C++ Определить является ли квадратная матрица симметричной не получается решить.. Именуйте темы осмысленно. Название темы должно максимально полно отражать ее содержимое. https://www.cyberforum.ru/ cpp-beginners/ thread279872.html C++ C/C++)не ищет сумму! +скобки не могу правильно расставить( https://www.cyberforum.ru/ cpp-beginners/ thread279869.html
В одномерном массиве, состоящем из n вещественных элементов, вычислить: − номер минимального элемента массива; − сумму элементов массива, расположенных между первым и вторым отрицательными...
Подсчет цифр и букв C++
Народ, есть такая проблема! Мне нужно написать прогу, которая считывает текст из файла и определяет чего больше: цифр или букв. Я сделал её, но она работает только для одной строки, а мне нужно для...
C++ ostream https://www.cyberforum.ru/ cpp-beginners/ thread279847.html
Вот мой класс: class BigInt { int Size; // Size - текущая длина (истинная длинна числа) int SizeMax; // SizeMax - максимальная длина int *Coef; // Массив...
C++ Qt C++ https://www.cyberforum.ru/ cpp-beginners/ thread279841.html
как закомментить целый кусок кода в qt одним нажатием?
C++ Конвертор десятичного числа в шестнадцатиричное с алгоритмом преобразования
Конвертор десятичного числа в шестнадцатиричное с алгоритмом преобразования (без простого вывода числа в шестнадцатиричной)... помогите пожалуйста очень надо, я полный новичек, хотелось бы посмотреть...
C++ Односвязные списки https://www.cyberforum.ru/ cpp-beginners/ thread279829.html
Вот такая задачка Дан текстовый файл. Группы символов, разделенные пробелами, будем называть словами. В файле оставить только по одному экземпляру каждого слова и добавить перед ними количество их...
C++ курировать по программированию Ищу человека который за благодарность будет направлять по правильному пути в программирование. Хочу разобраться в основах программирования. Суть примерно такова, этот человек будет выдавать мне... https://www.cyberforum.ru/ cpp-beginners/ thread279828.html
Многомерные массивы C++
Плз очень надо решить эту задачу:Составить текст программы и блок-схему.Задача нужно делать на Си.
C++ Продолжение изучения C++ https://www.cyberforum.ru/ cpp-beginners/ thread279801.html
Здравствуйте! Я осилил книгу Васильева "Самоучитель C++", но не понимаю, как эти знания можно применять на практике. Не могли бы вы посоветовать хорошую книгу для дальнейшего изучения языка?
567 / 406 / 132
Регистрация: 22.11.2017
Сообщений: 1,054
19.08.2019, 11:03 0

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

19.08.2019, 11:03. Показов 19221. Ответов 25
Метки (Все метки)

Ответ

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))
расположена медленная операция %. Может есть более быстрые аналоги по поиску остатка или определению кратности?

Вернуться к обсуждению:
Найти дружественные числа, принадлежащие отрезку [1; 10000] C++
0
Миниатюры
Найти дружественные числа, принадлежащие отрезку [1; 10000]   Найти дружественные числа, принадлежащие отрезку [1; 10000]  
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.08.2019, 11:03
Готовые ответы и решения:

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

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

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

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

25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.08.2019, 11:03

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

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

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

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

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