Глава 12. Вычисление НОД :: Идеи реализации

Идеи реализации
	Глава 12. Вычисление НОД

Идеи реализации

Алгоритм Евклида (рекурсивная версия)

Для вычисления НОД двух чисел существует алгоритм Евклида. Этот алгоритм очень простой.

Если числа равны, то их НОД совпадает с ними. Если меньшее из чисел равно нулю, то ответом будет большее. Иначе вычтем из большего числа меньшее и найдём их НОД. Это будет ответ.

Видно, что алгоритм Евклида формулируется как рекурсивный, поэтому уместно его рекурсивное программирование.

Осталось убедиться, что алгоритм Евклида не приведёт к бесконечной рекурсии. Действительно, для вычисления НОД двух чисел $x$ и $y$ (предположим, что $x ⩾ y$ ) придётся вычислить НОД $x - y$ и $y$ . Одно из чисел $x$ и $y$ на каждом шаге строго уменьшается, оставаясь неотрицательным, и поэтому, рано или поздно, одно из чисел обнулится, и алгоритм остановится.

Вычисление НОД двух чисел оформим как процедуру, вызывающую рекурсивно саму себя. Она будет в точности воплощать описанный алгоритм.

Perl
sub gcd
{
	my ($x, $y)=@_;
	return $y unless $x;
	return ($x>=$y)? gcd($x-$y, $y): gcd($x, $y-$x);
}

Индуктивное вычисление НОД нескольких чисел

Применим для НОД чисел $x_{1}, x_{2}, \dots, x_{n}$ обозначение $\gcd (x_{1} x_{2} x_{3} \dots x_{n})$ .

Для вычисления НОД нескольких чисел можно воспользоваться следующим свойством: $\gcd (x_{1} x_{2} x_{3} \dots x_{n}) = \gcd (\gcd (x_{1} x_{2} \dots x_{n - 1}), x_{n}) .$ Применение этого свойства к правой части последнего равенства позволит «разворачивать» выражение до тех пор, пока в нём не останутся многочисленные НОД от двух чисел: $\dots = \gcd (\gcd (\gcd (x_{1} x_{2} \dots x_{n - 2}), x_{n - 1}), x_{n}) = \dots$

Все эти наблюдения позволяют вычислять НОД последовательности чисел постепенно, по мере добавления новых чисел. Если НОД вычислено, то добавление нового числа к списку вынуждает нас вычислить НОД от старого НОД и добавленного числа. Особой обработки требует случай, если в списке единственное число. Но в этом случае в качестве НОД логично взять само это число.

Извлечём из массива @ARGV первое число в переменную $gcd:

Perl
my $gcd=shift @ARGV;

Затем в цикле до полного опустошения массива @ARGV будем вычислять НОД от старого НОД (он в переменной $gcd) и от нового числа (оно извлекается из массива @ARGV). Результат вычислений снова присваивается переменной $gcd.

Perl
while(@ARGV)
{
	$gcd=gcd($gcd, shift @ARGV);
}

Наконец, переменная $gcd выводится на экран и программа на этом завершается.

Perl
print "$gcd\n";

Алгоритм Евклида (итеративная версия)

Рекурсивная переформулировка задачи — это всегда программистская находка, которая ведёт к изящному решению. Однако нужно отдавать себе отчёт в том, что во многих алгоритмических языках (и Perl тут не исключение) рекурсия — дорогое удовольствие. Как правило, рекурсивная программа во время работы требует больше ресурсов компьютера, и, как следствие, медленнее работает.

Чтобы прояснить источник проблем при использовании рекурсии, проиллюстрируем работу рекурсивного алгоритма Евклида при вычислении НОД чисел $1$ и $100$ . В качестве исполнителя алгоритма (точнее, процедуры gcd) выступит не компьютер, а человек, специально обученный вычислять НОД двух чисел. Согласно алгоритму для получения результата ему потребуется выполнить вспомогательное вычисление НОД чисел $1$ и $99$ . Поскольку этот человек не может вести два вычисления одновременно, он обращается ко второму исполнителю, приостановив свою работу. Второй также приостановится, обратившись к третьему с заданием вычислить НОД $1$ и $98$ . В какой-то момент будут одновременно задействованы 99 вычислителей, из которых первые 98 приостановили свою работу и ждут последнего, 99-го. Каждый из этих 98 помнит точку приостановки своей работы, и, кроме того, значения всех своих локальных переменных. Для этого требуется довольно много памяти.

Программа с глубоко вложенными рекурсивными вызовами процедур может исчерпать всю доступную оперативную память компьютера и взяться за виртуальную (она расположена на жёстком диске компьютера). Обращение к виртуальной памяти происходит на порядок медленнее, чем к оперативной. Работа программы катастрофически замедлится.

На наше счастье имеется теорема, утверждающая, что любую рекурсивную программу можно заменить на эквивалентную, но не использующую рекурсию. Правда, теорема не даёт указаний, как осуществить такую равносильную замену.

В нашей задаче преобразование рекурсивной программы в нерекурсивную проводится просто. В цикле, пока первое из чисел не обнулится, делается следующее: если первое из чисел больше второго, они меняются местами; затем из второго вычитается первое. Когда цикл завершится, первое число обратится в нуль, а второе и будет искомым НОД, оно и возвращается из процедуры:

Perl
sub gcd
{
	my ($x, $y)=@_;
	while($x)
	{
		($x, $y)=($y, $x) if $x>$y;
		$y-=$x;
	}
	return $y;
}


Глава 12. Вычисление НОД		Готовая программа