Технический форум

Технический форум (http://www.tehnari.ru/)
-   Delphi, Kylix and Pascal (http://www.tehnari.ru/f43/)
-   -   Задача о конспектах для лоботряса Лёши (http://www.tehnari.ru/f43/t261462/)

ADOLAT 21.10.2018 13:47

Задача о конспектах для лоботряса Лёши
 
В далекой-далекой галактике студент Леша узнал, что через два дня у него экзамен. Так получилось, что за весь год он ни разу не сходил на занятия. Леша не отчаялся и решил рационально распределить оставшееся время до экзамена на подготовку.

Он знает, что сегодня у него осталось
a
a часов свободного времени, а завтра он сможет готовиться в течение
b
b часов. Обратите внимание, что на планете, где живет Леша, в дне может быть гораздо больше часов, чем в земном. Качество подготовки к экзамену зависит только от количества конспектов, которые Леша успеет прочитать. У Леши есть доступ к бесконечному количеству конспектов, но он знает, что первый конспект он прочитает за час, второй конспект за два часа и так далее, то есть Леша может прочитать конспект с номером
k
k за
k
k часов. Леша может читать конспекты в произвольном порядке, но он не может начать читать конспект в первый день, а дочитать во второй день.

Таким образом, Леша должен прочитать несколько конспектов целиком в первый день, затратив на это не более
a
a часов суммарно, и несколько конспектов целиком во второй день, затратив на это не более
b
b часов. Сколько максимум конспектов успеет прочитать Леша за оставшееся время до экзамена? Какие конспекты он должен читать в первый день, а какие — во второй?:jazik::lamo::bsod:

ADOLAT 21.10.2018 13:55

ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffff fffffffffffffffffffffffffffffffffffffffffff:sigh:

highman3 21.10.2018 14:00

http://www.tehnari.ru/f8/t15561/

Создавайте темы с осмысленным названием, топики с заглавием ПОМОГИТЕ!!!!!!!!!! будут удаляться.
А за

Цитата:

Сообщение от ADOLAT (Сообщение 2605500)
ffffffffffffffffffffffffffffffffffffffffffffffffff fffffffffffffffffffffffffffffffffffffff

Последует наказание и отсутствие помощи.

Vladimir_S 21.10.2018 21:29

Да... забавная такая задачка. Поломал малость голову. Но мне кажется, что я понял, как её решить.
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, но это не повлияет на общее количество конспектов, а оно-то нас и интересует.
Как-то так. Вроде бы.

GrayBill 22.11.2018 19:58

Здорово! Кажется, это называется "линейное программирование" :) Никогда не мог понять методику решения, кроме тупого перебора.


Часовой пояс GMT +4, время: 19:52.

Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.