Пересечение n-мерной плоскости с n-мерной областью

From

Max Alekseyev (2:5015/60)

To

Mykola Kovalchuk ()

Date

2003-01-23T16:55:22Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Mykola !

Replying to a message of Mykola Kovalchuk to All:

 MK> Есть n-мерная плоскость, задающаяся в виде:
 MK> A1*X1+A2*X2+...+An*Xn+B=0

Вообще-то это не плоскость, а гиперплоскость.

 MK> и n-мерная область задающаяся неравенствами:
 Xi>> =0 для всех i, а также
 MK> Xi<=Ci или Xi<=X(i+1)-Ci
 MK> (Ci>=0, для одной Xi используется только одно неравенство из второй
 MK> строчки, где она находится левой части). Плоскость гарантированно (по
 MK> условию) пересекает область, и на пересечении гарантированно есть
 MK> целочисленные точки. Так вот: надо найти ВСЕ эти целочисленные
 MK> точки...

Алгоритм Моцкина-Бургера для нахождения целочисленного остова тебе поможет...

Рекомендую почитать http://www.uic.nnov.ru/~zny/arageli/intpoint.ps
и посмотреть на программы http://www.uic.nnov.ru/~zny/arageli/arageli.html

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)