Алгоритм Евклида
HTML-код
- Опубликовано: 6 сен 2015
- Алгоритм Евклида для нахождения НОД двух целых чисел.
Поддержать Проект: donationalerts.ru/r/valeryvolkov
Мои занятия в Скайпе: id224349278
Новая Группа ВКонтакте: volkovvalery
Наибольший общий делитель. Математика 5-6 классы. Урок 15.
Поскольку Евклид лично объяснить свой алгоритм уже не может, то он с благодарностью наблюдает, как Вы это замечательно делаете вместо него)). Спасибо!
Хахаха. Евклид радуется
19 лет, заканчиваю первый курс и только благодаря вашему видео понял алгоритм Евклида...
Это грустно
@@user-cb1ix4hr6w грустно, что понял?
@@dom1noof грустно, что только сейчас
И снова я возвращаюсь к этому видео. Каждый раз как в первый смотрю.
5:47 начало
отличное объяснение! спасибо большое!
😀
Спасибо за полезное, нужное видео.
Просто супер!
POPUSK
Спасибо!
Спасибо огромное) Очень помогли😊
POPUSK
Браво. Понятно объясняете
Спасибо, помогли!
давайте еще 20 раз в процессе видео скажем "Алгоритм Евклида для НОД двух целых чисел"
А если нужно найти нод сразу трех чисел?
спс все понятно
Дякую
11 сентября 2022. урок 17 selfedu
Не понравилось мне доказательство. При этом не доказано, что все общие делители у обоих пар чисел одинаковы.
Вот моё доказательство. Числа a и b можно представить как разложение на простые числа. Тогда очевидно их НОД будет равен произведению совпадающих простых чисел, а комбинации из этих совпадающих простых чисел будут представлять общие делители, т.е. в НОДе спрятаны общие делители. В этом случае a=НОД*q1, а b=НОД*q2, а вторая пара чисел будет равна: a-b =НОД*(q1-q2) и b=НОД*q2
Отсюда видно, что у новой пары как минимум те же самые общие делители, что и у чисел a и b.
Но теперь нужно проверить, не появились ли у новой пары какие-то дополнительные общие делители. Если бы они были, то у чисел (q1-q2) и q2 можно было бы выделить какой-то общий делитель m, отличный от 1. Но тогда с учётом этого общего делителя числа a-b и b приняли бы следующий вид:
a-b =НОД*m*q` (*) и b=НОД*m*q2`
И тогда из (*) a = b + НОД*m*q` = НОД*m*q2` + НОД*m*q` = НОД*m*(q2`+q`)
Т.е. a = НОД*m*(q2`+q`), а b=НОД*m*q2`
Пришли к противоречию, т.к. у чисел a и b появился дополнительный общий множитель, которого изначально не было.
спасибо большое, с вашим объяснением стало намного понятнее
А по какому принципу находится НОД 4х и более цифр?
Очень просто. Выбираешь из чисел подходящую пару и ищешь их НОД.
Пусть у тебя есть числа a, b, c, d, тогда чтобы найти их нод для начала найдём нод(a, b) = x. Потом нод(x, c) = y, и наконец нод(y, d) = z. Число z и является искомым нод(a, b, c, d). Для большего числа чисел просто продолжаете данную закономерность
Объясните для чего это нужно знать? Пожалуйста🙏
Нужно для решения Диофантовых уравнений. А также в задачах по программированию будут попадаться
Без НОД не обойтись при решении примеров по умножению и делению дробных чисел. Вспомните математику для 6 класса😉
если вы задаетесь этим вопросом, то вам это не нужно
a и b могут быть любыми целыми, равенство НОД(а, b) = НОД(a-b, b) сохраняется
POPUSK
Ничего не понимаю
Где доказательство?
Так он же доказал, когда говорил, что все общие делители этих двух НОД совпадают
а если надо найти НОД (100110; 3) ?....
Грек бы вспотел, пока подсчитал....
Сумма цифр первого числа делится на 3, а значит и само число делится на 3, поэтому НОД(100110; 3)=3.
@@ValeryVolkov эээ какой Вы хитренький... ))))
ну это - понятно. You are a human.
НО... алгоритм НЕ проверяет делимость на 3 таким способом и пойдёт длинным путём.... очень длинным....
я когда-то, ещё в школе будучи, видел ещё способ, похожий на этот, только там было в основе получение и проверка остатка от деления..... алгоритм гораздо короче и эффективнее... а вот кого на что делили -- это уже седая старина, я уже не помню... ))
Алгоритм работает очень быстро, например, можно поделить большее число на меньшее с остатком и вычесть целую часть частного из большего числа.
@@ValeryVolkov вполне возможно, что так нам и давали этот способ. я 30 лет назад ушёл в сисадмины и математика меня стала мало касаться, а потому из памяти постепенно вытирается... ((
вот поэтому и стал часто смотреть Ваши передачи, немного мозги встряхнуть с ЭТОЙ стороны, математической....
Алгоритм можно ускорить, используя следующие тождества:
1. НОД двех четных чисел равен удвоенному НОД их половин:
НОД(2m,2n)=2*НОД(m,n)
2. НОД нечетного и четного числа равен НОД нечетного и половины четного:
НОД(2m+1,2n)=НОД(2m+1,n)
Алгоритм будет такой:
1. Даны два числа, a и b
2. Временная переменная n = 0
3. Пока a и b четные, выполняем a = a>>1, b = b>>1, ++n
4. Если a==b, то НОД=(a >1
6. Пока b четное, выполняем b = b>>1
7. Наибольшее из a и b заменяем на их разность, как и в алгоритме Евклида.
8. Перейти к 4
Это только схема. Можно ещё ускорить. Удобно использовать в программах для микропроцессоров, у которых нет команды деления.
В Вашем примере это будет примерно так:
a = 11000011100001110 100110
b = 00000000000000011 3
-----
a = 01100001110000111 50055
b = 00000000000000011
-----
a = 00011000011100001 12513
b = 00000000000000011
-----
a = 00001100001101111 6255
b = 00000000000000011
-----
a = 00000011000011011 1563
b = 00000000000000011
-----
a = 00000000011000011 195
b = 00000000000000011
-----
a = 00000000000000011 3
b = 00000000000000011
а этот алгоритм работает с 3 или более числами?
Если ни ошибаюсь, то ты сначала находишь НОД первых двух чисел (назовем его Z), а потом находишь НОД третьего числа и Z, и так далее
Очень просто. Выбираешь в ряду подходящую пару и ищешь их НОД. Убедись - алгоритм работает.
@@user-jz7kj6vd8n Ты не прав, контрпример 9 9 16, по твоему методу ты выберешь 2 девятки и скажешь что НОД трех чисел = девять, хотя на самом деле НОД (9, 9, 16) равно 1․
@@levonaghamalyan1195 Ваш пример некорректен, по той простой причине, что эти числа одинаковы. Их НОД = 9, по определению наибольшего делителя числа. Числа: 16 и 9 - взаимно простые. Их НОД = 1, по определению НОД взаимно простых чисел. Никакие алгоритмы здесь не нужны.
@@user-jz7kj6vd8n Вы же сами сказали "Выбрать из чисел два наименьших и найти их НОД". Если Вас раздражает то что в моем примере есть одинаковые числа, вот Вам еще один ։ НОД (9, 15, 32)․ Считаю НОД двух наименьших, как Вы и сказали ։ НОД (9, 15) = 3, но НОД (9, 15, 32) = 1. Возможно, я Вас просто не понимаю, но НОД множества находят не так как Вы описывали в своем комментарии․
Программирование прям какое то
Ну да
a = int(input("Введи число: "))
b = int(input("Введи число: "))
while a != 0 and b != 0:
if a > b:
a = a % b
else:
b = b % a
print(a+b)
@@redex9953 капец 10 месяцов прошло
Ничего не понятно...
POPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSKPOPUSK
По этому принципу никак не могу найти нод чисел 154 и 210. Ну или я что-то неправильно делаю
lamia Посчитал по этому алгоритму. Вышло 14
Amelia Haylee , да, я уже разобралась. Спасибо;)
@UC3o12_qXwX_55jA14Khm52Q (154; 210-154);. (56; 154);. (56, 154-56);. (98, 56);. (56; 98-56);. (56, 42); (42; 56-42); (14, 42); (14, 28); (14,14)
А как алгоритм этот работает для чисел 23 и 11? Ерунда полная!
Это взаимнопростые числа. Их общий делитель будет 1.
@@krenciak надо было оговорить этот момент
23-11 ; 11. НОД 12 и 11? Правильно, 1.
Вычитаешь, пока не получится 1=1
@@user-bh2ky9yo1m М-да...