|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
14.10.2016, 16:38 | #1 |
Пользователь
Регистрация: 14.10.2016
Сообщений: 18
|
Ученым удалось отправить на планету Марс мини-фабрику, которая может та одни сутки произвести мини-фабрику или дрона для сбора воды ( мини-фабрика или дрон для сбора воды могут начать работу только со следующих суток). Дрон собирает одну единицу воды за одни сутки.
Определите, за какое минимальное количество суток удастся собрать не менее N единиц воды. Формат вхолных линных Задаегся одно число N (1 <, N <, 10ч) - необходимое количество воды. Формат выходных линных Одно целое число М- минимально необходимое количество суток. Замечание Одна из правильных последовательностей действий выглядит так: • В первые сутки мини-фабрика производит дрона для сбора воды, • За вторые сутки мини-фабрика производит еще одного дрона, а первый дрон собирает одну единицу воды; • За третьи сутки мини-фабрика может произвести еще одного дрона или мини- фабрику, при этом первый дрон собирает еще одну единицу воды (итого он собрал 2 единицы воды), а второй дрон собирает единицу воды. Таким образом, накоплено 3 единицы воды за трое суток. Другая последовательность действий состоит в том, чтобы за первые сутки построить еще одну мини-фабрику, а за вторые сутки произвести двух дронов, которые на третьи сутки соберут 2 единицы воды. помогите программу составить Последний раз редактировалось Аватар; 14.10.2016 в 19:29. |
14.10.2016, 17:17 | #2 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
|
|
14.10.2016, 18:33 | #3 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
15.10.2016, 09:23 | #4 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
я думал от 1 до 10 - тут реально нарисовать полный перебор вариантов (я думал через рекурсию ветление запулить), но 10^9 - это для рекурсии многовато (ну, понятно, что рекурсия будет намного меньше, т.к. 10^9 это суммарное собранное значение, но всё равно количество вызовов (глубина стека) будет слишком велико. Значит, это тупиковый путь. Господа, кто видит алгоритм решения данной задачки, подскажите, как она реализуется? |
|
15.10.2016, 10:29 | #5 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Да, перебором не пойдет, там экспоненциальный рост или факториальный, сильно не вникал, уже для сотни дней немереное число вариантов. Должна быть некая формула. А вот как вывести? Крутые старшеклассники должны быть в математике
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
15.10.2016, 11:27 | #6 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Я сначала думал, что можно методом половинного деления.
Ведь по одной из стратегий - сначала накапливаются фабрики, потом они выпускают водосборщиков и на следующий день есть N воды. По такой стратегии требуется (log2 N)+2 = (log2 10^9)+2=30+2=32 дня. Потом можно было бы придумать критерий - искать день, начиная с которого выпускаются только водовозы или искать соотношение между фабриками и водовозами в ежедневном выпуске. А с другой стороны - почему бы и не полный перебор - ограничения 2 секунды, и глубина погружения не более 32. Или комбинация перебора с двоичным поиском на каждых сутках. |
15.10.2016, 11:30 | #7 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
За 32 дня ни при какой стратегии не будет 10^9
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
15.10.2016, 11:43 | #8 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Почему? Ведь при накоплении фабрик их количество удваивается каждый день.
1 день 1 действующая фабрика (ДФ) производит 1 фабрику 2 день 2 ДФ производят 2 фабрики 3 день 4 ДФ производят 4 фабрики ......................... 30 день 2^29 ДФ производят 2^29 фабрик 31 день 2^30 = 1'073'741'824 ~ 10^9 ДФ производят 2^30 водовозов 32 день фабрики безразличны, а 10^9 водовозов добывают 10^9 воды. Или где-то порок в рассуждениях? |
15.10.2016, 11:59 | #9 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Согласен, не прав. Для такой стратегии и итераций не нужно, просто найти минимальную степень двойки не меньшую N. Для малых N возможны нюансы. Насчет оптимальности вопрос
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
15.10.2016, 12:07 | #10 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Да, поэтому и предлагаю или полный перебор, ограниченный 32 днями.
Или рекурсивный спуск с поиском соотношения производства в данный день для достижения минимума (улучшенный перебор). Почему-то ощущение, что будет один "горб=яма" в целевой функции на каждых сутках. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Программа для сбора почты. | Denslav | Софт | 2 | 09.10.2015 08:28 |
ПО для учета анализа воды | ElenaTro | Софт | 3 | 26.11.2013 08:54 |
Нужен помощник для создания программы для сбора WMZ | wmsbor | Фриланс | 1 | 20.01.2012 10:02 |
Программа для сбора информации о компе | xaero93 | Помощь студентам | 2 | 31.01.2011 13:08 |
Программа для сбора колличества посещений | sergiksergik | Фриланс | 4 | 11.04.2009 21:33 |