|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 17 Jan 2003 18:48:11
To : Vitaly Lugovsky
Subject : Re: коммивояжёр
--------------------------------------------------------------------------------
> считать за труд. Сам же алгоритм простенький, намного короче его и не
> записать:
Итак, Вы признали, что применение рекурсии не дает пользы
дла решения первого примера. И даже написали свое решение,
которое точь-в-точь воспроизводит приведенный мною алгоритм на ML-e.
Хочу отметить еще такой момент: Сначала я дал описание
задачи (что бы подумать), а потом с задержкой привел решение.
Судя по Вашей реакции, вначале Вы не поверили, что матричный
алгоритм и есть решение задачи, и требовали от меня доказательств
адекватности приведенного алгоритма поставлений задаче.
Отсюда вывод: Ваши рекурсивные изыскания в области
разработки алгоритма явно лежали в стороне от правильного
решения. Следовательно, знание рекурсии во всех ее проявлениях
не сильно помогло Вам самому разработать правильный алгоритм
для решения этой задачи. И где-то сутки Вам потребовались,
чтобы убедиться в адекватности приведенного мною матричного
алгоритма поставленой задаче.
Hапоминаю: на topcoder-e люди, не зацикленые исключительно
на рекурсии, такой алгоритм разрабатывают и кодируют примерно
за 40 минут.
То есть человек получил описание задачи
(не способа ее решения, а именно описание задачи) - и через
40 минут засабмитил безглючный код, решающий эту задачу.
----------------------------------------------------------
Перейдем теперь к сравнению примеров:
**** Первый пример:
Итерацинное решение от меня:
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)
**** Второй пример:
Мое итерационное решение:
queue<Node*> q;
q.put(&root);
while(!q.empty()) {
Node *cur = q.get();
do_something(cur); // Processing current node
q.put(cur->left); q.put(cur->right);
}
Ваше рекурсивное решение:
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) | Tnone -> nxtlyr tl
)
| [] -> []
in tfindl f (nxtlyr nl)
--------
Теперь пусть обшество сравнит приведенные примеры,
и выскажет свое мнение в пользу читабельности, понятности,
компактности, эффективности и возможности анализа того или
иного алгоритма и приведенной в примерах его реализации.
В обшем же случае вопрос стоит так: Сильно ли рекурсия облегчила
жизнь при решении вышеприведенных задач-примеров?
Покамест же я не вижу реальных преимушеств Вашего подхода
перед классическим.
Резюмирую же я свой ответ фразой из произведения Михаила Афанасьевича Булгакова:
"Вы, профессор, воля ваша, что-то нескладное придумали! Оно,
может, и умно, но больно непонятно. Hад вами потешаться будут".
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
