Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Температура і бінарний пошук
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Hello!
В мене теж трабли з алгоритмами)
Така задачка:
От і не шарю більше нічого)
Нащо бінарний пошук? Тут тупо лінійні рівняння. Температура з першого дня може йти вгору за графіком
y=t1+(x-1)*K а спускатися до останнього - за графіком
y=tN-(x-N)*KДе y - значення температури, x - номер дня (від 1 до N, зокрема при x=1 y(1)=t1+0*K=t1, при x=N y(N)=tN-0*K=tN).
Прирівнюємо:
t1+(x-1)*K = tN-(x-N)*K
t1 + K*x - K = tN - K*x + K*N
2*K*x = tN-t1 + K*(N+1)
x = (tN-t1)/(2*K) + (N+1)/2Оце наш максимум. Мінімум знаходиться аналогічно.
Раджу побудувати графіки, там це стає очевидним.
Нащо бінарний пошук? Тут тупо лінійні рівняння. Температура з першого дня може йти вгору за графіком
y=t1+(x-1)*Kа спускатися до останнього - за графіком
y=tN-(x-N)*KДе y - значення температури, x - номер дня (від 1 до N, зокрема при x=1 y(1)=t1+0*K=t1, при x=N y(N)=tN-0*K=tN).
Прирівнюємо:t1+(x-1)*K = tN-(x-N)*K t1 + K*x - K = tN - K*x + K*N 2*K*x = tN-t1 + K*(N+1) x = (tN-t1)/(2*K) + (N+1)/2Оце наш максимум. Мінімум знаходиться аналогічно.
Раджу побудувати графіки, там це стає очевидним.
А хібa x, це не день?
koala написав:x - номер дня
А хібa x, це не день?
Га?
ну а треба ж макс температуру
Дякую
І побудуйте графіки.
але цей код дав іншу відповідь, ніж в прикладі
N = 4
K = 7
t1 = -10
tN = 1
x = (tN - t1) / (2.0 * K) + (N + 1) / 2.0
print(x)
y = t1 + (x - 1) * K
print("max temp = ", y)result:
3.28571428571
('max temp = ', 6.0)приклад:
max = 4
А ви побудували графіки?
так
Ну а тепер уважно подивіться на точки перетинів. Правда ж, вони зовсім не обов'язково цілі?
А тепер знайдіть на цих прямих найвищу точку із цілою абцисою (для цього достатньо округлити абцису, бо нахили однакові, отже, більша точка буде просто в бік округлення). Це видно?
От і роби бінарним пошуком. Підбирай масив змін температури і шукай підходящі масиви.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися