1 Востаннє редагувалося Q-bart (17.04.2018 11:29:13)

Тема: Температура і бінарний пошук

Hello!

В мене теж трабли з алгоритмами)

Така задачка:

Прихований текст
Протягом N днів робились записи температури. Але сталось так, що записи втратили, і залишились лише перший і останній.
Знаючи перший і останній запис температури, і також те, що за один день температура не може змінюватись більше як на K градусів, знайти макс. і мін. можливу температуру.

Напр. якщо сьогодні темп. 3 градуси, а K=4, то завтра вона може бути між -1 і 7 градусів.

Приклад:
N=4, K=7
First=-10
Last=1

Результат:
4, -13

Можливі розвитки:
-10 > -3 > 4 > 1
-10 > -13 > -6 > 1

Прихований текст
Ага, викладач сказав, що тут має бути бінарний пошук  :D

От і не шарю більше нічого)

Навчаюсь вчитись, щоб навчатись.

2 Востаннє редагувалося koala (17.04.2018 11:39:52)

Re: Температура і бінарний пошук

Нащо бінарний пошук? Тут тупо лінійні рівняння. Температура з першого дня може йти вгору за графіком

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

Оце наш максимум. Мінімум знаходиться аналогічно.
Раджу побудувати графіки, там це стає очевидним.

Подякували: Q-bart, 0x9111A, leofun01, HetmanNet, varkon5

3

Re: Температура і бінарний пошук

koala написав:

Нащо бінарний пошук? Тут тупо лінійні рівняння. Температура з першого дня може йти вгору за графіком

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, це не день?

Навчаюсь вчитись, щоб навчатись.

4

Re: Температура і бінарний пошук

Q-bart написав:
koala написав:

x - номер дня

А хібa x, це не день?

Га?

5

Re: Температура і бінарний пошук

ну  а треба ж макс температуру

Навчаюсь вчитись, щоб навчатись.

6

Re: Температура і бінарний пошук

Q-bart написав:

ну  а треба ж макс температуру

Тобто ви хочете сказати, що не можете з цих формул за x отримати y?
Тут іноді піднімають питання, нащо програмістам математика. Буду тепер відправляти у цю тему.

Подякували: Q-bart, leofun01, HetmanNet3

7

Re: Температура і бінарний пошук

Дякую

Навчаюсь вчитись, щоб навчатись.

8

Re: Температура і бінарний пошук

І побудуйте графіки.

9 Востаннє редагувалося Q-bart (23.04.2018 22:06:18)

Re: Температура і бінарний пошук

але цей код дав іншу відповідь, ніж в прикладі

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

Навчаюсь вчитись, щоб навчатись.

10

Re: Температура і бінарний пошук

А ви побудували графіки?

11

Re: Температура і бінарний пошук

так

Навчаюсь вчитись, щоб навчатись.

12

Re: Температура і бінарний пошук

Ну а тепер уважно подивіться на точки перетинів. Правда ж, вони зовсім не обов'язково цілі?

13 Востаннє редагувалося Q-bart (Вчора 00:08:34)

Re: Температура і бінарний пошук

https://i.imgur.com/QOScibF.png

Навчаюсь вчитись, щоб навчатись.

14

Re: Температура і бінарний пошук

А тепер знайдіть на цих прямих найвищу точку із цілою абцисою (для цього достатньо округлити абцису, бо нахили однакові, отже, більша точка буде просто в бік округлення). Це видно?