|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
04.03.2017, 20:54 | #1 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Задачка о числах
Здравствуйте
Мне нужна ваша помощь в следующем задании Дана последовательность чисел a1, a2, ..., aN. За одну операцию разрешается удалить любое (кроме крайних) число, заплатив за это штраф, равный произведению этого числа на сумму соседних. Требуется удалить все числа, кроме крайних, с минимальным суммарным штрафом. Код:
Что не так? Заранее спасибо |
04.03.2017, 21:41 | #2 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Он не кривой, не верный просто.
Например для чисел 1 2 1 0 он удалит первой 2 и в результате будет 5 А если первой удалить 1, то получим 4 Можно попробовать выбирать не просто минимальную сумму, а минимальное произведение суммы соседних на число. Идея с потолка, уверенности 0 ))
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
05.03.2017, 12:52 | #3 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Действительно
----- Это изменило работу программы в лучшую сторону, но по-прежнему не то |
05.03.2017, 13:06 | #4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Да и я о том же. С чего решил, что таким способом найдешь оптимальное решение?
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
08.03.2017, 16:01 | #5 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Перебирать все варианты последовательности удаления 98 чисел не подъемная задача. Но можно упростить. Выбрав любое число на отрезке и считая его последним при удалении, оптимальным будет сумма решений левого и правого отрезков и штрафа за удаление этого последнего числа. Точки на отрезке брать в цикле, выбрать минимум. Для полученных отрезков рекурсивно то же самое и ой-ля-ля )) Ну еще оптимизировать, запомнив в массиве для каждого отрезка его минимальный штраф, что бы повторно не считать, когда он опять попадется в этих рекурсиях
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
08.03.2017, 19:16 | #6 |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,527
|
при наличии в последовательности 0 просто удалять ВСЕХ его соседей.
программа — запись алгоритма на языке понятном транслятору
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Проблема с запятой в числах с плавающей точкой | sarexer | Visual C++ | 2 | 17.09.2016 12:01 |
МАКРОС_ДОБАВЛЕНИЕ В ЧИСЛАХ НУЛЕЙ, ПОСЛЕ ЗАПЯТОЙ | Окоча Юра | Microsoft Office Word | 4 | 04.02.2010 12:43 |
sinh в комплексных числах | Brabus | Помощь студентам | 11 | 23.01.2010 23:36 |
Дата в числах | Titan123 | Общие вопросы Delphi | 6 | 25.12.2008 13:22 |
Как убрать пробелы в числах!! | vavany22 | Microsoft Office Excel | 27 | 11.11.2008 11:23 |