IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Дружественная тройка чисел
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 18
Пол: Мужской

Репутация: -  0  +


Привет, мноого времени уже ломаю голову над задачей, мне хотя бы алгоритм решения...

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

С дружественной двойкой я бы справился, это легко, но когда одновременно надо подобрать 3 числа.....
Заранее спасибо за любую подсказку
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


такая пойдет ? 1980, 2016, 2556.
А вообще показывай для двойки свой код, посмотрим smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 18
Пол: Мужской

Репутация: -  0  +


Malice, в инете нашел тройку эту smile.gif?
Кода для двойки нет smile.gif но впринцепи знаю как реализовать...
Скажите как это как в алгоритме будет выглядеть.... как я вижу числа могут быть в большом разбросе sad.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


что есть собственные делители?...
например, для числа 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 одинаковых совершенных числа - такая тройка.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(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


Сообщение отредактировано: Malice -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






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

 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

спасибо. я по этому поводу и сомневалась - считать ли 1 и само число...
получается, для n=1 сумма равна 0?


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 18
Пол: Мужской

Репутация: -  0  +


Какие числа я понимаю 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.


Сообщение отредактировано: Zac -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Перебираем А. Для А считаем сумму делителей S. Перебираем все пары (B, C) такие, что B + C = S. Для каждой такой пары проверяем два других условия.

Сумму делителей не считай каждый раз - лучше завести массив sum_of_divisors[], и заполнить его один раз вначале.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Новичок
*

Группа: Пользователи
Сообщений: 18
Пол: Мужской

Репутация: -  0  +


Спасиб smile.gif вопросы....
"Для каждой такой пары проверяем два других условия."
Это какие условия smile.gif? (S(B)=A+C) and (S©=A+B)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Перебор можно делать обычный, только упростить его несколькими условиями:
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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(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".
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 18
Пол: Мужской

Репутация: -  0  +


НУ вот сделал.. сделал специально вывод промежуточный чисел а б с .. сижу с запущеной программой минуту 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.


Сообщение отредактировано: Zac -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Сумму делителей не считай каждый раз - лучше завести массив sum_of_divisors[], и заполнить его один раз вначале.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 18
Пол: Мужской

Репутация: -  0  +


Слушай, я этого не понимаю smile.gif как можно просчитать суммы эти заранее не зная чисел, и при том они меняются постоянно smile.gif.... если можно то подробней smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


посчитай сумму делителей для каждого числа от 1 до 10000, а потом используй.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Zac @ 11.12.2007 18:04) *

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

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

Сообщение отредактировано: Malice -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Новичок
*

Группа: Пользователи
Сообщений: 18
Пол: Мужской

Репутация: -  0  +


и правда забыл обнулят ьsmile.gif я рассеяный с улицы басеяной smile.gif

Это, теперь начиная с а=2
находит тройку но 120 240 0 .... и так всегда в конце 0, если менять a на большее значительно число.. н/п -
1740 3300 0
что не так?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Zac @ 11.12.2007 20:45) *

что не так?

Может первый writeln убрать который до проверки условий ?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Новичок
*

Группа: Пользователи
Сообщений: 18
Пол: Мужской

Репутация: -  0  +


ага smile.gif точно.. сработало...
Задача решена smile.gif Спасибо всем кто помогал мне.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 18:56
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name