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

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

Посмотрим, как в  решается задача об отрезках, на которые стороны 3, 4, 5 треугольника делятся точками касания со вписанной окружностью:

numeric p, q, r;

message "В самом начале:";
show p, q, r;

p+q=3;
message "После первого уравнения:";
show p, q, r;

q+r=4;
message "После второго уравнения:";
show p, q, r;

r+p=5;
message "После третьего уравнения:";
show p, q, r;

bye.

Сохраняем текст программы в файле equations.mp и запускаем транслятор:

Видно, что числовые переменные могут находиться в одном из трёх состояний: полностью неопределённом (тогда команды show показывают их имена), полностью определённом (показываются числовые значения переменных). Кроме того, возможно и промежуточное состояние переменной, когда она выражена через другие полностью неопределённые переменные — тогда показывается соответствующее линейное выражение. В терминологии структура данных, которая может быть или неопределённой, или хранить линейное выражение, в котором участвуют переменные, или хранить число, называется капсулой (capsule).

Можно заметить, как влияет появление очередного уравнения в программе на состояния переменных: одна из участвующих в уравнении букв выражается через остальные. В этом и заключается метод последовательного исключения неизвестных.

Нам нужен тип данных для представления в программе переменных в уравнениях. Мы могли бы назвать соответствующий класс Variable (variable — переменная), но тогда будет путаница между переменными в математике и переменными в языке программирования. Назовём этот класс Capsule.

Объекты класса должны подходить для хранения линейных выражений c участием других капсул. В частном случае, если в линейном выражении отсутствуют другие капсулы, там остаётся только лишь число — это тот самый случай, когда капсула становится «известной». Особый случай, когда значение капсулы полностью неизвестно, также следует предусмотреть.

Итак, придётся хранить в одном и том же объекте выражения наподобие этих: x = ? , x = 8 y + 11 z w + 3 , x = 22 . В линейных выражениях имеется чёткая структура: это список слагаемых, каждое из которых, за исключением последнего, является переменной (капсулой), умноженной на числовой коэффициент. Последнее слагаемое, свободный член выражения — число. Таким образом, подходящей структурой данных для линейных выражений служит массив, в котором ячейки с чётными индексами заняты коэффициентами и свободным членом. На нечётных местах располагаются капсулы. Этот массив должен иметь нечётный размер. В особом случае, когда значение капсулы полностью неизвестно, массив будет пустым — этот случай мы ни с чем не спутаем. На языке Perl значения переменной $x для приведённых выше примеров будут такими: [], [-8, $y, 11, $z, -1, $w, 3], [22], если в переменных $y, $z, $w находятся другие капсулы.

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

Типичная программа equation-345.pl, решающая систему линейных уравнений p + q = 3 , q + r = 4 , r + p = 5 , могла бы выглядеть так:

#!/usr/bin/perl

use warnings;
use Capsule;

my $p=Capsule->new;
my $q=Capsule->new;
my $r=Capsule->new;

Capsule::equation(1, $p, 1, $q, -3);
Capsule::equation(1, $q, 1, $r, -4);
Capsule::equation(1, $r, 1, $p, -5);

print "p=", $p->value, "\n";
print "q=", $q->value, "\n";
print "r=", $r->value, "\n";

% ./equation-345.pl p=2 q=1 r=3

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

Линейное выражение не нуждается в упрощении, если оно

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

Рассмотрим процесс упрощения на примере линейного выражения 15 a 3 b + 2 c + 6 d 4 , предполагая, что b = 5 a c + d + 2 , c = 7 , а переменные a и d полностью неизвестны.

Первый проход по списку делает подстановки тех переменных, которые не являются полностью неизвестными: 15 a 3 b + 2 c + 6 d 4 пропускаем 15 a 3 b + 2 c + 6 d 4 подставляем 15 a 3 5 a c + d + 2 + 2 c + 6 d 4 15 a 15 a + 3 c 3 d + 2 c + 6 d 10 пропускаем 15 a 15 a + 3 c 3 d + 2 c + 6 d 10 подставляем 15 a 15 a + 3 7 3 d + 2 c + 6 d 10 15 a 15 a 3 d + 2 c + 6 d + 11 пропускаем 15 a 15 a 3 d + 2 c + 6 d + 11 подставляем 15 a 15 a 3 d + 2 7 + 6 d + 11 15 a 15 a 3 d + 6 d + 25 пропускаем 15 a 15 a 3 d + 6 d + 25

Во втором проходе приводятся подобные слагаемые: 15 a 15 a 3 d + 6 d + 25 пропускаем 15 a 15 a 3 d + 6 d + 25 приводим 0 a 3 d + 6 d + 25 пропускаем 0 a 3 d + 6 d + 25 приводим 0 a + 3 d + 25

В третьем проходе удаляются одночлены с нулевыми коэффициентами: 0 a + 3 d + 25 удаляем 3 d + 25 пропускаем 3 d + 25

Самое время обсудить те действия, которые совершаются при обработке очередного уравнения.

Процедура equation получает список, представляющий линейное выражение — то самое, которое приравнивается нулю. Прежде всего выражение упрощается. После этого возможны следующие ситуации:

Разберёмся сначала со вторым, более простым случаем, когда после упрощения уравнение свелось к тривиальному 0 = 0 или a = 0 , где a — ненулевое число.

Уравнение 0 = 0 , очевидно, не добавляет никакой информации о неизвестных, и поэтому бесполезно. Такое уравнение назовём избыточным. при появлении избыточного уравнения выдаёт предупреждение Redundant equation. По желанию можно или игнорировать избыточные уравнения, или выдавать подобное предупреждение.

Уравнение a = 0 , где a 0 , конечно же ставит крест на наших попытках определить неизвестные из линейных уравнений. Такие уравнения назовём несовместными; откликается на их появление сообщением Inconsistent equation. Нам нет никакого смысла продолжать исполнение программы, если встретилось несовместное уравнение.

Тут однако есть проблема. Рассмотрим следующий пример:

$a=1000;
print "РАВНО!\n" if $a/333*333==$a;
print $a/333*333-$a, "\n";

Почему-то эта программа не печатает строчку РАВНО!, как можно было ожидать. Кроме того, вопреки ожиданиям, она напечатает не ноль, а что-то вроде этого:

Информатика-54© А. Н. Швец