21.10.2018, 13:47 | #1 (permalink) |
Новичок
Регистрация: 21.10.2018
Сообщений: 3
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Задача о конспектах для лоботряса Лёши
Он знает, что сегодня у него осталось a a часов свободного времени, а завтра он сможет готовиться в течение b b часов. Обратите внимание, что на планете, где живет Леша, в дне может быть гораздо больше часов, чем в земном. Качество подготовки к экзамену зависит только от количества конспектов, которые Леша успеет прочитать. У Леши есть доступ к бесконечному количеству конспектов, но он знает, что первый конспект он прочитает за час, второй конспект за два часа и так далее, то есть Леша может прочитать конспект с номером k k за k k часов. Леша может читать конспекты в произвольном порядке, но он не может начать читать конспект в первый день, а дочитать во второй день. Таким образом, Леша должен прочитать несколько конспектов целиком в первый день, затратив на это не более a a часов суммарно, и несколько конспектов целиком во второй день, затратив на это не более b b часов. Сколько максимум конспектов успеет прочитать Леша за оставшееся время до экзамена? Какие конспекты он должен читать в первый день, а какие — во второй? |
21.10.2018, 13:47 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
Мой вам совет - поищите ответы в аналогичных обсуждениях Задача по РТЦ и С Задача на C++ Задача на Яве |
21.10.2018, 13:55 | #2 (permalink) |
Новичок
Регистрация: 21.10.2018
Сообщений: 3
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff fffffffffffffffffffffffffffffffffffffffffff
|
21.10.2018, 14:00 | #3 (permalink) |
Banned
Регистрация: 05.05.2018
Сообщений: 1,498
Сказал(а) спасибо: 0
Поблагодарили 32 раз(а) в 17 сообщениях
Репутация: 8252
|
Правила форума
Создавайте темы с осмысленным названием, топики с заглавием ПОМОГИТЕ!!!!!!!!!! будут удаляться. А за Последует наказание и отсутствие помощи. |
21.10.2018, 21:29 | #4 (permalink) |
Специалист
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,807
Сказал(а) спасибо: 340
Поблагодарили 583 раз(а) в 208 сообщениях
Репутация: 113184
|
Да... забавная такая задачка. Поломал малость голову. Но мне кажется, что я понял, как её решить.
1. Понятно, что если нужно набрать максимальное КОЛИЧЕСТВО конспектов, то целесообразно идти с первого и далее по восходящей. 2. Таким образом, общее время, затраченное на штудирование n конспектов (Tn), можно определить, исходя из формул арифметической прогрессии: Wn = W1 + (n-1)*Q Tn = (n/2)*(W1 +Wn). Здесь W1 — первый член прогрессии, Wn — n-й член, Q — разность. В данном случае W1=Q=1. 3. Можно поставить обратную задачу: зная суммарное время, определить число n. Это приведёт к квадратному уравнению, целая часть осмысленного корня которого и будет ответом. 4. Временно "забудем" о невозможности дробить изучение конспекта между двумя днями и определим n вышеописанным способом, исходя из Tn = a + b. 5. А теперь я попробую доказать, что, невзирая на условие "неделимости" конспектов, найденное значение n и будет ответом на задачу. Действуем так: Из двух чисел a и b выбираем наибольшее. Пусть это будет, например, b (второй день). Определяем Nb — количество конспектов, которое надлежит изучить во ВТОРОЙ день. Тут несколько сложнее: нужно рассмотреть УБЫВАЮЩУЮ арифметическую прогрессию, стартующую с Wn с разностью Q=-1. Также потребуем, чтобы сумма Tb членов не превышала b. И теперь — внимание! — во ВТОРОЙ день наш лоботряс должен проштудировать: a) конспекты с номерами от n до n-Nb. б) конспект с номером b-Tb. Таким образом, ВТОРОЙ день будет заполнен целиком. в) то, что останется из n конспектов, автоматически влезет в день a. Рассмотрим пример. Пусть a=4, b=8. Таким образом, общее время, отведённое на учёбу, составит 12 часов. Находим, что n=4, т.е. надо изучить конспекты с номерами 1, 2, 3 и 4. Общее время штудирования этих конспектов составит 10 часов. Во второй день (8 часов) находим, что лоботряс может проштудировать 2 конспекта (начиная с самого длинного и вниз ПО ОЧЕРЕДИ). Этими конспектами будут 4 и 3, так что Tb составит 7. Добавим к ним конспект с номером 8-7=1, таким образом, ВТОРОЙ день окажется заполненным целиком. А на первый останется конспект номер 2 и два часа свободного времени. Конечно, можно, например, вместо 4 взять конспект 5, но это не повлияет на общее количество конспектов, а оно-то нас и интересует. Как-то так. Вроде бы. |
22.11.2018, 19:58 | #5 (permalink) |
Member
Регистрация: 22.11.2018
Сообщений: 11
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 166
|
Здорово! Кажется, это называется "линейное программирование" Никогда не мог понять методику решения, кроме тупого перебора.
|
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|