|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 19 Sep 2001 00:14:30
To : Ђ¤аҐ© Љг¤апўжҐў
Subject : Получение коэффициентов.
--------------------------------------------------------------------------------
Replying to a message of Андрей Кудрявцев to Azamat Kalimullin:
АК> Зря Вы, батенька, все это имеете в виду. Вот диагноз этого случая:
АК> Уравнение A*x+B*y=1 - уравнение прямой на плоскости в Декартовых
АК> координатах. Если эта прямая сотержит хоть одну точку с целыми
АК> координатами, то ИМХО она содержит бесконечное множество таких
АК> точек-решений (доказать не берусь, но нутром чувствую).
А чего тут доказывать? Если пара (x, y) - решение, то решениями так же будут
пары (x+B,y-A), (x+2*B,y-2*A) и т.д.
АК> Hо прямая
АК> может и не содержать таких точек вообще. Простой пример: 2*x+2*y=1,
АК> точнее A=B<>1
АК> Встает два вопроса
АК> 1. Как отфильтровать нерешаемые уравнения, т.е. определить что для
АК> пары A B решений нет.
Очень просто. Если HОД(A,B) <> 1, то решений нет.
АК> 2. Какое решение выбрать, если их много.
То, для которого 0 <= x < B, -A < y <= 0, например.
P.S. Hастоятельно рекомендую познакомиться с книжкой А.Шеня "Программирование:
теоремы и задачи", ссылку на которую я тут недавно приводил.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.6
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
