Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 25.04.2007, 10:19   #1
★★★★★★★★★★★★★
 
Hrach_Techie's Avatar
 
Join Date: 08 2004
Location: London, UK
Age: 38
Posts: 16,531
Downloads: 8
Uploads: 0
Reputation: 482 | 6
Default решение еще одной задачки из теории алгоритмов - может кому и пригодится

из серии блестим соплей на солнце пока Гаусс думал о новой задаче

Quote:
Given an integer matrix A(m, n). Prove that applying the operations of change of sign in a row or in a column one can get a matrix with nonnegative sums of elements in all rows and columns.
решение:
представим отрицательные числа в матрице 0 а положительные соответсвенно 1 имеем следующий паттерн:

1 0 0 1 1 1
0 0 0 0 0 1
0 0 1 1 1 1
1 1 1 1 1 1
0 1 1 1 1 1
......

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

возражения?
Reply With Quote
Old 25.04.2007, 11:12   #2
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 39
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

У меня есть альтернативная задача: имея систему уравнений Nm = 0, надо найти базис K с максимальным количеством позитивных элементов.
Reply With Quote
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 14:03.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.