Алгоритм Евклида

Алгоритм Евклида для нахождения наибольшего общего делителя. Даны два отрезка — и надо найти наибольший отрезок, которому кратны оба данных отрезка. Алгоритм Евклида — это большее делим на меньшее, а потом меньшее на остаток. Сначала больший отрезок делим на меньший.
Замеряю меньший отрезок и откладываю меньший на большем — получается один целый кусочек и остаток.
150 / 96 = 1 ост 54
Замеряю остаток и откладываю на меньшем отрезке. Получается опять один целый кусочек и остаток.
96 / 54 = 1 ост 42
Замеряю остаток и откладываю на предыдущем остатке. Получается опять один целый кусочек и остаток.
54 / 42 = 1 ост 12
Замеряю остаток и откладываю на предыдушем остатке. Получается три целых кусочка и остаток.
42 / 12 = 3 ост 6
Замеряю остаток и откладываю на предыдущем остатке. Получается ровно два целых кусочка.
12 / 6 = 2
Этот кусочек и есть НОД. И вот почему: предыдущий остаток содержит два целых кусочка, а каждый предыдущий остаток укладывается в предпредыдущем целое число раз, то есть и предпредыдущий остаток и остаток до него и изначальное целое — все делятся на наш последний кусочек нацело.

НОД(150,96) = 6

Поддержите нас!

Мы сделали Блицтест бесплатным и свободным от рекламы, потому что верим в доступное и качественное образование для детей. Чтобы сделать вклад в развитие детского образования ощутимее нам нужна ваша помощь. Если вы разделяете наши убеждения и хотите помочь, пожалуйста, расскажите о нас друзьям или сделайте добровольное пожертвование на развитие проекта. Спасибо!

Поддержите нас