Разработка
Пред. Глава 49. Линейные уравнения След.

Разработка

Приготовления

Определение класса Capsule мы начинаем с переменной класса $tolerance, отвечающей за «терпимость» при сравнении чисел с нулём. В объявлении переменной используем слово our вместо my, чтобы при желании можно было бы изменить её значение из программы, использующей класс Capsule, например, так — $Capsule::tolerance=1E-9;: 

Perl
package Capsule;

our $tolerance=1E-8;

Конструктор не сулит ничего интересного — обычный конструктор объектов, построенных на базе массива: 

Perl
sub new
{
	my $class=shift;
	my $self=[];
	return bless $self, $class;
}

Методы known и value

Метод known также устроен очень просто: он пытается упростить список с линейным выражением, вызывая метод simplify (мы до него ещё доберёмся), а после упрощения возвращает «да», если длина упрощённого списка равна единице, и «нет» в противном случае: 

Perl
sub known
{
	my $self=shift;
	$self->simplify;
	return @$self==1;
}

Метод value возвращает свободный член капсулы, если она полностью известна, и неопределённое значение, если это не так: 

Perl
sub value
{
	my $self=shift;
	if($self->known)
	{
		return $self->[0];
	}
	else
	{
		return;
	}
}

Метод simplify

А теперь обсудим наиболее сложный метод в классе Capsule, simplify. Его код получился не слишком длинным, но при этом очень насыщенным. Поэтому, уважаемые читатели, будьте очень внимательны — написать код для нас оказалось несравненно легче, чем комментарии к нему!

Первым делом разберёмся со случаями, когда упрощать нечего: если длина списка меньше трёх, метод завершается (следует заметить, что список длины два в принципе невозможен): 

Perl
my $self=shift;
return if @$self<3;

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

Perl
for(my $i=0; $i<$#$self; $i+=2)

Тогда выражение $self->[$i] даёт коэффициент при очередной капсуле в линейном выражении, а $self->[$i+1] — саму капсулу. Частично или полностью известные капсулы (то есть нуждающиеся в подстановке) выявляются так: 

Perl
if(@{$self->[$i+1]})

Для них-то и делается подстановка.

Сейчас мы приведём полностью фрагмент кода, ответственного за первый проход, за подстановки (без этого его очень трудно будет пояснять): 

Perl
for(my $i=0; $i<$#$self; $i+=2)
{
	if(@{$self->[$i+1]})
	{
		my @capsule=@{$self->[$i+1]};
		for(my $j=0; $j<@capsule; $j+=2)
		{
			$capsule[$j]*=$self->[$i];
		}
		$self->[-1]+=pop @capsule;
		splice @$self, $i, 2, @capsule;
		redo;
	}
}

Внутри условной конструкции обнаружена капсула, полностью или частично известная. Это ссылка на некоторый массив длины не менее трёх. Сделаем копию этого массива в переменной @capsule. Домножим все коэффициенты и свободный член в этом массиве (элементы с нечётными индексами) на коэффициент перед капсулой. Эта задача решается во внутреннем цикле. В строчке, которая следует за внутренним циклом, у списка @capsule удаляется свободный член, который тут же добавляется к свободному члену исходного выражения, $self->[-1]. В списке @capsule остаются лишь капсулы и предшествующие им коэффициенты. Затем подставляемая капсула удаляется вместе с коэффициентом при ней, а на их место становится подстановка — то, что осталось в массиве @capsule. Этим занимается команда splice.

Ох, кажется, читателю будет столь же тяжело понять эти пояснения, как тяжело было нам их сформулировать. Попробуем пояснить, что происходит, на примере подстановки в линейном выражении 3 ⁢ x − 4 ⁢ y + 5 выражения x = 7 ⁢ y − 6 (при этом должно получиться 21 ⁢ y − 4 ⁢ y − 13 ; полученное выражение ещё ждёт дальнейшее упрощение в виде приведения подобных слагаемых).

Итак, в нашем примере $self=[3, $x, -4, $y, 5], $x=[7, $y, -6]. 

Perl
my @capsule=@$x;					@capsule⟹(7, $y, -6)

for(my $j=0; $j<@capsule; $j+=2)
{
	$capsule[$j]*=$self->[$i];
}									@capsule⟹(21, $y, -18)

$self->[-1]+=pop @capsule;			@capsule⟹(21, $y)
									$self⟹[3, $x, -4, $y, -13]

splice @$self, $i, 2, @capsule;		$self⟹[21, $y, -4, $y, -13]

Что же делает оператор redo? Цикл for автоматически увеличит на два переменную $j, выполнив команду модификации $j+=2. Но в случае, когда вместо одночлена 3 ⁢ x совершается подстановка, то есть вставляется одночлен 21 ⁢ y , и, кроме того, свободный член в $self увеличивается на − 18 , увеличение счётчика $j привело бы к тому, что мы «проскочили» бы только что вставленный одночлен 21 ⁢ y , и перешли бы к следующему, 4 ⁢ y . Между тем одночлен 21 ⁢ y , возможно, тоже нуждается в подстановке, если переменная y частично или полностью известна. Здесь нужно перезапустить тело цикла, не выполняя команду модификации, чтобы можно было рассмотреть этот одночлен, а не следующий за ним. Альтернативой к команде redo могла быть последовательность команд $j-=2; next;, которая «отматывает» счётчик $j назад. Оператор redo встретится ещё дважды в теле метода simplify, во втором и третьем упрощающих проходах.

Затем идёт код, отвечающий за приведение подобных слагаемых: 

Perl
outer: for(my $i=0; $i<$#$self; $i+=2)
{
	for(my $j=0; $j<$i; $j+=2)
	{
		if($self->[$j+1]==$self->[$i+1])
		{
			$self->[$j]+=$self->[$i];
			splice @$self, $i, 2;
			redo outer;
		}
	}
}

Здесь во внешнем цикле перебираются одночлены, а во внутреннем — предшествующие им одночлены (вдруг среди них встретится подобный, то есть содержащий ту же самую капсулу). Тогда их следует объединить. Как выявить случаи, когда в списке встречаются одинаковые капсулы? Как проверить, что капсула одна и та же? Технически, капсула — это ссылка на массив. Одинаковость ссылок проверяется путём их арифметического сравнения (условный оператор именно это и делает). Если выявлена капсула, которая ранее уже встречалась в списке, она удаляется вместе с её коэффициентом, а удалённый коэффициент прибавляется к коэффициенту при ранее встретившейся такой же капсуле. Тут нужно перезапустить тело внешнего цикла (не внутреннего!). Для перезапуска применяем оператор redo с меткой; этой меткой помечаем внешний цикл.

Осталась самая лёгкая часть метода simplify — удаление одночленов с нулевыми коэффициентами. Оставим её без пояснений: 

Perl
for(my $i=0; $i<$#$self; $i+=2)
{
	unless($self->[$i])
	{
		splice @$self, $i, 2;
		redo;
	}
}

Есть одно трудное место, связанное с использованием redo; оно нуждается в пояснении.

Метод equation

Процедура equation получает в виде списка левую часть уравнения (в правой части ноль). Первое, что нужно сделать — упростить выражение. У нас уже запрограммирован соответствующий метод simplify, однако он определён для капсул. Капсула — это ссылка на массив со списком, для которой была выполнена операция bless, превращающая ссылку в объект класса Capsule. Чтобы воспользоваться уже готовым методом, «завернём» список в объект класса Capsule, поместим объект в переменную $eqn и вызовем для него метод simplify: 

Perl
(my $eqn=bless [@_], 'Capsule')->simplify;

Если после упрощения левая часть уравнения окажется полностью известной, уравнение или несовместно, или избыточно, в зависимости от числа, стоящего в левой части: 

Perl
if(@$eqn==1)
{
	if(abs($eqn->[0])>$tolerance)
	{
		die "Несовместное уравнение (свободный член=$eqn->[0])!\n";
	}
	# warn "Избыточное уравнение!\n"
}

В противном случае выражаем из уравнения первую же присутствующую в нём капсулу. Для этого удаляем её вместе с коэффициентом, сохраняя их соответственно в переменных $var и $coefficient. Потом копируем список уравнения в список капсулы $var. В завершение делим все числа списка на число -$coefficient. 

Perl
else
{
	my $coefficient=shift @$eqn;
	my $var=shift @$eqn;
	@$var=@$eqn;
	for(my $i=0; $i<=$#$var; $i+=2)
	{
		$var->[$i]/=-$coefficient;
	}
}

Вы не поверите, но это всё.

Пред. Наверх След.
Идеи реализации Начало Готовая программа
Информатика-54© А. Н. Швец