![]()
Обсуждение![]()
:![]()
Жадный алгоритм
Проект «Информационные технологии» (уровень 3, важность высокая) 
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете Уровень статьи по шкале оценок проекта: в развитии
Важность статьи для проекта «Информационные технологии»: высокая |
Алгоритмов по-моему не хватает. Насколько я знаю есть ещё алгоритмы Дейкстра, Флойда, и ещё какие-то. Я о них ничё не знаю, поэтому писать не буду.
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)
Ответить
[ответить
]