Дружественные числа

@pasha_2001 · Регистрация: 14.11.2012

Студворк — интернет-сервис помощи студентам

Требуется написать файл-функцию для решения поставленной задачи.
Два натуральных числа называются «дружественными», если каждое из них равно сумме всех делителей другого, за исключением его самого (таковы, например, числа 220 и 284). Сформировать матрицу, строками которой являтся все пары «дружественных» чисел, не превосходящих заданного натурального числа.

Уважаемый Зосима предложил сделать следующее:

Кроме того, в задании сказано создать матрицу, поэтому я после всего добавил преобразование векторов в матрицу.
Еще в условии сказано "равно сумме всех делителей другого, за исключением его самого" поэтому для исключения этого самого я исправил 21-ю строку: из суммы вычел x.

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function M = bel(c)
 
a = [];
b = [];
for i = 1:(c-1)
    for j = (i+1):c
        if ( delitel(i)==j ) && ( delitel(j)==i )
            a = [a i]; % добавляем в конец массива
            b = [b j];
        end
    end
end
 
% Формируем матрицу
M(:,1) = a; % первый столбец
M(:,2) = b; % второй столбец
end
 
function SumDel = delitel(x)
k = 1:x;
SumDel = sum( k ( find ( mod(x,k)==0 ) )) - x;
end

Теперь создал программку использования этой функции:Код Matlab M

Matlab M
1
2
3
4
5
clear
clc
tic % засекаем секундомер
m = bel(1300) % усиленно считаем
toc % останавливаем секундомер

Оно работает... но сильно не радуйся - считает очень дооолго (И не мудрено - все считается влоб, перебором)
Я добавил tic toc чтобы видеть сколько времени оно считает.
Так даже для N=1300 (чтоб получить еще и вторую пару чисел 1184, 1210) это 160с (хотя кажется что дольше).
А когда я захотел получить четвертую пару (5020, 5564) и ввел bel(6000) - через 10 минут терпение лопнуло и я закрыл матлаб)))

Как его довести до ума - пока не знаю. Правда нашел функции расчетов подобных чисел на матворке. Надеюсь дружишь с английским

У меня при значении 1300 считалось 36 секунд.
Предлагайте знающие как ускорить алгоритм поиска)

Зосима · 14.11.2012, 16:25

Я еще чуток оптимизировал ф-цию вычисления суммы делителей:

Matlab M
1
2
3
4
5
function SD = delitel(x)
k = 1:x-1; % возможные делители, исключая само число
% немного магии:
SD = k*(mod(x,k)==0)'; % применяем матричное умножение:
end

Можно было сделть поэлементное умножение, а затем его сумму: SD = sum( k.*(mod(x,k)==0));
Но я таки вспомнил правило матричного умножения!: "элемент равен сумме произведений строки на столбец"

Пояснения к 4-й строке: если x - число, а k=1:x-1 - вектор, то:
mod(x,k) - это тоже вектор остатков от деления x на k.
mod(x,k)==0 - логический вектор, в котором на позициях, где выполняется условие будет 1, где не выполняется - 0, но это также как и k - вектор-строка, поэтому мы его транспонируем: (mod(x,k)==0)' и совершаем матричное умножение под которое и заточен матлаб.

Также вместо двух строк можно записать одну:
SD = (1:x-1)*(mod(x,(1:x-1))==0)';
Но методом научного тыка (дя, я написал маленькую программку) получилось, что такая конструкция считает дольше (вероятно когда интерпретатор натыкается на (1:x-1) ему приходится каждый раз создавать новую переменную, рассчитывать ее и выделять память).

Но даже с такой максимально оптимизированной функцией суммы делителей вычисления не сильно ускорились

Будем думать над телом функции bel.

Добавлено через 1 час 33 минуты
Хе, удалось рассчитать 6 пар чисел (N=11000) за 15 секунд

Все что я сделал: сразу рассчитал в массив значения сумм делителей всех чисел меньших N, а затем путем перебора элементов массива находил пары по предложенному тобой выражению.

Таким образом значительно уменьшилось кол-во вызовов ф-ции расчета суммы.
В данном варианте она вызывается только N=11000 раз, в начале.
А в предыдущем для (N=1300) ф-ция вызывалась 1688700 раз!

Вот как я это узнал:

Кликните здесь для просмотра всего текста

Matlab M
1
2
3
4
5
6
7
8
N = 1300;
n = 0;
for i = 1:(N-1)
    for j = (i+1):N
        n = n+2; % потому как вызывается в обеих условиях
    end
end
n

Поэтому какой бы оптимальной и быстрой не была ф-ция расчета суммы, при таком кол-ве обращений, длительность расчетов будет немалым!

Ах да, совсем забыл выложить листинг новой файл-функции:

Matlab M
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
function M = bel(N)
 
% рассчитаем суммы делителей для всех чисел меньше N
for i=1:N
    SD(i) = sumdel(i);
end
 
% объявляем массивы
a = zeros(1,N); 
b = a;
for i = 1:(N-1)
    for j = (i+1):N
        if ( SD(i)==j ) && ( SD(j)==i )
            % добавляем числа в матрицу
            a(i) = i; 
            b(i) = j;
        end
    end
end
 
% формируем матрицу из ненулевых элементов
M(:,1) = a(a~=0);
M(:,2) = b(b~=0);
end
 
function SD = sumdel(x) % рассчет суммы делителей
k = 1:x-1; % исключая само число
SD = k*(mod(x,k)==0)';
end

Вот как бы и все пока

Единственное, над чем еще можно подумать - это более эффективное нахождение пары чисел.
Вероятно можно избавиться от циклов и заменить их векторными и логическими операциями, но мне пока ничего конкретного на ум не приходит

@pasha_2001 · 14.11.2012, 16:33 **[ТС]**

Супер, работает очень быстро

Огромное спасибо!

Зосима · 14.11.2012, 20:16

Не по теме:

Дружественные числа? Что вы делаете? Аххах! Прекратите! :D

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function M = bel(N)
 
SD = zeros(1,N);
x = 1:N
;
for i = x
    k = 1:x(i)-1;
    SD(i) = k*( mod(x(i),k)==0 )';
end
 
a = zeros(1,N);  b = a;
for i = 1:(N-1)
     for j = (i+1):N
         if (SD(i)==j)&&(SD(j)==i)
             a(i) = i;
             b(i) = j;
         end
    end 
end
M(:,1) = a(a>0);
M(:,2) = b(b>0);
end

Вот что я набросал по дороге домой с телефона.
Я внес подфункцию sumdel в тело самй функции bel, это позволит еще уменьшить кол-во обращений к внешним ф-циям и должно увеличить быстродействие.

Проверь длительность на N=11000

Matlab M
1
2
3
4
clear
tic
bel(11000)
toc

О результатах сообщи, крайне любопытно узнать прав я был или нет

Добавлено через 8 минут
В 4й строке точка с запятой убежала - исправь пожалуйста!
А то он выведет массив x=1:N и загадит весь экран)))

@pasha_2001 · 15.11.2012, 09:30 **[ТС]**

По скорости на моем компе последний результат выиграл по времени 0.2 сек)
Кстати сегодня заметил и не понял что означает ' в строке

Matlab M
1
SD(i) = k*( mod(x(i),k)==0 )';

?

Зосима · 15.11.2012, 09:39

Сообщение от pasha_2001

По скорости на моем компе последний результат выиграл по времени 0.2 сек)

Ясненько, значит не сильно повлияло на быстродействие. Значит мы уже довольно близко приблизились к пределу.

Кстати сегодня заметил и не понял что означает ' в строке
SD(i) = k*( mod(x(i),k)==0 )'; ?

Этот значек означает транспонирование, т.е. вектор-строка (mod==1) превращается в вектор-столбец (разворачивается), только так будет правильно работать матричное умножение: сумма произведений строки k на столбец (mod==1)'
Смекаешь?

@pasha_2001 · 15.11.2012, 09:45 **[ТС]**

смекаю, но самую малость

пошерстю интернет еще

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@pasha_2001 0 / 0 / 0 Регистрация: 14.11.2012 Сообщений: 89
	14.11.2012, 16:33 [ТС]
	Супер, работает очень быстро Огромное спасибо! 0

@pasha_2001 0 / 0 / 0 Регистрация: 14.11.2012 Сообщений: 89
	15.11.2012, 09:45 [ТС]
	смекаю, но самую малость пошерстю интернет еще 0