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

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

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


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 15 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

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

Ученым удалось отправить на планету Марс мини-фабрику, которая может та одни сутки произвести мини-фабрику или дрона для сбора воды ( мини-фабрика или дрон для сбора воды могут начать работу только со следующих суток). Дрон собирает одну единицу воды за одни сутки.
Определите, за какое минимальное количество суток удастся собрать не менее 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
Сообщений: 25,613
Репутация: 5617
По умолчанию

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

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

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

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

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

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

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

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

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

Почему? Ведь при накоплении фабрик их количество удваивается каждый день.
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
Адрес: Северодонецк.ua
Сообщений: 18,797
Репутация: 6622
По умолчанию

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

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Программа для сбора почты. 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


17:48.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.

Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru