Главная страница
qrcode

задачи для начинающих


Названиезадачи для начинающих
Дата18.03.2020
Размер168 Kb.
Формат файлаdoc
Имя файлаrazbor (4).doc
ТипЗадача
#65787
Каталог

Решения задач заочного тура 2005-06 учебного года
Задача А. Часы с боем.

Автор задачи и разбора –Гуровиц В.М.



Тема: «задачи для начинающих»

Решение первое: моделирование. Будем “крутить” стрелки часов, каждую минуту оценивая ситуацию и считая удары. Этот алгоритм можно реализовать, например, так.

while (h1 <> h2) or (m1 <> m2) do begin

inc(m1); {прибавляем одну минуту}

if m1 = 60 then begin

inc(h1); h1 := h1 mod 24; m1 := 0;

if h1 mod 12 = 0 then

inc(res, 12)

else

inc(res, h1 mod 12);

end

else

if m1 = 30 then

inc(a);

end;

(здесь h1:m1 – начальное время, h2:m2 – конечное время, res – количество ударов).
Решение второе: подсчет ударов. Пусть начальное время меньше конечного. Тогда можно подсчитать количество ударов следующим образом. Общее количество ударов складывается из
“часовых” ударов в моменты времени (h1+1):00, (h1+2):00, …, h2:00;
  • “получасовых” ударов в моменты времени (h1+1):30, (h1+2):30, …, h2:30;
  • “получасового” удара в момент времени h1:30, если m1<30;
  • “получасового” удара в момент времени h2:30, если m2>30.
    Теперь заметим, что за сутки часы бьют 180 раз. Поэтому в случае, когда конечное время меньше начального, можно поменять их местами, вычислить количество ударов по приведенной выше схеме и вычесть полученное число из 180.

    Решение третье: явная формула. Обозначим через U(t

    Для величины U(t,0) тоже можно вывести явную формулу. Например, такую:
    U(h:m,0) = (h DIV 12) * 78 + {Количество “часовых” ударов

    за полные 12 часов }

    + (h MOD 12) * ((h MOD 12) + 1) DIV 2

    {количество “часовых” ударов

    за остальное время }

    + h {количество “получасовых” ударов}

    + ord (m > 30) {еще один “получасовой” удар,

    если m>30 }

    Задача B. Выборы жрецов.


    Автор разбора – Гуровиц В.М.



    Тема: «задачи для начинающих»

    После внимательного прочтения условия задачи становится понятно, что нужно считать из входного файла номера жрецов-покровителей, и затем заменить некоторые из них на новые. Вот как это можно было реализовать.
    1) Читаем номера жрецов покровителей:

    for i:=1 to N do

    read(a[i]);
    2) Читаем пары (старый номер, новый номер):

    for i:=1 to M do

    read(k,b[k]);

    Теперь b[k] – либо новый номер, соответствующий старому номеру k, либо 0, если номер не изменился.
    3) Печатаем номера, при необходимости заменяя старый номер новым.

    for i:=1 to N do

    if b[a[i]]>0 then write(b[a[i]],' ')

    else write(a[i],' ');

    Задача C. Представление чисел


    Автор задачи — Петров А.А., автор разбора – Гуровиц В.М.



    Тема: делимость

    Пусть A и B – искомые числа, а d – их наибольший общий делитель. Поскольку N=A+B, и каждое из чисел A и B делится на d, то и N делится на d. Таким образом, в качестве кандидата на роль d можно рассматривать наибольший делитель числа N, меньший N.

    Тогда e = N : d – наименьший делитель числа N, больший 1.

    Представим число N в виде суммы N = (N : e) + (N – N : e). Оба слагаемых делятся d, поэтому можно положить A = N:e, B = N - N:e. Таким образом, исходная задача свелась к нахождению наименьшего делителя е числа N, большего единицы.

    Заметим, что либо
    Следовательно, для нахождения числа e достаточно перебрать все числа от 2 до Заметим, что перебор всех чисел от 2 до N требует времени, выходящего за рамки временных ограничений задачи. Также слишком много времени требует поиск наибольшего делителя числа N, меньшего N.
    Как часто бывает, текст решения в данном случае существенно короче, чем его описание:
    i:=2;

    while (N mod i > 0) AND (i<=sqrt(N)) do

    Inc(i);

    if (N mod i > 0) then

    write(N-1,' ',1)

    else

    write(N div i,' ',N – N div i);
    Но оказывается, что это решение можно еще упростить!

    Заметим, что если число N – простое, то НОД(A,B) = 1 для любых натуральных A и B, дающих в сумме N, поэтому можно вывести любые натуральные числа, сумма которых равна N. Пользуясь этим, можно еще сократить приведенную выше программу:
    i:=2;

    while (N mod i > 0) AND (i<=sqrt(N)) do

    Inc(i);

    write(N div i,' ',N – N div i);
    Совет: при такой реализации sqrt(N) вычисляется при каждой итерации цикла while. Этого можно избежать, если заранее вычислить эту величину и использовать в условии цикла ее значение.


    Задача D. Гексагон

    Автор разбора – Гуровиц В.М.




    Тема: «задачи на разные темы»

    Пусть x – суммарная длина ходов, сделанных в направлении X, y – суммарная длина ходов в направлении y, z – суммарная длина ходов в направлении z. Заметим, что любую клетку поля можно задавать не тремя координатами, а двумя. В частности, клетка (X,Y,Z) совпадает с клеткой (X-Z,Y+Z,0), а также с клеткой (X+Y,0,Z-Y) и с клеткой (0,Y+X,Z-X). Для того чтобы найти кратчайший путь из данной клетки, нужно записать ее координаты в таком виде, чтобы как можно больше координат оказались равными нулю.
    Задача Е. Магия Копперфильда

    1
    2
    3
    4
    5
    2
    3
    4
    5
    6
    3
    4
    5
    6
    7
    4
    5
    6
    7
    8
    5
    6
    7
    8



    Автор разбора – Гуровиц В.М.



    Тема: игры и стратегии

    Сначала разберемся, в чем же состоит секрет фокуса. Раскрасим клетки квадрата в два цвета в шахматном порядке. Заметим, что после чётного количества ходов мы всегда оказываемся в клетке того же цвета, что и начальная клетка, а после нечётного количества ходов мы всегда “меняем цвет”. Таким образом, мы всегда знаем цвет клетки, на которую в данный момент указывает палец зрителя. Если мы будем каждый раз удалять клетки только соответствующего цвета, и при этом всегда оставлять связную фигуру, состоящую более чем из одной клетки, то цель будет достигнута.

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

    Для вычисления номера клетки заметим, что каждая следующая клетка диагонали имеет номер на N-1 больше, чем предыдущая клетка той же диагонали (если идти по диагонали налево и вниз).
    Задача F. Кубическое уравнение

    Автор разбора – Гуровиц В.М.



    Тема: делимость

    Решение этой задачи опирается на следующий несложный факт:

    Если целое число x – решение уравнения n-й степени с ненулевым свободным членом, то x является делителем этого свободного члена.

    Это несложно доказать: сумма (в нашем случае Ax3+Bx2+Cx+D) равна нулю, а все слагаемые кроме последнего делятся на x, следовательно, и последнее слагаемое, то есть свободный член, делится на x.

    Таким образом, если D отлично от нуля, то нам достаточно перебрать все делители числа D (включая отрицательные), и, подставив каждый из них в уравнение, выбрать те, которые являются корнями уравнения. Если же D = 0, то можно “сократить” на x, не забыв при этом корень x = 0. Если в полученном уравнении свободный член опять окажется равным нулю, нужно еще раз сократить на x и т.д.

    Случай, когда A = B = C = D = 0 – единственный случай, когда уравнение имеет бесконечно много решений, и потому требуется вывести в выходной файл “-1”. Во всех остальных случаях уравнение либо имеет не более трех корней, либо вовсе не имеет корней. Поэтому отсортировать полученные корни по возрастанию не составит труда.

    Заметим, что приведенное решение не зависит от того, является ли данное уравнение кубическим, то есть, равно ли A нулю.
    Задача G. Скорая помощь

    Автор разбора – Антонов В.Ю.
    Тема: делимость, перебор

    Сначала решим более простую задачу. По номеру квартиры, количеству квартир на одном этаже и количеству этажей в доме определим подъезд и этаж, где находится квартира. Пусть K – заданный номер квартиры, A – количество квартир на этаже, а M – количество этажей в доме. Тогда искомый номер подъезда будет равен (K-1) Div (M*A)+1. Для поиска номера этажа занумеруем квартиры в каждом подъезде, начиная с 1. Новый номер квартиры будет равен K=(K-1) Mod (M*A)+1, а искомый номер этажа (K'-1) DivA+1.

    Для решения основной задачи будем перебирать возможное количество квартир на этаже (от 1 до 1000), проверять совпадение номера этажа N2 и подъезда P2 для заданной во входном файле квартиры K2 и, если полученные и имеющиеся данные совпадают, то воспользоваться вышеописанным решением для квартиры, заданной номером K1.

    При выводе ответа стоит учесть, что если правильных ответов несколько, то у них могут совпадать только этажи, только подъезды, или ничего не совпадать.

    Задача H. A-функция от строчки

    Автор задачи – Василевский Б.О., автор разбора – Антонов В.Ю.
    Тема: алгоритмы на строках

    Сведём эту задачу к другой, похожей задаче и воспользуемся методом динамического программирования.

    Определим функцию z(i) следующим образом:

    z(i) = максимально возможное k такое, что равны следующие строки:

    S[1]+S[2]+S[3]+…+S[k]

    и S[i]+S[i+1]+S[i+2]+…+S[i+k-1]

    где S[i] – i-й символ строки S, а знак + означает, что символы записываются в строчку непосредственно друг за другом; z(1) положим равным нулю.

    Будем решать задачу нахождения z(i) для всевозможных значений i от 1 до N.

    Предположим, что новая задача решена для первых i-1 элементов строки. Среди уже посчитанных значений функции z найдём такое, z-функция для которого максимально «выступает», т.е. найдём такое l<i, что l+z(l)-1 максимально. Возможны два случая.
    l+z(l)-1<i. В этом случае z(i) будем вычислять, используя определение.
  • l+z(l)-1>=i. Если i+z(i-l+1)<l+z(l), то z(i) будет равно z(i-l+1). Если же i+z(i-l+1)>=l+z(l), то функции z будем считать, используя определение, учитывая, что l+z(l)-i символов уже совпадает.
    Покажем, что данный алгоритм можно реализовать так, чтобы количество выполняемых операций было пропорционально длине заданной строки S.

    Заметим, что l не обязательно пересчитывать на каждом шаге. Предположим, что для (i-1)-го элемента строки уже вычислена функция z и значение l. Тогда для i-го элемента строки l может либо не измениться, либо поменять значение на i-1.

    Сумма l и z[l] может только увеличиваться с увеличением l, при этом эта сумма может увеличиваться не более чем N раз. Поэтому при подсчёте z при помощи определения (1-й случай и часть второго случая) потребуется не более N операций.

    Для решения исходной задачи модифицируем заданную строку S, поставив после неё любой символ, которого в ней нет. После этого символа запишем перевёрнутую строку S (S[N]+S[N-1]+…+S[2]+S[1]). Для полученной строки посчитаем z функцию, которая была описана выше. Ответом будут являться значения функции для 2*N+1, 2*N,…,N+2 элементов.

    Задача I. Олимпиада по алхимии

    Автор задачи — Леонов Я.А., автор разбора – Антонов В.Ю.

    Тема: алгоритмы на графах – алгоритм Дейкстры

    Решение этой задачи использует один из стандартных алгоритмов на графах: алгоритм Дейкстры. Не будем приводить здесь его описание, т.к. его можно найти во многих книгах (к примеру, в книге Т. Кормена «Алгоритмы: построение и анализ»).

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

    Задача J. Лотерея

    Автор задачи – Лунев А.А., автор разбора – Антонов В.Ю.
    Тема: структуры данных

    Введём несколько определений.

    Глубиной вершины v называется минимальное количество рёбер, которое требуется пройти, чтобы попасть из корня дерева в v.

    Глубина дерева – максимальная из глубин вершин, принадлежащих дереву.

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

    Представим множество M-значных чисел в K-ичной системе счисления в виде дерева следующим образом. Глубина дерева будет равна M, и из каждой вершины будет выходить по K рёбер, соответствующих К различным цифрам. Каждому M-значному числу в K-ичной системе будет соответствовать путь из корня дерева в одну из висячих вершин глубины M. Путь для числа J выбирается следующим образом:

    Если мы находимся на глубине i, то идём по ребру, на котором написана i+1-я цифра числа J.

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

    В каждой вершине будем хранить количество чисел, первые цифры которых совпадают с путём от корня до данной вершины. Тогда исходная задача сводится к поиску пути в дереве, для которого сумма чисел, записанных на пройденных в пути вершинах, с соответствующими коэффициентами, будет минимальна. Коэффициент для корня равен 0, для вершин, находящихся на глубине 1 – Ai>1 – AiAi
    Переформулированную таким образом задачу можно решить при помощи метода динамического программирования. Будем решать задачу «снизу вверх», т.е. будем искать пути с минимальными суммами в поддеревьях, корни которых находятся на глубине i, а параметр i будем перебирать от M до 0. Предположим, что ответ для вершин, находящихся на глубине i+1 уже посчитан. Тогда ответом для вершины на глубине i будет являться сумма числа, записанного в вершине, умноженного на соответствующий коэффициент, и минимума из ответов для сыновей данной вершины. Инициализацией для алгоритма является нахождение ответа для вершин, находящихся на глубине M. Это делается нахождением произведения соответствующего коэффициента на количество билетов с номером, который совпадает с путём от корня дерева до данной вершины.

    Заметим, что для данной задачи не требуется полностью строить дерево, в нём может быть не более чем N*M элементов. А весь алгоритм потребует порядка N*M*K операций.

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

    Задача K. Коммерческий калькулятор

    Авторы разбора – Антонов В.Ю. и Гуровиц В.М.
    Тема: структуры данных

    Для решения данной задачи воспользуемся жадным алгоритмом. Среди данных n чисел выберем два наименьших, сложим их, и запишем полученную сумму вместо этих чисел. Теперь из полученного набора из n-1 числа опять выберем два наименьших, и повторим операцию. Так будем действовать до тех пор, пока не вычислим сумму всех n чисел. Например, для набора (1,2,4,5,6) алгоритм будет работать следующим образом:
    18=7+11.
    Сначала покажем, как эффективно реализовать данный алгоритм, а затем докажем, что предложенный жадный способ вычисления суммы является самым дешевым.
    Если для хранения набора чисел использовать отсортированный массив, то нам потребуется порядка N2 операций для вставки в массив N новых значений, что не удовлетворяет ограничениям по времени. Поэтому для реализации предложенного алгоритма воспользуемся структурой данных «куча». Не будем здесь приводить описание этой структуры, т. к. его можно найти во многих книгах (к примеру, в книге Т. Кормена «Алгоритмы: построение и анализ»). В этом случае количество операций будет пропорционально N log N, что удовлетворяет всем ограничениям задачи.
    Теперь докажем, что указанный способ вычисления суммы – самый дешевый. Нам достаточно доказать, что существует самый дешевый способ вычисления, при котором на первом шаге складываются два самых маленьких числа. Тогда утверждение будет доказано по индукции. Пусть это не так. Рассмотрим самый выгодный порядок операций. Построим дерево, соответствующее данному порядку вычислений. Как оно устроено понятно из примера на рисунке.

    Заметим, что от каждого из данных n чисел мы выплачиваем 5% столько раз, на какой глубине в дереве это число находится (поскольку именно столько раз оно участвует в сложениях).

    Пусть в таком дереве две вершины с минимальными значениями m и n не являются братьями и находятся на глубине h
    Отметим, что аналогичный жадный алгоритм используется для построение кодов Хаффмена, применяющихся для сжатия текстов. Об этом также можно прочитать в книге Т. Кормена.
    Задача L. Пересечение кубов

    Автор задачи — Василевский Б.О., авторы разбора – Василевский Б.О. и Юрьев А. Ю.
    Тема: геометрия
    Задачу можно было решить двумя принципиально разными способами. Первый способ (предложенный Василевский Б.О.) — вывод точных формул вычисления объема. Второй способ (предложенный Юрьевым А.О.) основывается на приближенных вычислениях.
    Способ 1.Рассматриваемое решение не сильно отличается от решения более общей задачи: надо найти фигуру (многогранник) TОпределение. Плоскость назовем собственной для многогранника T, если она содержит какую-либо его грань (многоугольник).
    Идея решения состоит в том, чтобы отсекать от TСначала договоримся, как мы будем хранить многогранник. Для данного решения удобно представить его как набор граней (многоугольников). Для каждой такой грани будем хранить плоскость, в которой она находится (соответствующая собственная плоскость для данного многогранника) и упорядоченный список вершин (две соседние вершины соединены ребром). Обсудим это подробнее для случая кубов.
    Предложение 1. При отсечении от первого куба всего, что не принадлежит второму, в любой момент у любой грани существует точка L, которая «сохранится» до конца процесса, т.е. которая принадлежит TВ самом деле, общая вписанная сфера TЭта точка обладает еще одним полезным свойством.
    Предолжение 2. Если опустить из O перпендикуляр на плоскость грани, его основание будет совпадать с L.
    Это следует из свойства касательной плоскости к сфере.
    Предложение 3. Пусть плоскость задается в пространстве уравнением Ax + By + Cz + D = 0. Тогда вектор (A, B, C) ортогонален этой плоскости. (Это утверждение является полным аналогом теоремы для плоскости о том, что если прямая задается уравнением Ax + By + C = 0, то вектор (A,B) перпендикулярен этой прямой).
    Теперь мы обладаем достаточными знаниями для того, чтобы понять, как эффективно хранить плоскость для каждой грани. Пусть она задается уравнением Ax + By + Cz + D = 0 и точка L (описанная выше) имеет координаты (a, b, c). Тогда векторы (a, b, c) и (A, B, С) коллинеарны. Пусть d · (a, b, c) = (A, B, C), d  0. Тогда уравнение плоскости примет вид: ax + by + cz + D/d = 0. Если взять x = a, y = b и z = c, то равенство будет верным, так как L лежит в этой плоскости. Получаем: a2 + b2 + c2 = -D/d. Заметим, что L лежит также на сфере радиуса 1, то есть a2 + b2 + c2 = 1. Таким образом, уравнение плоскости можно записать через координаты точки L: ax + by + cz = 1. Поэтому вместо уравнения плоскости будем хранить координаты точки L (они понадобятся также при подсчете объема).
    Теперь научимся упорядочивать список вершин данной грани R. Перед этим сделаем так, чтобы в списке не было двух совпадающих вершин.
    Предложение 4. Чтобы упорядочить вершины выпуклого многоугольника R в порядке обхода, достаточно отсортировать их по полярному углу в данной плоскости относительно точки L.
    Это следует из того, что многоугольник R выпуклый, и L лежит внутри R.
    Определение. Ориентированным объемом трех векторов a(ab(bc(сV(a, b, c) = aМодуль этой величины равен объему параллелепипеда, со сторонами, образованными векторами a, b, c. Иногда эта величина будет положительна, иногда – отрицательна. Когда какой знак будет получаться, обсудим подробнее.
    Пусть все три вектора отложены от начала координат. Представим себе, что мы сидим на конце вектора c и смотрим на плоскость, содержащую a и b. Рассмотрим такой минимальный угол φ > 0, при повороте на который по часовой стрелке вокруг начала координат в плоскости векторов a и b вектор a станет сонаправлен вектору b. Для всех таких a, b, c, что φ < 180, знак V(a, b, c) будет одинаков. Аналогично, для всех таких a, b, c, что φ > 180, знак V(a, b, c) также будет одинаков, причем он будет отличаться от знака ориентированного объема в предыдущем случае (это обобщение ориентированной площади для двух векторов на плоскости).

    Вернемся к упорядочиванию вершин. Рассмотрим вектор с = OL с координатами(la, b, c) < 0, то вершина A идет в нашем упорядочивании раньше вершины B.
    Таким образом мы можем отсортировать список вершин каждой грани.
    Теперь перейдем непосредственно к описанию алгоритма решения задачи.
    Из первого куба надо «извлечь» собственные для него плоскости, для этого достаточно вычислить координаты соответствующих точек L.
    Инициализация второго куба TТеперь каждой гранью куба Tненужными), лежащие по разные стороны с точкой O относительно плоскости P. На самом деле это будет выглядеть так: будут создаваться новые вершины в гранях, пересекающих P (точнее – точки пересечения ребер с P), удаляться ненужные вершины граней, создаваться новые грани из точек пересечения P и граней T.
    Обсудим это подробнее. Подумаем, каким может быть взаимное расположение T и плоскости P.

    Если P совпадает с какой-либо плоскостью, содержащей какую-либо грань T, то P не может повлиять на T (не существует точек T, лежащих по другую сторону с O относительно P).

    В противном случае P пересекает некоторые грани T.
    Нам нужен список всех точек, лежащих в P и при этом на сторонах граней T. Понятно, что именно из них получится новая грань – многоугольник, являющийся сечением T плоскостью P.
  • Во-вторых, надо модифицировать грани, пересекающие P, так, чтобы на них не осталось ненужных точек.
    Придумаем, как выполнить (2), потом в результате выполним и (1).


    У нас будет глобальный список найденных точек (1). Время от времени будем его пополнять.

    Рассмотрим произвольную грань T, пересекающую P. Пусть эта грань лежит в плоскости a. Плоскость P пересекается плоскостью a по прямой. Эта прямая имеет с гранью (многоугольником) общие точки по условию. Их количество либо 1, либо 2, либо бесконечно много.

    Если 1 – то P касается грани и ненужных точек на грани нет. Просто запомним в список эту точку.

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

    Последний случай (бесконечно много общих точек у грани и прямой) возможен тогда и только тогда, когда прямой полностью принадлежит какая-то сторона S грани. С точки зрения реализации этот случай не отличается от предыдущего. В список занесутся вершины стороны S. Никакой внутренней вершины в списке не должно оказаться, так как мы ищем пересечение отрезка и плоскости в том случае, когда оба конца не лежат в этой плоскости, иначе это просто бессмысленно.
    Предложение 5. Рассмотрим плоскость P: ax + by + cz = 1 и две точки A(x1, y1, z1) и B(x2, y2, z2). Отрезок AB пересекает P по внутренней (отличной от A и B) точке тогда и только тогда, когда величины

    v1 = a*x1 + b*y1 + c*z1 – 1,

    v2 = a*x2 + b*y2 + c*z2 – 1

    имеют разные знаки.

    Упражнение. Доказать, что координаты точки пересечения (точки C) плоскости ax + by + cz = 1 и отрезка, соединяющего две точки A(x1, y1, z1) и B(x2, y2, z2) (в случае, если существует точка пересечения и она является внутренней для AB) такие:

    C((x1*v2 – x2*v1) / (v2 – v1), (y1*v2 – y2*v1) / (v2 – v1), (z1*v2 – z2*v1) / (v2 – v1)), где

    v1 = a*x1 + b*y1 + c*z1 – 1,

    v2 = a*x2 + b*y2 + c*z2 – 1.
    Вернемся к (1). У нас имеется список всех точек, принадлежащих одновременно P и какому-нибудь ребру многогранника T. Выпуклая оболочка этих точек, очевидно, образует новую грань (сечение). Ни одна из этих точек не лежит внутри оболочки, так как все эти точки лежат на границе многогранника (не внутри). Удалим совпадающие точки в списке, отсортируем (у нас имеются координаты точки L для этой плоскости – (a, b, c) – коэффициенты уравнения плоскости). Получилась полноценная грань нового многогранника. Добавим ее в список граней.
    Такие действия нужно проделать для каждой собственной плоскости.
    Осталось сказать о способах вычисления объема имеющегося у нас многогранника. Напомним, что O(0, 0, 0) лежит строго внутри него. Поэтому искомый объем равен сумме объемов пирамид с вершиной O и каждой гранью в качестве основания.

    Напомним, что объем пирамиды равен H*S / 3, где H – расстояние от вершины до плоскости основания, S – площадь основания. В данном случае H = 1 – одно из свойств точки L для данной плоскости. Остается научиться находить площадь грани.

    Понятно, как на плоскости находить площадь многоугольника AУточним, что нам известно про такой треугольник. Одна из его вершин - точка L, две другие (A и B) – это соседние вершины некоторой грани. Можно посчитать площадь, например, используя формулу Герона, или же посчитать синус угла между векторами LA и LB с помощью скалярного произведения и найти площадь как половину произведениия длин двух сторон на синус угла между ними.
    Можно эту площадь найти другим способом. Вспомним, что абсолютная величина V (a, b, c) равна объему параллелепипеда на векторах a, b, c. В данном случае полезно посмотреть V(OL, LA, LB) = VЗамечание. Описание реализации гораздо длиннее самой реализации.
    Способ 2.
    Рассмотрим тело, получившееся при пересечении двух кубов. Будем вычислять его объем приближенно, используя, метод трапеций. Так как пересечение двух кубов не содержит криволинейных поверхностей, то результат приближенных вычислений будет очень близок к верному значению даже при небольшой точности вычислений.

    Разобьем отрезок [-1;1] оси OZ на N равных частей (от величины N будет зависеть точность вычислений). Пусть длина каждой части равна ∆z=2/N. Будем строить сечения тела плоскостями, проходящими параллельно плоскости XOY, через середины построенных отрезков. По теореме Лагранжа, на каждом отрезке [z
    VCut(zCut(z)–площадь сечения тела плоскостью, проходящей через точку z.

    Таким образом, чем меньше ∆z (соответственно, больше N), тем лучше точка (z
    Остается вопрос: как вычислять Cut(z)? Очевидно, что мы можем сначала строить сечение каждого из кубов отдельно, а затем находить площадь пересечения получившихся многоугольников. Более того, заметим, что сечение куба A не зависит от координаты z: оно является квадратом с вершинами в точках (1; 1) (1;-1) (-1;-1) (-1; 1). Сечение куба B можно найти, если последовательно пересечь плоскость со всеми его ребрами, а затем построить из получившихся точек выпуклый многоугольник.

    Пересечение многоугольников ищется по стандартной схеме: в него войдут
    все точки первого многоугольника, принадлежащие второму;
  • все точки второго многоугольника, принадлежащие первому;
  • точки попарного пересечения всех сторон обоих многоугольников.

  • перейти в каталог файлов


  • связь с админом