Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / НОД трех чисел / 11 сообщений из 11, страница 1 из 1
04.11.2015, 20:04
    #39094617
ванмомас намбаван
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
У меня есть алгоритм для НОД 2х чисел :
Код: c#
1.
2.
3.
4.
5.
6.
static int nod(int a, int b)
        {
            if (b == 0)
                return a;
            return nod(b, a % b);
        }


Если для 3х чисел сделать так :
Код: c#
1.
2.
int k = nod(a, b);
Console.WriteLine(nod(k, c));


То оно не для всех тестов зайдет.Даже если к это НОД двух меньших чисел.
Есть у кого на примете алгоритм для НОД трех чисел?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.11.2015, 20:20
    #39094627
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
ванмомас намбаван,

Вы в поиске были?
Первая же ссылка в яндексе:
http://www.cleverstudents.ru/divisibility/nod_finding.html мы сформулировали и доказали теорему: наибольший общий делитель нескольких чисел a1, a2, …, ak равен числу dk, которое находится при последовательном вычислении НОД(a1, a2)=d2, НОД(d2, a3)=d3, НОД(d3, a4)=d4, …, НОД(dk-1, ak)=dk.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.11.2015, 20:26
    #39094631
ванмомас намбаван
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
miksoft,так я все по сути делаю правильно,в чем может быть причина того что не заходят все тесты?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.11.2015, 20:29
    #39094635
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
ванмомас намбаванв чем может быть причина того что не заходят все тесты?Приведите пример конкретных чисел, для которых результат неправильный.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.11.2015, 20:43
    #39094648
ванмомас намбаван
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
miksoft,к сожалению тесты на закрытом сервере и они мне не известны.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.11.2015, 22:11
    #39094700
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
ванмомас намбаван,

Проведите свои.
Или найдите другой алгоритм, сравните результаты с ним.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.11.2015, 23:17
    #39094736
x1ca4064
x1ca4064
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
ванмомас намбаванв чем может быть причина того что не заходят все тесты?

Возможно, Ваш алгоритм НОД для 2х чисел неверен. Что получается для НОД(3,12)?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.11.2015, 02:01
    #39094774
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
Почему вы возвращаете static int ?

Попробуйте так:
Код: plaintext
1.
2.
3.
4.
5.
int gcd(int a,int b)
{
   if(b==0) return a;
   return gcd(b,a-b*(int)floor(a/b);
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.11.2015, 02:50
    #39094781
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
x1ca4064ванмомас намбаванв чем может быть причина того что не заходят все тесты?

Возможно, Ваш алгоритм НОД для 2х чисел неверен. Что получается для НОД(3,12)?
алгоритм не его, а Евклида :) но я не уверен что для отрицательных чисел a%b будет работать так, как полагал Евклид.
ванмомас намбаван, если вариант предложенный выше не подойдёт, попробуйте предварительно обработать входные параметры(создайте функцию-обёртку) таким образом, чтобы числа были неотрицательные.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.11.2015, 05:44
    #39094800
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
ванмомас намбаванЕсли для 3х чисел сделать так :
Код: c#
1.
2.
int k = nod(a, b);
Console.WriteLine(nod(k, c));


То оно не для всех тестов зайдет.Даже если к это НОД двух меньших чисел.
Есть у кого на примете алгоритм для НОД трех чисел?
Привиди пример из трех чисел для которых этот код не сработает.

ИМХУ Ты не там ошибку ищешь.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.11.2015, 21:45
    #39097047
ванмомас намбаван
ванмомас намбаван
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НОД трех чисел
Все очень просто,надо брать модуль)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / НОД трех чисел / 11 сообщений из 11, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 395ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1340885]:
 0ms
get settings:
 6ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 130ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 28ms
get tp. blocked users:
 1ms
others: 207ms
total:  395ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]