Решение задачи 12.
Как известно НОК(a,b)=ab/НОД(a,b).
Для нахождения НОД используем алгоритм Евклида. Будем обозначать НОД(a,b) просто как (a,b).
Шаг алгоритма. Пусть a>=b (если это не так, то просто поменяем содержимое переменных a и b местами).
Если b=0, то (a,b)=a, СТОП.
Иначе (a,b)=(a mod b,b).
Действительно, если g=(a,b), то он делит и a, и b, и остаток r от деления a на b: a=bs+r, тут s - частное a div b, r = a mod b. Покажите, что (a,b)=(r,b).
Обозначим через a величину a mod b. Снова выполним шаг алгоритма.
Существует и другой, более быстрый ('машинный') вариант нахождения НОД:
Для вычисления НОД воспользуемся следующими очевидными равенствами:
1). (0,a)=a, (a,b)=(b,a)
2). (a,b)=(a-b,b)
3). Если a и b оба четны, то (a,b)=2*(a/2,b/2)
4). Если a четно, а b - нет, то (a,b)=(a/2,b)
5). Если a и b оба нечетны и a>b, то (a-b) - четное число,при этом (a-b)<max{a,b} и (a,b)= =(a-b,b).
Алгоритм :
Шаг 1. k:=1
Шаг 2. Пока a и b одновременно четны, выполняем
a:=a/2
b:=b/2
k:=k*2
Шаг 3. Если оба числа a и b нечетны,то на место большего из них заносимразность его и меньшего из чисел, иначе, если одно из чисел a или b четно, то делим его на 2.
Шаг 4. Если одно из чисел (a или b) равно нулю, то (a,b) равен произведению другого числа на k, и алгоритм завершает работу, иначе перейти на шаг 3.
|
