| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм для решения задачи |
| Автор: spamoney 18.12.2010, 13:23 |
| Здравствуйте, помогите составить алгоритм для следующей задачки: Есть следующая таблица: Y/X 100 300 900 600 100 700 - - - - - 300 - - - - - 100 - - - - - 600 - - - - - 300 - - - - - Необходимо вместо прочерков поставить 9 цифр (не меньше, не больше), таким образом что бы сумма каждой строки по X соответсвовала уже извесному (начальному) числу по X, аналогично и по Y т.е пример: Y/X 100 300 900 600 100 700 - 100 600 - - 300 100 - 200 - - 100 - - 100 - - 600 - 200 - 400 - 300 - - - 200 100 Смотрим соответсвие: Y1=700=100+600 Y2=300=100+200 .... X3=900=600+200+100 X4=600=400+200 .... Помогите пожалуйста составить алгоритм который бы вывел все возможные варианты расстановки 9 чисел, а то я уже всю голову сломал... |
| Автор: Akina 18.12.2010, 16:51 |
| Ну так это же тривиальное решение системы линейных уравнений. |
| Автор: _Y_ 18.12.2010, 20:15 |
| Akina, мне много лет назад понадобилось решить систему 16 линейных уравнений. Оказалось не так просто - машинная ошибка съедала все. Судя по даным, они целочисленные. Может это можно использовать? |
| Автор: Akina 18.12.2010, 23:00 |
При наличии гарантии, что решение существует, и оно целочисленное - можно. |
| Автор: _Y_ 19.12.2010, 16:19 | ||||
Если вдаваться в детали, то я пробовал разные методы. Помню брал Гаусса с разной точностью, итерационный, еще уйму каких-то. Давно было. Проблема же заключается в том, что чем больше линейных уравнений в системе, тем больше, для получения достоверного результата, должны разниться известные величины. А у меня разброс между ними был в пределах процентов 10-20 только (сколь помню). Ну, например, уравнения с такого рода коэффициентами
ни один алгоритм не соглашался воспринимать как достоверно различающиеся. Как я понял из первого поста, известные значения в заданной таблице могут быть любыми. Возможно и размер матрицы может быть не только 5х5. Поэтому и сомнения у меня возникли. |
| Автор: _Y_ 19.12.2010, 23:01 |
| Фантом, именно. Проблема в том, что чем больше размер системы, тем больше этот самый эпсилон, определяющий близость определителя к нулю для данного вычислительного метода при данной машинной ошибке. |