Обсуждение:Жадный алгоритм (KQvr';yuny&"g;udw glikjnmb)
Проект «Информационные технологии» (уровень III, важность для проекта высокая)
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Untitled
[править код]Алгоритмов по-моему не хватает. Насколько я знаю есть ещё алгоритмы Дейкстра, Флойда, и ещё какие-то. Я о них ничё не знаю, поэтому писать не буду.
1. Есть-то они есть, да вот "жадные" ли они????
2. Неплохо бы слово "жадный" в кавычки взять. А то сами по себе алгоритмы не бывают ни жадными, ни щедрыми, ни добрыми, ни злыми. 94.25.37.21 20:03, 12 июля 2009 (UTC)
Примеры | Размен монет
[править код]В разделе про размен монет сказано, что, если сумма двух любых меньших номиналов всегда меньше или равна большему номиналу, то жадный алгоритм дает правильный ответ. Это неверно. Рассмотрим, например, номиналы 1, 10, 21 и попробуем разменять 30. Жадный алгоритм дает 1*21 + 9*1, т.е. 10 монет, при этом это можно сделать за 3 монеты: 3*10. --Metallo lom 21:20, 6 марта 2015 (UTC)
- Это верно подмечено, и ошибка тянется, наверное, с англовики, где вообще какое-то противоречие написано: In the US (and most other) coin systems, a greedy algorithm of picking the largest denomination of coin which is not greater than the remaining amount to be made will always produce the optimal result. This is not automatically the case, though: if the coin denominations were 1, 3 and 4, then to make 6, the greedy algorithm would choose three coins (4,1,1) whereas the optimal solution is two coins (3,3). РоманСузи 12:23, 7 марта 2015 (UTC)