Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 5.00
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
#1

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

07.03.2012, 00:09. Просмотров 3097. Ответов 6
Метки нет (Все метки)

Вокруг звезды вращается 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 равно значению а.
0
Изображения
 
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.03.2012, 00:09
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача на НОД,НОК (C++):

НОК и НОД - C++
Здоров Всем ! Вот условие : Определить функцию для нахождения наименьшего общего кратного (НОК) и наибольшего общего...

НОК НОД - C++
Можно ли использовать такой код для нахождения НОК НОД? #include &lt;iostream&gt; #include &lt;conio.h&gt; using std::cout; using std::cin; ...

НОД и НОК - C++
Дан НОД и НОК надо найти каким числом они (НОД и НОК) принадлежат

Вычисление НОД и НОК - C++
Нужно написать программу по вычислению НОД и НОК. Мысли проскакивают, но не полное решение). Подскажите кто сможет, только не кидайте...

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

Нахождение НОД и НОК двух чисел - C++
Вот код программы на Паскале нужно переделать на С++ { Рекурсивные алгоритмы: нахождения НОД и НОК двух чисел } var a,b:longint; ...

6
valeriikozlov
Эксперт С++
4675 / 2501 / 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.
Если есть ссылка на задачу, то лучше лучше укажите ссылку.
0
alekola
21 / 21 / 1
Регистрация: 04.08.2011
Сообщений: 103
07.03.2012, 07:36 #3
Эм, честно не уверен но вроде ссылки за форум разрешены.
Вообщем у меня на сайте есть функции для нахождения НОД и НОК,
можете поглядеть http://www.kolesnikov-dv.ru/?p=49 все с комментариями
0
denys_l
52 / 52 / 4
Регистрация: 26.09.2011
Сообщений: 186
07.03.2012, 11:12 #4
Мне кажется, что здесь ещё формулы должны были быть, которые по каким-то причинам не отобразились.... Надо бы обновить
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 12:49  [ТС] #6
Так выглядит задача, если я как-то неправильно поставил ее условие.
http://www.e-olimp.com.ua/problems/1185
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
07.03.2012, 13:32 #7
Цитата Сообщение от Джон Посмотреть сообщение
Так выглядит задача, если я как-то неправильно поставил ее условие.
http://www.e-olimp.com.ua/problems/1185
теперь я даже не представляю что ты там писал, есть кстати предпросмотр когда мессдж отправляешь
вот в цитате предыдущей видно, что ты запостил, и не видно, что ты хотел этим сказать
после всяких "если" "значение" "К=" следует пустота
0
07.03.2012, 13:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.03.2012, 13:32
Привет! Вот еще темы с ответами:

Вычисление нок и нод переменных натуральных чисел - C++
Здравствуйте. Искал подобную тему по форуму, но там все либо на 2 числа либо на несколько, но с фиксированным числом после компиляции....

Функция нахождения НОК, НОД и демонстрация вывода - C++
1)Написать функцию для нахождения НОК двух целых чисел. Написать фукнцию для нахождения НОД двух целых чисел. Написать программу...

Название задачи: Коробки (Тема НОД, НОК) - C++
Тестирующая система e-olimp.com , ни один тест не проходит. ------------------------------- Коробки Есть две коробки. В первой...

Найти НОК и НОД , и что бы можно было ввести до 10 чисел , как это сделать на с++? - C++
Здравствуйте , мне нужно найти НОК и НОД , и что бы можно было ввести до 10 чисел , как это можно реализовать на языке С++?


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.