Метод потенциалов Транспортная задача

@Qazan · Регистрация: 30.04.2013

Как можно найти цикл в матрице ?
нехватает этой чудо функций

@SatanaXIII · 23.04.2014, 09:49

Сообщение от Qazan

Как можно найти цикл в матрице ?

Не могли бы вы пояснить, что имеется в виду под циклом?

@Qazan · 24.04.2014, 08:52 **[ТС]**

SatanaXIII,

Пусть имеется некоторая матрица размера (n,m) . В ней выделены n + m - 1 элементов.Назовем их Хорошими.
Если в Хороших элементах нет цикла то они ОченьХорошие.

Циклом в Хороших элементах называется такое подмножество A элементов из Хороших,что
в каждой строчке и столбце наидется ровно два элемента .

Например ,
1. (1,1) (1,3) (3,3) (3,5) (5,5) (5,1)
2. (1,1) (1,3) (3,3) (3,1)
для матрицы размерности больше 5

@Izual · 24.04.2014, 11:24

Сообщение от Qazan

Циклом в

Сообщение от Qazan

элементах называется

Сообщение от Qazan

подмножество A элементов

Сообщение от Qazan

что в каждой строчке и столбце наидется ровно два элемента

"А" - это сколько? Если есть n на m...
Если опустить "А" и взять в разсчёт что нужно ровно два элемента одинаковых найти - ну берите и сравнивайте.
Создайте переменную, например int k=0; Начинаете перебором сравнивать элементы.. блин у тебя 169 репутация, а задача начального уровня. Подобные задачи есть в книге, которая является азом обучения "С/С++ в задачах и примерах" автор Н.Культин.

@Qazan · 24.04.2014, 14:17 **[ТС]**

Izual, подмножество - тогда наверное меньше чем m + n - 1

а все нужно , чтобы каждый индекс встречался дважды при количестве элементов больше 3

PS : По факту моя репутация 20

@Izual · 24.04.2014, 15:16

Сообщение от Qazan

наверное меньше чем m + n - 1

Что значит наверное, что препод не уточнил?

Если у нас вся матрица это m x n, то (если взять m=5 и n=6) всего будет из примера 30 элементов. Но мы разсматриваем только m+n-1, значит всего 10 из 30.. И какие эти 10? Не очень ясно где эти 10 элементов вообще находятся...

@Qazan · 24.04.2014, 16:04 **[ТС]**

Izual, вы меня не поняли

если я говорю о подмножестве, значит это меньше либо равно ,не так ли ?

Я понял ,что задачу следует интерпретировать так

Найти все элементы у которых координаты встречаются по два (рассматривая отдельно i и j е координаты).

у меня пока такая идея :

создать массив целых чисел b размером max{n,m}

теперь проходя по Хорошим элементам
делать b[i]++; & b[j]++;

потом

C++

 
   for(int i = 0;i < min{n,m};i++)
   { 
       if(b[i] != 4) return false;
   } 
   for(iunt i = min{n,m};i < max{n,m};i++)
   {
       if(b[i] != 2) return false;
   }
   return true;

Как вы думаете оптимально ?
может можно быстрей и экономней ?

@Izual · 24.04.2014, 16:39

Сообщение от Qazan

может можно быстрей и экономней ?

Зачем? Вы ведь не будете эту формулу использовать для грамоздких целей, где под миллион n m. А раз так то и оптимизировать не вижу смысла, к тому же предполагаю что задача изначально не для usability, а для развития логики и демонстрации умений создавать алгоритм. А раз так - то вы уже сделали то что надо было.
Хотя с другой стороны я оптимизацией никогда не занимался в "мелочном плане", оптимизация нужна там где это жизненно необходимо - т.е. для реального использования при этом соотнося "цена и качество", ведь оптимизировать можно и через сам ассемблер, но смысла писать код на ассемблере - ну никакого нет. Так что то что я подчеркнул из книги Фленова "Иссуство программирования C++ и DirectX", так это то что оптимизировать надо в пределах разумного и только если игра стоит свеч.
У вас получился минимизированный код - это уже хорошо, я обычно чисто на это делаю упор - чем меньше строк кода - тем лучше. А то ведь когда реальные программы делаеш, то оптимизация может принести вместо 2-3 строк все 20-30, а это слишком усложняет жизнь, особенно когда изначально под 10 000 строк кода.(и в 20 раз если умножить - будет ппц, не стоит оно того, т.е. возможно только в отдельных моментах. Да и сила нынешних компов растёт, с появлением много процессорных чипов появился смысл делать много поточные приложения, которые оптимизируют в 1.9 раз(почти в 2) как минимум - а это куда больше чем даже самый навороченный оптимизированный код.(ну в передлах разумного построения изначального истественно)
Так что не замарачивайтесь имхо..

@Qazan · 24.04.2014, 20:23 **[ТС]**

Izual, для домашки по методам оптимизаций
лень писать все итераций

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10
		1
	Метод потенциалов Транспортная задача 23.04.2014, 08:52. Показов 2798. Ответов 8 Метки нет (Все метки) Как можно найти цикл в матрице ? нехватает этой чудо функций 0

@SatanaXIII Почетный модератор 5850 / 2861 / 392 Регистрация: 01.11.2011 Сообщений: 6,907
	23.04.2014, 09:49	2
	Сообщение от Qazan Как можно найти цикл в матрице ? Не могли бы вы пояснить, что имеется в виду под циклом? 0

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10
	24.04.2014, 08:52 [ТС]	3
	SatanaXIII, Пусть имеется некоторая матрица размера (n,m) . В ней выделены n + m - 1 элементов.Назовем их Хорошими. Если в Хороших элементах нет цикла то они ОченьХорошие. Циклом в Хороших элементах называется такое подмножество A элементов из Хороших,что в каждой строчке и столбце наидется ровно два элемента . Например , 1. (1,1) (1,3) (3,3) (3,5) (5,5) (5,1) 2. (1,1) (1,3) (3,3) (3,1) для матрицы размерности больше 5 0

@Izual 143 / 122 / 21 Регистрация: 13.11.2012 Сообщений: 1,564
	24.04.2014, 11:24	4
	Сообщение от Qazan Циклом в Сообщение от Qazan элементах называется Сообщение от Qazan подмножество A элементов Сообщение от Qazan что в каждой строчке и столбце наидется ровно два элемента "А" - это сколько? Если есть n на m... Если опустить "А" и взять в разсчёт что нужно ровно два элемента одинаковых найти - ну берите и сравнивайте. Создайте переменную, например int k=0; Начинаете перебором сравнивать элементы.. блин у тебя 169 репутация, а задача начального уровня. Подобные задачи есть в книге, которая является азом обучения "С/С++ в задачах и примерах" автор Н.Культин. 0

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10
	24.04.2014, 14:17 [ТС]	5
	Izual, подмножество - тогда наверное меньше чем m + n - 1 а все нужно , чтобы каждый индекс встречался дважды при количестве элементов больше 3 PS : По факту моя репутация 20 0

@Izual 143 / 122 / 21 Регистрация: 13.11.2012 Сообщений: 1,564
	24.04.2014, 15:16	6
	Сообщение от Qazan наверное меньше чем m + n - 1 Что значит наверное, что препод не уточнил? Если у нас вся матрица это m x n, то (если взять m=5 и n=6) всего будет из примера 30 элементов. Но мы разсматриваем только m+n-1, значит всего 10 из 30.. И какие эти 10? Не очень ясно где эти 10 элементов вообще находятся... 0

@Izual 143 / 122 / 21 Регистрация: 13.11.2012 Сообщений: 1,564
	24.04.2014, 16:39	8
	Сообщение от Qazan может можно быстрей и экономней ? Зачем? Вы ведь не будете эту формулу использовать для грамоздких целей, где под миллион n m. А раз так то и оптимизировать не вижу смысла, к тому же предполагаю что задача изначально не для usability, а для развития логики и демонстрации умений создавать алгоритм. А раз так - то вы уже сделали то что надо было. Хотя с другой стороны я оптимизацией никогда не занимался в "мелочном плане", оптимизация нужна там где это жизненно необходимо - т.е. для реального использования при этом соотнося "цена и качество", ведь оптимизировать можно и через сам ассемблер, но смысла писать код на ассемблере - ну никакого нет. Так что то что я подчеркнул из книги Фленова "Иссуство программирования C++ и DirectX", так это то что оптимизировать надо в пределах разумного и только если игра стоит свеч. У вас получился минимизированный код - это уже хорошо, я обычно чисто на это делаю упор - чем меньше строк кода - тем лучше. А то ведь когда реальные программы делаеш, то оптимизация может принести вместо 2-3 строк все 20-30, а это слишком усложняет жизнь, особенно когда изначально под 10 000 строк кода.(и в 20 раз если умножить - будет ппц, не стоит оно того, т.е. возможно только в отдельных моментах. Да и сила нынешних компов растёт, с появлением много процессорных чипов появился смысл делать много поточные приложения, которые оптимизируют в 1.9 раз(почти в 2) как минимум - а это куда больше чем даже самый навороченный оптимизированный код.(ну в передлах разумного построения изначального истественно) Так что не замарачивайтесь имхо.. 1

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10
	24.04.2014, 20:23 [ТС]	9
	Izual, для домашки по методам оптимизаций лень писать все итераций 0

Опции темы