Виж темите без отговор | Виж активните теми Дата и час: 28.03.2024 13:21



Отговори на тема  [ 10 мнения ] 
НОД на повече от две числа 
Автор Съобщение
(The Grizzlies)
Аватар

Регистриран на: 23.08.2012 08:02
Мнения: 10353
Местоположение: Augusta Vindelicorum
Отговори с цитат
Мнение  НОД на повече от две числа   |   07.01.2016 12:58


Откривам новия подфорум с едно питане от сферата на математиката.

Има ли изобщо някакъв алгоритъм, формула или изобщо нещо подобно за намирането на най-голям общ делител (НОД) на повече от две числа?

Или с други дум, иде реч за екселската функция GCD (Greatest Common Divisor).

Проблемът е, че си говорим за тест без достъп до ексел, т.е. само сметки с лист и химикалка + джобен калкулатор. Освен това числата са между четири- и седемцифрени. :safin: :outofspace: :helpless:

Евклидовият алгоритъм е що-годе ок, но само за две числа. При повече от две числа по принцип могат посредством този алгоритъм да се намерят НОДовете за всяка една двойка числа от групата (примерно за a,b, и c съответно НОД(a,b), НОД(a,c), НОД(b,c)), но оттам нататък (поне аз и поне засега) я карам с хамалогия и стъкмистика.

Някакви познания/идеи/предложения?

Мерси на всички предварително!

_________________
GREEN AND GOLD 'TIL THE CLUB IS SOLD!


 
(Крива Нива)
Аватар

Регистриран на: 20.05.2012 18:28
Мнения: 9586
Отговори с цитат
Мнение  Re: НОД на повече от две числа   |   10.01.2016 13:44


Алгоритми има - примерно алгоритъм на Евклид:

https://bg.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D1%8A%D0%BC_%D0%BD%D0%B0_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4

Универсална формула обаче няма, доколкото съм запознат.

_________________
Изображение


 
(The Grizzlies)
Аватар

Регистриран на: 23.08.2012 08:02
Мнения: 10353
Местоположение: Augusta Vindelicorum
Отговори с цитат
Мнение  Re: НОД на повече от две числа   |   10.01.2016 13:52


bai Momchil написа:
Алгоритми има - примерно алгоритъм на Евклид:

https://bg.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D1%8A%D0%BC_%D0%BD%D0%B0_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4

Универсална формула обаче няма, доколкото съм запознат.

Вече споменах, че алгоритъма на Евклид го знам, но той, както и всички останали, е само за две числа. Екселската формула GCD, както всички други формули, трябва да базира на някакъв алгоритъм. Ето този ако мога да намеря...

_________________
GREEN AND GOLD 'TIL THE CLUB IS SOLD!


 
(Крива Нива)
Аватар

Регистриран на: 20.05.2012 18:28
Мнения: 9586
Отговори с цитат
Мнение  Re: НОД на повече от две числа   |   10.01.2016 13:58


SUBXERO написа:
bai Momchil написа:
Алгоритми има - примерно алгоритъм на Евклид:

https://bg.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D1%8A%D0%BC_%D0%BD%D0%B0_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4

Универсална формула обаче няма, доколкото съм запознат.

Вече споменах, че алгоритъма на Евклид го знам, но той, както и всички останали, е само за две числа. Екселската формула GCD, както всички други формули, трябва да базира на някакъв алгоритъм. Ето този ако мога да намеря...


Може пак да използваш Евклид, като започнеш с 2 числа, после намираш НОД на НОД-а от първите 2 с третото и т.н.

_________________
Изображение


 
(Крива Нива)
Аватар

Регистриран на: 20.05.2012 18:28
Мнения: 9586
Отговори с цитат
Мнение  Re: НОД на повече от две числа   |   10.01.2016 14:01


Като гугълнеш малко точно същото казват хората:

The GCD of 3 numbers can be computed as gcd(a, b, c) = gcd(gcd(a, b), c).

:cheers:

_________________
Изображение


 
(The Grizzlies)
Аватар

Регистриран на: 23.08.2012 08:02
Мнения: 10353
Местоположение: Augusta Vindelicorum
Отговори с цитат
Мнение  Re: НОД на повече от две числа   |   10.01.2016 14:06


Това ми беше една от идеите по принцип, но ми се стори рискована и я отхвърлих. Ти сигурен ли си в този метод или просто предполагаш?

Другата ми идея я споделих по-горе - да намеря НОДа на всяка една двойка числа и после евентуално техния НОД, което обаче (засега) става с налучкване.

_________________
GREEN AND GOLD 'TIL THE CLUB IS SOLD!


 
(The Grizzlies)
Аватар

Регистриран на: 23.08.2012 08:02
Мнения: 10353
Местоположение: Augusta Vindelicorum
Отговори с цитат
Мнение  Re: НОД на повече от две числа   |   10.01.2016 14:08


Ясно, значи е изпитан метод. Много мерси! :cheers:

_________________
GREEN AND GOLD 'TIL THE CLUB IS SOLD!


 
(Крива Нива)
Аватар

Регистриран на: 20.05.2012 18:28
Мнения: 9586
Отговори с цитат
Мнение  Re: НОД на повече от две числа   |   10.01.2016 14:17


SUBXERO написа:
Това ми беше една от идеите по принцип, но ми се стори рискована и я отхвърлих. Ти сигурен ли си в този метод или просто предполагаш?

Другата ми идея я споделих по-горе - да намеря НОДа на всяка една двойка числа и после евентуално техния НОД, което обаче (засега) става с налучкване.


Ако го правиш програмно, слагаш всичките числа в един масив и правиш следното:

nod = number[0];

loop (тук ти е цикъла въртиш го от 1 до дължината на масива) {

nod = gcd(nod, number[i]) - тук gcd ти функцията за НОД по алгоритъма на Евклид

}

и тва трябва да е. Като ти свърши цикъла nod ще ти е резултата.

_________________
Изображение


Последна промяна bai Momchil на 10.01.2016 14:20, променена общо 1 път



 
(The Grizzlies)
Аватар

Регистриран на: 23.08.2012 08:02
Мнения: 10353
Местоположение: Augusta Vindelicorum
Отговори с цитат
Мнение  Re: НОД на повече от две числа   |   10.01.2016 14:29


Момчи, що не четеш бе, човек? Ставаше дума за тест с лист, химикалка и джобен калкулатор (без функции). Всичко останало е осъществимо.

Мерси все пак за идеите. Може някога някому да потрябват. Затова са тези форуми в крайна сметка.

_________________
GREEN AND GOLD 'TIL THE CLUB IS SOLD!


 
(Крива Нива)
Аватар

Регистриран на: 20.05.2012 18:28
Мнения: 9586
Отговори с цитат
Мнение  Re: НОД на повече от две числа   |   10.01.2016 14:52


SUBXERO написа:
Момчи, що не четеш бе, човек? Ставаше дума за тест с лист, химикалка и джобен калкулатор (без функции). Всичко останало е осъществимо.

Мерси все пак за идеите. Може някога някому да потрябват. Затова са тези форуми в крайна сметка.



Хахахах сори :)

Ама и на лист да е алгоритъма е същият ;)

_________________
Изображение


 
Покажи мненията от миналия:  Сортирай по  
Отговори на тема   [ 10 мнения ] 

Кой е на линия

Потребители разглеждащи този форум: 0 регистрирани и 1 госта


Вие не можете да пускате нови теми
Вие не можете да отговаряте на теми
Вие не можете да променяте собственото си мнение
Вие не можете да изтривате собствените си мнения

Търсене:
Иди на:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware for PTF.
Хостинг