Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > Delphi > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 14.10.2016, 17:38   #1
kukobch
Пользователь
 
Регистрация: 14.10.2016
Сообщений: 18
По умолчанию

Ученым удалось отправить на планету Марс мини-фабрику, которая может та одни сутки произвести мини-фабрику или дрона для сбора воды ( мини-фабрика или дрон для сбора воды могут начать работу только со следующих суток). Дрон собирает одну единицу воды за одни сутки.
Определите, за какое минимальное количество суток удастся собрать не менее N единиц воды.
Формат вхолных линных
Задаегся одно число N (1 <, N <, 10ч) - необходимое количество воды.
Формат выходных линных
Одно целое число М- минимально необходимое количество суток.

Замечание
Одна из правильных последовательностей действий выглядит так:
• В первые сутки мини-фабрика производит дрона для сбора воды,
• За вторые сутки мини-фабрика производит еще одного дрона, а первый дрон собирает одну единицу воды;
• За третьи сутки мини-фабрика может произвести еще одного дрона или мини- фабрику, при этом первый дрон собирает еще одну единицу воды (итого он собрал
2 единицы воды), а второй дрон собирает единицу воды. Таким образом, накоплено
3 единицы воды за трое суток.
Другая последовательность действий состоит в том, чтобы за первые сутки построить еще одну мини-фабрику, а за вторые сутки произвести двух дронов, которые на третьи сутки соберут 2 единицы воды.

помогите программу составить

Последний раз редактировалось Аватар; 14.10.2016 в 20:29.
kukobch вне форума Ответить с цитированием
Старый 14.10.2016, 18:17   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,260
По умолчанию

Цитата:
Задаегся одно число N (1 <, N <, 10ч) - необходимое количество воды.
меньше чего?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 14.10.2016, 19:33   #3
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,061
По умолчанию

Это он так изобразил 1 <= N <= 10^9

олимпиадная задача
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 15.10.2016, 10:23   #4
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,260
По умолчанию

Цитата:
Это он так изобразил 1 <= N <= 10^9
ну это всё меняет.
я думал от 1 до 10 - тут реально нарисовать полный перебор вариантов (я думал через рекурсию ветление запулить), но 10^9 - это для рекурсии многовато (ну, понятно, что рекурсия будет намного меньше, т.к. 10^9 это суммарное собранное значение, но всё равно количество вызовов (глубина стека) будет слишком велико.
Значит, это тупиковый путь.

Господа, кто видит алгоритм решения данной задачки, подскажите, как она реализуется?
Serge_Bliznykov вне форума Ответить с цитированием
Старый 15.10.2016, 11:29   #5
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,061
По умолчанию

Да, перебором не пойдет, там экспоненциальный рост или факториальный, сильно не вникал, уже для сотни дней немереное число вариантов. Должна быть некая формула. А вот как вывести? Крутые старшеклассники должны быть в математике
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 15.10.2016, 12:27   #6
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 414
По умолчанию

Я сначала думал, что можно методом половинного деления.
Ведь по одной из стратегий - сначала накапливаются фабрики, потом они выпускают водосборщиков и на следующий день есть N воды. По такой стратегии требуется
(log2 N)+2 = (log2 10^9)+2=30+2=32 дня.
Потом можно было бы придумать критерий - искать день, начиная с которого выпускаются только водовозы или искать соотношение между фабриками и водовозами в ежедневном выпуске.

А с другой стороны - почему бы и не полный перебор - ограничения 2 секунды, и глубина погружения не более 32. Или комбинация перебора с двоичным поиском на каждых сутках.
FPaul вне форума Ответить с цитированием
Старый 15.10.2016, 12:30   #7
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,061
По умолчанию

За 32 дня ни при какой стратегии не будет 10^9
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 15.10.2016, 12:43   #8
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 414
По умолчанию

Почему? Ведь при накоплении фабрик их количество удваивается каждый день.
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 воды.

Или где-то порок в рассуждениях?
FPaul вне форума Ответить с цитированием
Старый 15.10.2016, 12:59   #9
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,061
По умолчанию

Согласен, не прав. Для такой стратегии и итераций не нужно, просто найти минимальную степень двойки не меньшую N. Для малых N возможны нюансы. Насчет оптимальности вопрос
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 15.10.2016, 13:07   #10
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 414
По умолчанию

Да, поэтому и предлагаю или полный перебор, ограниченный 32 днями.
Или рекурсивный спуск с поиском соотношения производства в данный день для достижения минимума (улучшенный перебор). Почему-то ощущение, что будет один "горб=яма" в целевой функции на каждых сутках.
FPaul вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Программа для сбора почты. Denslav Софт 2 09.10.2015 09:28
ПО для учета анализа воды ElenaTro Софт 3 26.11.2013 08:54
Нужен помощник для создания программы для сбора WMZ wmsbor Фриланс 1 20.01.2012 10:02
Программа для сбора информации о компе xaero93 Помощь студентам 2 31.01.2011 14:08
Программа для сбора колличества посещений sergiksergik Фриланс 4 11.04.2009 21:33