Исходное сообщение
"Нужна помощь при написании программы (псевдокод или C++)" Отправлено skb7, 25-Ноя-13 02:15
> сдается мне, что именно в Вашем посте выше была ссылка на использование > графов для решения подобных задач, которая сейчас благополучно пропала. Вышка 1-2 > курс института. Ссылка никуда не пропадала. На всякий случай, вот она: http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&... Задача там называется "Путь максимальной стоимости". Графов я там не заметил, обычный двумерный массив. И да, по этой ссылке вы можете видеть (в самом конце) подтверждение того, что говорил вам pavlinux, и что говорил я: невозможно уменьшить сложность алгоритма для этой задачи, которая есть O(n*m), что является как раз-таки сложностью брутфорса. Если вы посмотрите алгоритм, реализованный там, то убедитесь в этом, там будет что то типа: for (i = 0; i < n; ++i) {     for (j = 0; j < m; ++j) {         /* some code */     } } Цитата оттуда: Сложность алгоритма нахождения пути максимальной стоимости также имеет порядок O(nm) и, очевидно, не может быть уменьшена, поскольку для решения задачи необходимо использование каждого из nm элементов данного массива P.

Ваше сообщение
Имя*:
EMail:	Для отправки новых сообщений в текущей нити на email укажите знак ! перед адресом, например, !user@host.ru (!! - не показывать email). Более тонкая настройка отправки ответов производится в профиле зарегистрированного участника форума.
Заголовок*:
Сообщение*:	>> сдается мне, что именно в Вашем посте выше была ссылка на использование >> графов для решения подобных задач, которая сейчас благополучно пропала. Вышка 1-2 >> курс института. > Ссылка никуда не пропадала. На всякий случай, вот она: > http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&chapterid=57 > Задача там называется "Путь максимальной стоимости". > Графов я там не заметил, обычный двумерный массив. > И да, по этой ссылке вы можете видеть (в самом конце) подтверждение > того, что говорил вам pavlinux, и что говорил я: невозможно уменьшить > сложность алгоритма для этой задачи, которая есть O(n*m), что является как > раз-таки сложностью брутфорса. Если вы посмотрите алгоритм, реализованный там, то убедитесь > в этом, там будет что то типа: > [code] > for (i = 0; i < n; ++i) { > for (j = 0; j < m; ++j) > { > /* some code */ > } > } > [/code] > Цитата оттуда: > [code] > Сложность алгоритма нахождения пути максимальной стоимости также имеет порядок O(nm) и, > очевидно, не может быть уменьшена, поскольку для решения задачи необходимо использование > каждого из nm элементов данного массива P. > [/code]
	Введите код, изображенный на картинке: