Дружественная тройка чисел |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Дружественная тройка чисел |
Zac |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 18 Пол: Мужской Репутация: 0 |
Привет, мноого времени уже ломаю голову над задачей, мне хотя бы алгоритм решения...
Задача Диксона. Будем говорить, что три натуральных числа образуют дружественную тройку, если сумма собственных делителей каждого числа равна сумме двух других чисел. Отыскать хотя бы одну дружественную тройку натуральных чисел. С дружественной двойкой я бы справился, это легко, но когда одновременно надо подобрать 3 числа..... Заранее спасибо за любую подсказку |
Malice |
Сообщение
#2
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
такая пойдет ? 1980, 2016, 2556.
А вообще показывай для двойки свой код, посмотрим |
Zac |
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 18 Пол: Мужской Репутация: 0 |
Malice, в инете нашел тройку эту ?
Кода для двойки нет но впринцепи знаю как реализовать... Скажите как это как в алгоритме будет выглядеть.... как я вижу числа могут быть в большом разбросе |
мисс_граффити |
Сообщение
#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 одинаковых совершенных числа - такая тройка. -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
Malice |
Сообщение
#5
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
Malice, в инете нашел тройку эту ? Обижаешь, набросал пример.. Долго думал только над собственными делителями, в терминологии я н есилен, варианта 4 перебрал Просто мне кажется из 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 - |
volvo |
Сообщение
#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? -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
Zac |
Сообщение
#8
|
Новичок Группа: Пользователи Сообщений: 18 Пол: Мужской Репутация: 0 |
Какие числа я понимаю и как они находятся в математической части ....
А может както так - Перебераем первое число А пока не найдем для него дружественное число - Б, если оно найдено, то Б есть сумма двух числе С+В которые дружественны А.и как то из этой суммы надо выделить эти 2 числа.. Бред какойто получился )) Вот быстро наваял тут для двух чисел ) нооо чето не работает ) зацикливается и не выходит из програмки Uses CRT; Сообщение отредактировано: Zac - |
Michael_Rybak |
Сообщение
#9
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Перебираем А. Для А считаем сумму делителей S. Перебираем все пары (B, C) такие, что B + C = S. Для каждой такой пары проверяем два других условия.
Сумму делителей не считай каждый раз - лучше завести массив sum_of_divisors[], и заполнить его один раз вначале. |
Zac |
Сообщение
#10
|
Новичок Группа: Пользователи Сообщений: 18 Пол: Мужской Репутация: 0 |
Спасиб вопросы....
"Для каждой такой пары проверяем два других условия." Это какие условия ? (S(B)=A+C) and (S©=A+B) |
Malice |
Сообщение
#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 условия. При таком раскладе ту тройку можно найти в в течении минуты |
Michael_Rybak |
Сообщение
#12
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
|
Zac |
Сообщение
#13
|
Новичок Группа: Пользователи Сообщений: 18 Пол: Мужской Репутация: 0 |
НУ вот сделал.. сделал специально вывод промежуточный чисел а б с .. сижу с запущеной программой минуту число а ткоа до 160ого поменялось, В и С меняются на разные числа.... может не правильно поправляйте.. Сори , еще раз запустил, изменив тип данных - на Интеджер вместо лОнгИнт... так быстрее перебирает А
Uses CRT; Сообщение отредактировано: Zac - |
Michael_Rybak |
Сообщение
#14
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата Сумму делителей не считай каждый раз - лучше завести массив sum_of_divisors[], и заполнить его один раз вначале. |
Zac |
Сообщение
#15
|
Новичок Группа: Пользователи Сообщений: 18 Пол: Мужской Репутация: 0 |
Слушай, я этого не понимаю как можно просчитать суммы эти заранее не зная чисел, и при том они меняются постоянно .... если можно то подробней
|
Michael_Rybak |
Сообщение
#16
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
посчитай сумму делителей для каждого числа от 1 до 10000, а потом используй.
|
Malice |
Сообщение
#17
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
НУ вот сделал.. В твоей программе d1,d2 и d3 обнуляются 1 раз в начале программы, а надо каждый раз перед подсчетом. Это первое что в глаза бросается. Плюс можно сделать так, что числы были разными, иначе у тебя найдется первая тройка из 120-ток. ps зарание ничего считать не надо, цифры почти не повторяются, т.к. перебор не полный.. Сообщение отредактировано: Malice - |
Zac |
Сообщение
#18
|
Новичок Группа: Пользователи Сообщений: 18 Пол: Мужской Репутация: 0 |
и правда забыл обнулят ь я рассеяный с улицы басеяной
Это, теперь начиная с а=2 находит тройку но 120 240 0 .... и так всегда в конце 0, если менять a на большее значительно число.. н/п - 1740 3300 0 что не так? |
Malice |
Сообщение
#19
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
|
Zac |
Сообщение
#20
|
Новичок Группа: Пользователи Сообщений: 18 Пол: Мужской Репутация: 0 |
ага точно.. сработало...
Задача решена Спасибо всем кто помогал мне. |
Текстовая версия | 29.03.2024 18:56 |