|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Lugovsky 2:5080/1003 16 Jan 2003 19:01:25
To : Oleg Khovayko
Subject : Re: коммивояжёр
--------------------------------------------------------------------------------
Oleg Khovayko <olegh@hotpop.com> wrote:
> Так и быть, привожу решение:
>
> int NumWays(int I, int J, int K, vector< vector<int> > matrix) {
> vector<int> V(N);
> V[I] = 1;
> while(K--)
> V *= matrix; // тут векторное произведение вектора на матрицу
> return V[J];
> }
Так... Тут я погорячился. Обламываюсь с доказательством - оно
неэлементарное в достаточной мере для того, чтоб перевод в рекурсию вообще
считать за труд. Сам же алгоритм простенький, намного короче его и не
записать:
let numways n i j k m =
let v0 = Array.make n 0 in v0.(i) <- 1;
let v = dowhile (fun x -> vm_mul x m) k v0 in
v.(j)
> А вот еще один пример:
> Есть дерево. Задача: обойти дерево по слоям.
> Я утверждаю, что существует итеративное решение этой задачи,
> пропорциональное N, то есть каждый узел дерева посещается один раз.
>
> Рекуррентный алгоритм - в студию!
> А потом я дам итерационный...
Вот, типа, самый тупой и примитивный вариант:
let rec tfindl f nl =
let rec nxtlyr = function
hd :: tl ->
(match hd with
Tnode(v,l,r) -> if f v than raise (Found(v)) else
l::r::(nxtlyr tl)
)
| [] -> []
in tfindl f (nxtlyr nl)
Причём, тут рекурсия хвостовая - так что стек не растёт ни фига.
Hефункциональным тут является только исключение - но можно и без исключений
написать, мало что изменится.
Естественно, каждый узел дерева тут посещается лишь один раз.
--- ifmail v.2.15dev5
* Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
