Помощь - Поиск - Пользователи - Календарь
Полная версия: Дружественная тройка чисел
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Zac
Привет, мноого времени уже ломаю голову над задачей, мне хотя бы алгоритм решения...

Задача Диксона. Будем говорить, что три натуральных числа образуют дружественную тройку, если сумма собственных делителей каждого числа равна сумме двух других чисел. Отыскать хотя бы одну дружественную тройку натуральных чисел.

С дружественной двойкой я бы справился, это легко, но когда одновременно надо подобрать 3 числа.....
Заранее спасибо за любую подсказку
Malice
такая пойдет ? 1980, 2016, 2556.
А вообще показывай для двойки свой код, посмотрим smile.gif
Zac
Malice, в инете нашел тройку эту smile.gif?
Кода для двойки нет smile.gif но впринцепи знаю как реализовать...
Скажите как это как в алгоритме будет выглядеть.... как я вижу числа могут быть в большом разбросе sad.gif
мисс_граффити
что есть собственные делители?...
например, для числа 12 - это 1,2,3,4,6,12?
если так, то, например, дружественные тройки - это
6 6 6
(1+2+3+6=6+6)
28 28 28
(1+2+4+7+14+28=28+28)
36 36 55
(1+2+3+4+6+9+12+18+36=55+36)
496 496 496

нашла перебором. достаточно долго, но с учетом, что нам нужна лишь 1 тройка, можно было дойти лишь до 6 - это уже достаточно быстро.
ну и, опять же, раз только одна - можно воспользоваться поиском совершенных чисел (было на форуме). 3 одинаковых совершенных числа - такая тройка.
Malice
Цитата(Zac @ 11.12.2007 14:42) *

Malice, в инете нашел тройку эту smile.gif?

Обижаешь, набросал пример.. Долго думал только над собственными делителями, в терминологии я н есилен, варианта 4 перебрал smile.gif Просто мне кажется из 2-ки в 3-ку переделать будет не сложно если приведешь код.
Такие 3-ки выходят если не включать само число в делители:
Цитата
120 120 120
672 672 672
1560 1740 1740
1980 2016 2556

Такие, если включать:
Цитата
6 6 6
28 28 28
36 36 55
496 496 496
volvo
Юля, само число не надо считать... При вычислении таких "дружественных цепочек" (amicable chains) считается сумма так называемых "proper divisors":
Цитата
A positive divisor of n which is different from n is called a proper divisor

мисс_граффити
Цитата
Юля, само число не надо считать...

спасибо. я по этому поводу и сомневалась - считать ли 1 и само число...
получается, для n=1 сумма равна 0?
Zac
Какие числа я понимаю smile.gif и как они находятся в математической части ....
А может както так -
Перебераем первое число А пока не найдем для него дружественное число - Б, если оно найдено, то Б есть сумма двух числе С+В которые дружественны А.и как то из этой суммы надо выделить эти 2 числа.. Бред какойто получился smile.gif))

Вот быстро наваял тут для двух чисел smile.gif) нооо чето не работает smile.gif) зацикливается и не выходит из програмки smile.gif

Uses CRT;
var b,d1,d2,i,a:integer;
flag1,flag2:boolean;
begin
CLRSCR;
writeln('Дружественная двойка');
flag1:=false;
flag2:=false;
a:=2;
b:=2;
d1:=0; d2:=0;
Repeat
a:=a+1;
Repeat
b:=b+1;
for i:=1 to b-1 do {Ищем норм делители для второго числа и сумируем}
if (b mod i)=0 then d1:=d1+i;
if d1=a then {если сумма норм делителей 2ого числа и первое число равны то находим обратное утверждение}
begin
for i:=1 to a-1 do
if (a mod i)=0 then d2:=d2+i;
if d2=b then {Если и сумма норм. делителей числа А совпало с числом Б то флаги тру}
begin
flag2:=true;
flag1:=true;
end;
end;

Until flag2=true;

Until flag1=true;


writeln(a,' ',b,' ',d1,' ',d2);
readln;
end.
Michael_Rybak
Перебираем А. Для А считаем сумму делителей S. Перебираем все пары (B, C) такие, что B + C = S. Для каждой такой пары проверяем два других условия.

Сумму делителей не считай каждый раз - лучше завести массив sum_of_divisors[], и заполнить его один раз вначале.
Zac
Спасиб smile.gif вопросы....
"Для каждой такой пары проверяем два других условия."
Это какие условия smile.gif? (S(B)=A+C) and (S©=A+B)
Malice
Перебор можно делать обычный, только упростить его несколькими условиями:
1. считаем все тройку чисел (A,B, C) отсортированной по возрастанию, тогда B>=A, C>=B. Тогда тройки не будут повторятся в разных комбинациях
2. при переборе B сужаем границы - слева понятно - B>=A, справа - оно меньше S(A) (ведь по условию s(a)=b+c)
3. C вообще не перебираем, оно должно быть равно S(A)-B
Дальше просто проверка на 3 условия. При таком раскладе ту тройку можно найти в в течении минуты smile.gif
Michael_Rybak
Цитата(Zac @ 11.12.2007 16:03) *

Спасиб smile.gif вопросы....
"Для каждой такой пары проверяем два других условия."
Это какие условия smile.gif? (S(B)=A+C) and (S©=A+B)

Именно так.

Malice, твои пункты 2 и 3 я подразумевал под "Перебираем все пары (B, C) такие, что B + C = S".
Zac
НУ вот сделал.. сделал специально вывод промежуточный чисел а б с .. сижу с запущеной программой минуту smile.gif число а ткоа до 160ого поменялось, В и С меняются на разные числа.... может не правильно smile.gif поправляйте.. Сори , еще раз запустил, изменив тип данных - на Интеджер вместо лОнгИнт... так быстрее перебирает А

Uses CRT;
var b,c,d3,d1,d2,j,i,a:Integer;
flag1:boolean;
begin
CLRSCR;
writeln('Ќ е®¦¤Ґ­ЁҐ ¤а㦥б⢥­­®© ва®©ЄЁ');
flag1:=false;

a:=2;
b:=2;
d1:=0; d2:=0; d3:=0;
Repeat
a:=a+1;
for i:=1 to a-1 do
if (a mod i)=0 then d1:=d1+i;
For b:=a to d1 do
begin
for j:=1 to b-1 do
if ((b mod j)=0) then d2:=d2+j;
c:=d1-b;
for i:=1 to c-1 do
if (c mod i)=0 then d3:=d3+i;
writeln(a,' ',b,' ',c);
if (d1=b+c) and (d2=a+c) and (d3=a+b) then
begin
writeln(a,' ',b,' ',c);
flag1:=true;
end;
end;
Until flag1=true;
readln;
end.
Michael_Rybak
Цитата
Сумму делителей не считай каждый раз - лучше завести массив sum_of_divisors[], и заполнить его один раз вначале.
Zac
Слушай, я этого не понимаю smile.gif как можно просчитать суммы эти заранее не зная чисел, и при том они меняются постоянно smile.gif.... если можно то подробней smile.gif
Michael_Rybak
посчитай сумму делителей для каждого числа от 1 до 10000, а потом используй.
Malice
Цитата(Zac @ 11.12.2007 18:04) *

НУ вот сделал..

В твоей программе d1,d2 и d3 обнуляются 1 раз в начале программы, а надо каждый раз перед подсчетом. Это первое что в глаза бросается. Плюс можно сделать так, что числы были разными, иначе у тебя найдется первая тройка из 120-ток.
ps зарание ничего считать не надо, цифры почти не повторяются, т.к. перебор не полный..
Zac
и правда забыл обнулят ьsmile.gif я рассеяный с улицы басеяной smile.gif

Это, теперь начиная с а=2
находит тройку но 120 240 0 .... и так всегда в конце 0, если менять a на большее значительно число.. н/п -
1740 3300 0
что не так?
Malice
Цитата(Zac @ 11.12.2007 20:45) *

что не так?

Может первый writeln убрать который до проверки условий ?
Zac
ага smile.gif точно.. сработало...
Задача решена smile.gif Спасибо всем кто помогал мне.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.