Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Алгоритм для решения задачи


Автор: 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_ @  18.12.2010,  21:15 Найти цитируемый пост)
Оказалось не так просто - машинная ошибка съедала все.

 smile Ошибка при расчёте определителя матрицы 16*16 не может быть такой большой! видимо, был выбран неправильный метод. Мне приходилось решать системы с сотню уравнений - и как-то особой потери точности не наблюдалось... к тому же всегда можно выполнить итерационное уточнение решения.

Цитата(_Y_ @  18.12.2010,  21:15 Найти цитируемый пост)
Судя по даным, они целочисленные. Может это можно использовать? 

При наличии гарантии, что решение существует, и оно целочисленное - можно.

Автор: _Y_ 19.12.2010, 16:19
Цитата(Akina @ 18.12.2010,  23:00)
 smile Ошибка при расчёте определителя матрицы 16*16 не может быть такой большой! видимо, был выбран неправильный метод.

Если вдаваться в детали, то я пробовал разные методы. Помню брал Гаусса с разной точностью, итерационный, еще уйму каких-то. Давно было.

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

a0 + a1*200 + a2*200 + ... + a16*200 = 0
.............
a0 + a1*210 + a2*190 + ... + a16*205 = 0

ни один алгоритм не соглашался воспринимать как достоверно различающиеся.

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

Автор: Фантом 19.12.2010, 19:54
Цитата(_Y_ @  19.12.2010,  16:19 Найти цитируемый пост)
Если вдаваться в детали, то я пробовал разные методы. Помню брал Гаусса с разной точностью, итерационный, еще уйму каких-то. Давно было.

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

Автор: _Y_ 19.12.2010, 23:01
Фантомименно. Проблема в том, что чем больше размер системы, тем больше этот самый эпсилон, определяющий близость определителя к нулю для данного вычислительного метода при данной машинной ошибке.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)