| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Построение матрицы |
| Автор: IvanB 14.5.2006, 14:38 | ||
Извиняюсь, в центре помощи тему создавал, но ничего не получилось....  Спросить здесь можно? Задача была:
Хоть направление подскажите, в котором копать..... |
| Автор: neHb 14.5.2006, 17:10 |
| Какие есть ограничения на m,n,l,k? |
| Автор: IvanB 15.5.2006, 07:36 | ||
Нет разницы. Нужен просто алгоритм. Скорее для небольших чисел. (<200 где-то) |
| Автор: nostromo 15.5.2006, 15:49 | ||
| Постановка задачи до конца неясна: 1) При проверке возможности перехода, разность чисел берется по модулю, или между значениями в новой клетке и текущей? 2) Допустимы ли самопересечения пути? Есть варианты: -- Наступать на клетку в которой побывали нельзя. -- Пути могут самопересекаться, но с какими-то дополнительными ограничениями. -- Двигаться можно только вправо или вверх (самый простой и удобный случай, могу предложить алгоритм). Добавлено @ 15:52 3)
Имеются в виду m, n? |
| Автор: IvanB 15.5.2006, 16:17 | ||||||
Между значениями в новой клетке и в текущей.
Пути пересекаться не могут, т.к. из самопересечения следует бесконечность количества путей.
Да |
| Автор: nostromo 15.5.2006, 16:32 | ||
Правильно ли я понял, что в соседних клетках не могут стоять числа, скажем, 2, 3, если k=5? Путь на них зацикливается и, значит, в соседних клетках могут стоять только числа, разность по модуль между которыми не меньше k. Это так? |
| Автор: IvanB 15.5.2006, 16:40 | ||
....... Да. |
| Автор: nostromo 15.5.2006, 17:15 |
| Вот некоторые мысли. Если забыть об условии, регулирующем возможность перехода из одной клетки в другую и ограничиться только перемещениями вправо и вверх, то всего различных путей получится $C(n+m, n)$ (биномиальный коэффициент). Это довольно много. Так $C(200,100) ~ 10^59$. Алгоритм для случая, когда $l <= C(n+m, n)$: 1). В клетку (i, j) записываем число $k*(n+m-i-j)$. Это гарантирует, что из каждой клетки можно перейти только правее или выше (разность влево и вниз всегда равна $k$, а вправо и вверх --- $-k$). 2). С каждой клеткой связываем число $A$, проходящих через нее путей. Его нетрудно оценить. Пусть B(x,y) --- число путей из клетки (1,1) в клетку (x,y). Очевидно, в данном случае оно удовлетворяет рекурсивному соотношению: $B(i,j) = B(i-1,j) + B(i,j-1)$, что позволяет эффективно его вычислить. Тогда $A(i,j) = B(i,j) * B(m-i+i, n-j+1)$. 3) Если есть клетка, для которой $A(i,j) = A(m,n) - l$, то записав в нее достаточно большое или достаточно малое число (что бы попав внее уже нельзя было выйти. Будем далее называть такие клетки заблокированными) мы получим искомое решение задачи. 4) Если нет клетки, для которой $A(i,j) = A(m,n) - l$, то можно итеративно блокировать по одной клетки (стоит попробовать начинать с наименьших начений $A(i,j)$), пересчитывать в получившейся таблице значения $B(i,j), A(i,j)$ и искать подходящую клетку ($A(i,j) = A(m,n) - l$). Алгоритм не гарантирует решение задачи при всех значениях параметров, но, возможно, окажется полезным. В случае, если $l > C(n+m, n)$ ситуация заметно сложнее, причем очевидно, задача не всегда разрешима в принципе... |
| Автор: IvanB 15.5.2006, 17:25 | ||||
Это понял. За это спасибо.
А если ещё влево и вверх ходить можно. С право и вверх всё довольно очевидно получается. Проблема в том, что поставили именно такую задачу.  |
| Автор: nostromo 16.5.2006, 08:57 | ||
Именно такую задачу я и решаю. Прочитайте внимательнее то, что я написал. Сначала, как вспомогательная задача, рассмотрен случай, когда можно перемещаться только вправо и вверх, а затем предложен алгоритм решения исходной задачи, единственным ограничением для работы которого является условие $l <= C(m+n, n)$. При тех типичных значениях m, n, которые Вы указали, это означает, что l может быть 50-значным числом, а значение k вообще не важно. Вам этого мало? |
| Автор: IvanB 16.5.2006, 12:18 | ||
Простите за невнимательность. Насчёт ограничения C(m+n,n) уточню. |
