Форум программистов, компьютерный форум CyberForum.ru

Задача на НОД,НОК - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 5.00
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 00:09     Задача на НОД,НОК #1
Вокруг звезды вращается n планет. Тангенциальная скорость планет постоянна. Направление вращений планет одинаково. Парадом планет называется момент времени, в который все планеты располагаются на одной прямой. Необходимо вычислить промежуток времени между последовательными парадами планет.За заданным количеством планет n вычислить n чисел – периоды вращения планет.

Создал алгоритм математически, но не знаю, как его реализовать на С++.
Такой вот алгоритм:Рассмотрим i - ую и j - ую планету. Они вместе с солнцем будут находиться на одной прямой через время t, если

Здесь через {x} обозначена дробная часть числа x.
Или то же самое, что значение

является целым. Поскольку i и j – любые значения от 1 до n, то можно утверждать, что число
K =
должно быть целым. Если в качестве t взять значение a / b, где
a = НОК(t1, t2, …, tn), b = 2 * НОД(t1 – t0, t2 – t0, …, tn – t0),
то значение K будет целым. Переменной t0 следует присвоить наименьшее значение из ti. Осталось сократить дробь a / b на их наибольший общий делитель.

Покажем, как вычислить a = НОК(t1, t2, …, tn), совершив минимум операций над большими числами (значение а является большим). Переберем все пары (ti, tj), i < j , для каждой пары вычислим d = НОД(ti, tj), после чего разделим tj на d. После этого произведение оставшихся ti равно значению а.
Изображения
 
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.03.2012, 04:37     Задача на НОД,НОК #2
Джон, вопрос-то в чем? То что нужно вычислить
Цитата Сообщение от Джон Посмотреть сообщение
a = НОК(t1, t2, …, tn)
тут Вы правы.
А то как Вы это делаете:
Цитата Сообщение от Джон Посмотреть сообщение
Переберем все пары (ti, tj), i < j , для каждой пары вычислим d = НОД(ti, tj), после чего разделим tj на d. После этого произведение оставшихся ti равно значению а.
не понятно.
Если вопрос именно в этом, то лучше в ручную распишите, как вычисляете НОК(3,4,5,6).
Также напишите максимально возможное n и ti.
Если есть ссылка на задачу, то лучше лучше укажите ссылку.
alekola
 Аватар для alekola
21 / 21 / 1
Регистрация: 04.08.2011
Сообщений: 103
07.03.2012, 07:36     Задача на НОД,НОК #3
Эм, честно не уверен но вроде ссылки за форум разрешены.
Вообщем у меня на сайте есть функции для нахождения НОД и НОК,
можете поглядеть http://www.kolesnikov-dv.ru/?p=49 все с комментариями
denys_l
51 / 51 / 4
Регистрация: 26.09.2011
Сообщений: 186
07.03.2012, 11:12     Задача на НОД,НОК #4
Мне кажется, что здесь ещё формулы должны были быть, которые по каким-то причинам не отобразились.... Надо бы обновить
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
07.03.2012, 11:48     Задача на НОД,НОК #5
Цитата Сообщение от Джон Посмотреть сообщение
Вокруг звезды вращается n планет. Тангенциальная скорость планет постоянна. Направление вращений планет одинаково. Парадом планет называется момент времени, в который все планеты располагаются на одной прямой. Необходимо вычислить промежуток времени между последовательными парадами планет.За заданным количеством планет n вычислить n чисел – периоды вращения планет.

Создал алгоритм математически, но не знаю, как его реализовать на С++.
Такой вот алгоритм:Рассмотрим i - ую и j - ую планету. Они вместе с солнцем будут находиться на одной прямой через время t, если

Здесь через {x} обозначена дробная часть числа x.
Или то же самое, что значение

является целым. Поскольку i и j – любые значения от 1 до n, то можно утверждать, что число
K =
должно быть целым. Если в качестве t взять значение a / b, где
a = НОК(t1, t2, …, tn), b = 2 * НОД(t1 – t0, t2 – t0, …, tn – t0),
то значение K будет целым. Переменной t0 следует присвоить наименьшее значение из ti. Осталось сократить дробь a / b на их наибольший общий делитель.

Покажем, как вычислить a = НОК(t1, t2, …, tn), совершив минимум операций над большими числами (значение а является большим). Переберем все пары (ti, tj), i < j , для каждой пары вычислим d = НОД(ti, tj), после чего разделим tj на d. После этого произведение оставшихся ti равно значению а.
во первых:слишком много пар сравнивается, во вторых: так нельзя НОК всех чисел найти
1) НОК (a,b,c,d,e ...) = НОК( НОК(a,b) , c,d,e ...) или НОК ( НОК(a,b), НОК(c,d,e ...))
2) если планеты i,j - на одной линии с солнцем, i,k - на одной линии с солнцем, тогда j,k на одной линии с солнцем и их не надо проверять
т.е. достаточно выбрать жертву(допустим ближайшая планета), а остальные должны быть на одной линии с ней и с солнцем

т.е. алгоритм совсем простой
надо найти HOK(L,t2-t1,t3-t1,...,tn-t1),
L-Pi радиан или 180° или 200 градиан или что там еще?
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 12:49  [ТС]     Задача на НОД,НОК #6
Так выглядит задача, если я как-то неправильно поставил ее условие.
http://www.e-olimp.com.ua/problems/1185
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.03.2012, 13:32     Задача на НОД,НОК
Еще ссылки по теме:

Вычисление нок и нод переменных натуральных чисел C++
C++ Вычисление НОД и НОК
Разработать класс "Cmp", обеспечивающий нахождение НОД и НОК двух чисел C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
07.03.2012, 13:32     Задача на НОД,НОК #7
Цитата Сообщение от Джон Посмотреть сообщение
Так выглядит задача, если я как-то неправильно поставил ее условие.
http://www.e-olimp.com.ua/problems/1185
теперь я даже не представляю что ты там писал, есть кстати предпросмотр когда мессдж отправляешь
вот в цитате предыдущей видно, что ты запостил, и не видно, что ты хотел этим сказать
после всяких "если" "значение" "К=" следует пустота
Yandex
Объявления
07.03.2012, 13:32     Задача на НОД,НОК
Ответ Создать тему
Опции темы

Текущее время: 15:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru