Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 09.12.2010, 05:33   #1
MadReason
Ищу работу
Форумчанин
 
Аватар для MadReason
 
Регистрация: 16.02.2007
Сообщений: 269
По умолчанию Комбинаторика

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

например:


получено 3 контура

разобрался с алгоритмом 1xN
F(ni)=F(ni-1)+ni

Код:
function F(n:byte):cardinal;
begin
if n=1 then result:=1 else
result:=f(n-1)+n;
end;
и с алгоритмом 2xN
kont:=x*f(y)+y*f(x)+1+fact(x)*fact( y);

где f() предыдущая функция и либо x, либо y должны быть равны 2

надеюсь кто-нибудь подскажет как это обобщить или еще чего хорошего)
или может кто подскажет как вывести что-то подобное до 8го порядка.
в ручную я на третьем уже сбился считать контуры)
Пишу на Delphi все что угодно, недорого, красиво, с комментариями
###icq 107335###

Последний раз редактировалось MadReason; 09.12.2010 в 05:36.
MadReason вне форума Ответить с цитированием
Старый 09.12.2010, 08:25   #2
Prime123
Пользователь
 
Регистрация: 07.12.2010
Сообщений: 79
По умолчанию

Контуры только прямоугольной и квадратичной формы?Или любые?
Если я чем-то вам помог-не стесняйтесь,ставьте +

Если ошибаюсь-поправляйте,учусь на ошибках,реагирую адекватно
Prime123 вне форума Ответить с цитированием
Старый 09.12.2010, 11:39   #3
MadReason
Ищу работу
Форумчанин
 
Аватар для MadReason
 
Регистрация: 16.02.2007
Сообщений: 269
По умолчанию

любые.
как бы обводим по граням клеток контуры, только чтоб замкнутые были и между собой не пересекались, больше ограничений нет.
нельзя например нарисовать квадратный замкнутый контур с дыркой внутри, т.к. нельзя непрерывной линией нарисовать такую фигуру
Пишу на Delphi все что угодно, недорого, красиво, с комментариями
###icq 107335###
MadReason вне форума Ответить с цитированием
Старый 09.12.2010, 12:03   #4
Z1000000
Форумчанин
 
Регистрация: 04.05.2010
Сообщений: 495
По умолчанию

Если условия задать в виде графа, то задача формулируется:
Найти Все циклы в графе.

Вот что пишет народ в Инете.

Цитата:
Очевидным решением задачи поиска циклов в заданном графе является применение DFS или, проще говоря поиска в глубину. Но, кажется, есть более оптимальные алгоритмы решения (хотя в общем случае задача является NP-полной).

Поиск в глубину, собственно, является естественным подходом для поиска циклов.
Однако, замечу, что лучше все-таки искать не все циклы графа поиском в глубину (решение "в лоб"), а только фундаментальное множество циклов. Т.к. каждый цикл графа может быть получен из циклов этого множества (фундаментального множества циклов) посредством операции симметрической разности (иногда получаются вырожденные случаи, но они легко отбрасываются).
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948
Z1000000 вне форума Ответить с цитированием
Старый 09.12.2010, 22:52   #5
MadReason
Ищу работу
Форумчанин
 
Аватар для MadReason
 
Регистрация: 16.02.2007
Сообщений: 269
По умолчанию

Большое спасибо за направление.
а нет алгоритма или примера поиска всех циклов в графе? буду очень признателен.
на сколько я понимаю, потом нужно будет разделить количество полученных циклов на 2? так как будет на один контур 2 цикла в разных направлениях?
Пишу на Delphi все что угодно, недорого, красиво, с комментариями
###icq 107335###
MadReason вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Комбинаторика и переборы C# pro100saniok Помощь студентам 2 05.12.2010 16:00
Комбинаторика Васильева Зинаида Помощь студентам 1 15.10.2010 18:55
Комбинаторика чисел и суммирование f1UZ Общие вопросы C/C++ 7 05.06.2010 16:25
Комбинаторика в Паскале shegan Помощь студентам 0 21.12.2009 21:01