1

Тема: "Розумне" сортування

Хай, от уявіть собі, є набір простих рівнянь, типу
x1+y2=5;
x2+y2=3;
x3+y2=5; і т.д.
Зазделегідь нам невідомі ні x, ні y, тому x1 ми приймаємо за нуль, і вже на основі цього значення обчислюємо значення інших змінних. От мені це треба запрограмувати, і виникла проблема в тому, аби відстортувати набір рівнянь таким чином, аби змінні, значення котрих я знайшов в попередньому рівняні, давали мені змогу знайти значення всіх наступних змінних. От вам приклад,
http://puu.sh/8HY2n.jpg зліва, це як в мене зара відстортовані рівняння. Проблема в четвертому рівнянні, як бачите, з попередніх рівнянь я не знаю значення ні змінної U3, ні змінної V2, тому не можу.. ну не можу, треба якось відсортувати набір рівнянь так, аби він виглядав, як зправа. Як це зробити? Код мені не потрібно, просто на словах поясніть правило, по якому має сортуватись масив рівнянь. Заздалегідь дякую

Прихований текст

, koala

.

2 Востаннє редагувалося koala (11.05.2014 15:13:03)

Re: "Розумне" сортування

У мене таке враження, що ви намагаєтеся розв'язати якусь задачу, але не хочете нам сказати, яку, тому напридумували собі ось таке, що аж заплуталися...
У нас є граф з вершинами x1,y1,x2,y2,... Коли ми фарбуємо одну вершину в певний колір, всі пов'язані із нею ребрами вершини також фарбуються. Питання: скільки вершин достатньо пофарбувати, щоб розфарбувати весь граф? Відповідь: це залежить від графа, точніше, від його зв'язності. Якщо він зв'язний, то 1; якщо ні - то треба по 1 в кожній компоненті зв'язності. Це зрозуміло?
Алгоритм:
Доки ( множина нерозв'язаних рівнянь не пуста )
- встановити довільне значення довільній змінній
- доки ( є рівняння із відомими змінними )
- - виключати рівняння з множини нерозв'язаних, додавати змінні до множини відомих
Коли виключаєте рівняння, можете його ставити в ваш відсортований масив.

3

Re: "Розумне" сортування

koala написав:

У мене таке враження, що ви намагаєтеся розв'язати якусь задачу, але не хочете нам сказати, яку, тому напридумували собі ось таке, що аж заплуталися...
У нас є граф з вершинами x1,y1,x2,y2,... Коли ми фарбуємо одну вершину в певний колір, всі пов'язані із нею ребрами вершини також фарбуються. Питання: скільки вершин достатньо пофарбувати, щоб розфарбувати весь граф? Відповідь: це залежить від графа, точніше, від його зв'язності. Якщо він зв'язний, то 1; якщо ні - то треба по 1 в кожній компоненті зв'язності. Це зрозуміло?
Алгоритм:
Доки ( множина нерозв'язаних рівнянь не пуста )
- встановити довільне значення довільній змінній
- доки ( є рівняння із відомими змінними )
- - виключати рівняння з множини нерозв'язаних, додавати змінні до множини відомих
Коли виключаєте рівняння, можете його ставити в ваш відсортований масив.

да то все та сама транспортна задача і метод потенціалів

4 Востаннє редагувалося Torbins (11.05.2014 18:13:35)

Re: "Розумне" сортування

Хм, а метод Гауса тут хіба не катить?
Щоправда далеко не кожна система рівнянь має розв'язок. Але якщо він усе ж таки є, то питання порядку обчислення зазвичай не стоїть. Може у вашої системи просто нема розв'язків?

5

Re: "Розумне" сортування

Тут змінних більше, ніж рівнянь, тому рішень нескінчена кількість - принаймні, так сформулював питання ТС, і я не маю підстав йому не вірити в його задачі.

6

Re: "Розумне" сортування

Хдопці хлопці, все ок, рівняння робляться, але от пошук того циклу знову дав збій

7

Re: "Розумне" сортування

Приклад реальних рівнянь можна? А то абстрактні речі можна обговорювати довго й з абстрактною користю.

Подякували: koala1

8

Re: "Розумне" сортування

Torbins написав:

Приклад реальних рівнянь можна? А то абстрактні речі можна обговорювати довго й з абстрактною користю.

да все ок з рівняннями, проблема з пошуком циклу в методі потенціалів

9

Re: "Розумне" сортування

Пане Torbins, так як koala пройшов повз моєї біди, та залишив мене помирати в муках, я звертаюся до Вас. Дивіться, є матриця, в деяких клітинках матриці є числа, в деяких немає. Ми обираємо клітинку, в котрій немає числа, та маємо побудувати цикл, кутами котрого будуть клітинки з числами. От Вам декілька прикладів. Дивіться на клітинки, в котрих є знак + або -. Також, аби ви не лякались, клітинки можуть містити два числа, і от кути цикла мають бути в саме таких клітинках. В цьому прикладі початок циклу в точці 1,3
http://puu.sh/8IsRe.png
В цьому прикладі початок в клітинці 3,1
http://puu.sh/8IsU5.png
А тут в 1, 2
http://puu.sh/8IsVM.png

10

Re: "Розумне" сортування

Так от, яким же має бути алгоритм, аби знайти такий цикл? Я вже і так, і так, але мій алгоритм не універсальний, для одної матриці він працює, а для іншої ні.

11

Re: "Розумне" сортування

Із цими таблицями давайте продовжимо в окремій темі: http://replace.org.ua/post/25213/#p25213