Коль скоро речь зашла о школьных типовых задачах, рассмотрим ещё одну - вычисление суммарного сопротивления электрической цепи.

Конфигурация цепи, состоящей из резисторов, соединённых проводниками, задана в виде дерева (рис. 1.5). Дерево вводится в компьютер с помощью специально разработанного редактора, по возможности простого. Требуется вывести на экран получившуюся цепь и определить её суммарное сопротивление (для этого придётся написать рекурсивную функцию, вычисляютцую сопротивление любого заданного поддерева).

параш

-[ > R4

послед

пар ami

R2 R3

Рис 1.5. Представление электрической цепи в виде бинарного дерева

Напомню, сопротивление участка цеци, состоящего из последовательно соединённых резисторов R1 и R2, равно R1 + R2. Сопротивление участка цепи, состоящего из параллельно соединённых резисторов R1 и R2, равно R1*R2/(R1 + R2).

ГЛАВА 2.

РЕШЕНИЕ математических

задач

1.3.3. Расчет сопротивления, или электрическая цепь как бинарное дерево

Решению математических задач с помощью компьютера всегда уделялось особое внимание. Даже термин математическое обеспечение ЭВМ в соответствии с Большим энциклопедическим словарём используется в самом широком смысле: Комплекс программ, описаний и инструкций, обеспечивающих автоматическое функционирование ЭВМ. Различают общее математическое обеспечение (для организации вычислительного процесса на данной ЭВМ) и специальное математическое обеспечение (для решения конкретных задач) . В наши дни акценты сильно сместились, и большинство пользователей вряд ли отнесут DVD-проигрыватель или графический редактор к математическому обеспечению.

Однако задачи, пришедшие в программирование из математики, остаются. Причём отдельные подзадачи очень часто возникают при разработке, казалось бы, никак не связанных с математикой программ - например, при создании компьютерного бильярда или черчении проволочных объектов виртуального мира.

Некоторыми подобными задачами мы сейчас и займёмся.

2.1. АЛГЕБРА И ГЕОМЕТРИЯ

2.1.1. Интерполяция по Лагранжу, или восстановление недостАющЕй информации

Пусть после года наблюдений за окружающей средой у вас осталась таблица из двенадцати чисел, соответствующих средней температуре воздуха на улице за каждый месяц. Теперь нужно соединить все двенадцать точек плавной линией, чтобы пол)лся красивый график, который можно распечатать на принтере. Такого рода плавная 1фивая (называемая интерполирующей) может быть построена автоматически. Существуют различные методики решения этой задачи. Рассмотрим одну из них: интерполяцию многочленом Лагранжа.

Глава 2. Решение математических задач

Теория гласит, что для любого множества точек на плоскости (х у,), (Xj, Уз), , (Хд, Уд) можно построить многочлен Рп(х), график которого проходит через каждую точку множества. Для вычисления Р (х) служит формула:

г . ч (x-xJ(x-x,)...(x-x,J(x-x,J...(x-xJ тд,ец{х) =

(XrXj(XrXj...(XrX,J(XrX,J...(XrXj

Поясню структуру этой формулы. Многочлен состоит из суммы п элементов вида L(x)yj. Здесь у - это известная ордината i-й точки множества, а элемент L(x) вычисляется по второй формуле.

В числителе дроби L(x) находится произведение всех разностей вида (х - х) для к = 1,2,п, за исключением элемента (х - х.). В знаменателе находится произведение всех разностей вида (х - х) для к = 1,2,.... п, за исключением элемента (Xj - х), равного нулю. Обратите внимание, что знаменатели всех дробей L.(x) не зависят от х, и их достаточно вычислить единственный раз.

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

Для тех, кто до сих пор не был знаком с интерполяцией по Лагранжу, замечу заранее, что форма получившейся кривой может вас изрядно удивить. Поскольку алгоритм интерполяции не учитывает природы процесса (в данном случае процесса сезонного изменения температуры), график многочлена может показывать физически необоснованные скачки. Так, если средняя температура в июне была 25 градусов, а в июле - 30, график между этими точками теоретически может подскочить до 60 градусов или упасть до нуля. Гарантируется лишь, что все точки будут соединены плавной линией.

Некоторые другие способы интерполяции (например, сплайновая) свободны от этого недостатка.

2.1.2. Помощник химика

Сведение химических уравнений к алгебраическим

Обычная задача для школьного урока химии - уравнивание реакций, то есть нахождение таких коэффициентов в уравнении химической реакции,

Решение

Эта задача сводится к решению системы линейных уравнений. Рассмотрим пример, приведённый в формулировке задания:

кон + h..so,

k..so. + н,0

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

а*кон + b*hso, = C*KSO + d*h20,

где А, в, С и D - переменные, значения которых необходимо определить. Для их определения служат уравнения баланса, Количество которых равно количеству элементов, участвующих в реакции. Баланс элемента отражает тот факт, что число атомов этого элемента в левой и правой частях уравнения реакции должно совпадать:

к: а = с*2

о: а + в*4 = с*4 + d н: а + в*2 = d*2

s: в = с

Получилось четыре зфавнения с четырьмя неизвестными. В стандартной форме их можно записать следующим образом:

1*а + 0*в + (-2)*с + 0*d = о

1*а + 4*в + (-4)*с + (-1)*d = о

1*а + 2*в + 0*с + (-2)*d = о

0*а + 0*в + (-1)*с + 0*d = о

Поскольку решение системы линейных зфавнений - задача хорошо известная и многократно описанная, я не буду на ней останавливаться (например, можно воспользоваться методом Гаусса).

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

Преодолеть это затруднение можно, например, зафиксировав один из коэффициентов. Пусть А = 1. Тогда из системы уравнений

1 = с*2

1 + в*4 = с*4 + d 1 + в*2 = d*2 в = с

следует решение: В = 1/2, С = 1/2, D = 1. Умножая коэффициенты на наименьшее общее кратное знаменателей полученных дробей (в данном случае 2), получаем итоговый результат: А = 2, B=1,C = 1,D = 2.

Общую схему решения предлагаю читателю вывести самостоятельно.

2 Заж.772

чтобы для каждого элемента количество его атомов в реагентах равнялось количеству атомов в продуктах реакции.

Было: KOH + HjSO, -KjSO. + HjO

Стало: 2КОН + HSO = KSO + 2Up

Школьные алгоритмы нахождения коэффициентов носят, так сказать, эвристический характер. Им недостаёт системности. Тем не менее определить искомые коэффициенты можно автоматически (и отнюдь не только перебором).

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

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

Тогда реакция взаимодействия гидроксида калия с серной кислотой, приведённая вьппе, будет выглядеть так:

к 1 о 1 н 1 н 2 s 1 о 4 к 2 s 1 о 4 н 2 о 1

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

2 112

Подсказка

У химических уравнений много общего с уравнениями алгебраическими. Подумайте, где здесь неизвестные и какие алгебраические уравнения могут помочь их найти.