ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / НОД трех чисел
11 сообщений из 11, страница 1 из 1
НОД трех чисел
    #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:04
| Ответить | Цитировать | Написать  
НОД трех чисел
    #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:20
| Ответить | Цитировать | Написать  
НОД трех чисел
    #39094631
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ванмомас намбаван
Участник
miksoft,так я все по сути делаю правильно,в чем может быть причина того что не заходят все тесты?
...
Рейтинг: 0 / 0
04.11.2015, 20:26
| Ответить | Цитировать | Написать  
НОД трех чисел
    #39094635
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
ванмомас намбаванв чем может быть причина того что не заходят все тесты?Приведите пример конкретных чисел, для которых результат неправильный.
...
Рейтинг: 0 / 0
04.11.2015, 20:29
| Ответить | Цитировать | Написать  
НОД трех чисел
    #39094648
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ванмомас намбаван
Участник
miksoft,к сожалению тесты на закрытом сервере и они мне не известны.
...
Рейтинг: 0 / 0
04.11.2015, 20:43
| Ответить | Цитировать | Написать  
НОД трех чисел
    #39094700
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
ванмомас намбаван,

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

Возможно, Ваш алгоритм НОД для 2х чисел неверен. Что получается для НОД(3,12)?
...
Рейтинг: 0 / 0
04.11.2015, 23:17
| Ответить | Цитировать | Написать  
НОД трех чисел
    #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:01
| Ответить | Цитировать | Написать  
НОД трех чисел
    #39094781
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
x1ca4064ванмомас намбаванв чем может быть причина того что не заходят все тесты?

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


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

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


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