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

@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++
1
2
3
4
5
6
7
8
9
10
 
   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, для домашки по методам оптимизаций
лень писать все итераций

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 27.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 27.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 27.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 25.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 25.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10

	Метод потенциалов Транспортная задача 23.04.2014, 08:52. Показов 3300. Ответов 8 Метки нет (Все метки) Как можно найти цикл в матрице ? нехватает этой чудо функций 0

@Qazan 215 / 63 / 25 Регистрация: 30.04.2013 Сообщений: 865 Записей в блоге: 10
	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 0

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

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