Что такое алгоритм: различия между версиями
Содержимое удалено Содержимое добавлено
Дискретная математика, алгоритмы и структуры данных |
|||
Строка 170:
Покажем, что наш алгоритм нахождения НОДа чисел <math>a</math> и <math>b</math>.
Действительно, НОД<math>(a,\;b)=\;</math>НОД<math>(a-b,\;b)</math> при <math>a>b</math>, поэтому, несмотря на то, что на каждом шаге меняется одно из чисел, значение НОД<math>(a,\;b)</math> остаётся неизменным. Максимальное из чисел <math>a</math> и <math>b</math> с каждым шагом уменьшается, и в какой-то момент они становятся равны друг другу и равны искомому
Докажите, что НОД<math>(a,\;b)=\;</math>НОД<math>(a-b,\;b)</math> для любых неотрицательных целых <math>a</math> и <math>b</math>, таких что <math>a>b</math>.
| |||